OpenRaiser/Intern-Atlas huggingface dataset:
Projecting the Forward Rate Flow onto a Finite Dimensional Manifold
Venue: arXiv cs.CE 2005
Year: 2005

Given a Heath-Jarrow-Morton (HJM) interest rate model $\mathcal{M}$ and a parametrized family of finite dimensional forward rate curves $\mathcal{G}$, this paper provides a technique for projecting the infinite dimensional forward rate curve $r_{t}$ given by $\mathcal{M}$ onto the finite dimensional manifold $\mathcal{G}$.The Stratonovich dynamics of the projected finite dimensional forward curve are derived and it is shown that, under the regularity conditions, the given Stratonovich differential equation has a unique strong solution. Moreover, this projection leads to an efficient algorithm for implicit parametric estimation of the infinite dimensional HJM model. The feasibility of this method is demonstrated by applying the generalized method of moments.
Multi-Proxy Multi-Signcryption Scheme from Pairings
Venue: arXiv cs.CR 2005
Year: 2005

A first multi-proxy multi-signcryption scheme from pairings, which efficiently combines a multi-proxy multi-signature scheme with a signcryption, is proposed. Its security is analyzed in detail. In our scheme, a proxy signcrypter group could be authorized as a proxy agent by the cooperation of all members in the original signcrypter group. Then the proxy signcryptions can be generated by the cooperation of all the signcrypters in the authorized proxy signcrypter group on behalf of the original signcrypter group. The correctness and the security of this scheme are proved.
Algorithms for Max Hamming Exact Satisfiability
Venue: arXiv cs.DS 2005
Year: 2005

We here study Max Hamming XSAT, ie, the problem of finding two XSAT models at maximum Hamming distance. By using a recent XSAT solver as an auxiliary function, an O(1.911^n) time algorithm can be constructed, where n is the number of variables. This upper time bound can be further improved to O(1.8348^n) by introducing a new kind of branching, more directly suited for finding models at maximum Hamming distance. The techniques presented here are likely to be of practical use as well as of theoretical value, proving that there are non-trivial algorithms for maximum Hamming distance problems.
On Hats and other Covers
Venue: arXiv cs.IT 2005
Year: 2005

We study a game puzzle that has enjoyed recent popularity among mathematicians, computer scientist, coding theorists and even the mass press. In the game, $n$ players are fitted with randomly assigned colored hats. Individual players can see their teammates' hat colors, but not their own. Based on this information, and without any further communication, each player must attempt to guess his hat color, or pass. The team wins if there is at least one correct guess, and no incorrect ones. The goal is to devise guessing strategies that maximize the team winning probability. We show that for the case of two hat colors, and for any value of $n$, playing strategies are equivalent to binary covering codes of radius one. This link, in particular with Hamming codes, had been observed for values of $n$ of the form $2^m-1$. We extend the analysis to games with hats of $q$ colors, $q\geq 2$, where 1-coverings are not sufficient to characterize the best strategies. Instead, we introduce the more appropriate notion of a {\em strong covering}, and show efficient constructions of these coverings, which achieve winning probabilities approaching unity. Finally, we briefly discuss results on variants of the problem, including arbitrary input distributions, randomized playing strategies, and symmetric strategies.
Interactive Unawareness Revisited
Venue: arXiv cs.AI 2005
Year: 2005

We analyze a model of interactive unawareness introduced by Heifetz, Meier and Schipper (HMS). We consider two axiomatizations for their model, which capture different notions of validity. These axiomatizations allow us to compare the HMS approach to both the standard (S5) epistemic logic and two other approaches to unawareness: that of Fagin and Halpern and that of Modica and Rustichini. We show that the differences between the HMS approach and the others are mainly due to the notion of validity used and the fact that the HMS is based on a 3-valued propositional logic.
A Model-driven Approach for Grid Services Engineering
Venue: arXiv cs.SE 2005
Year: 2005

As a consequence to the hype of Grid computing, such systems have seldom been designed using formal techniques. The complexity and rapidly growing demand around Grid technologies has favour the use of classical development techniques, resulting in no guidelines or rules and unstructured engineering processes. This paper advocates a formal approach to Grid applications development in an effort to contribute to the rigorous development of Grids software architectures. This approach addresses cross-platform interoperability and quality of service; the model-driven paradigm is applied to a formal architecture-centric engineering method in order to benefit from the formal semantic description power in addition to model-based transformations. The result of such a novel combined concept promotes the re-use of design models and eases developments in Grid computing by providing an adapted development process and ensuring correctness at each design step.
A Maple Package for Computing Groebner Bases for Linear Recurrence Relations
Venue: arXiv cs.SC 2005
Year: 2005

A Maple package for computing Groebner bases of linear difference ideals is described. The underlying algorithm is based on Janet and Janet-like monomial divisions associated with finite difference operators. The package can be used, for example, for automatic generation of difference schemes for linear partial differential equations and for reduction of multiloop Feynman integrals. These two possible applications are illustrated by simple examples of the Laplace equation and a one-loop scalar integral of propagator type
CP-nets and Nash equilibria
Venue: arXiv cs.GT 2005
Year: 2005

We relate here two formalisms that are used for different purposes in reasoning about multi-agent systems. One of them are strategic games that are used to capture the idea that agents interact with each other while pursuing their own interest. The other are CP-nets that were introduced to express qualitative and conditional preferences of the users and which aim at facilitating the process of preference elicitation. To relate these two formalisms we introduce a natural, qualitative, extension of the notion of a strategic game. We show then that the optimal outcomes of a CP-net are exactly the Nash equilibria of an appropriately defined strategic game in the above sense. This allows us to use the techniques of game theory to search for optimal outcomes of CP-nets and vice-versa, to use techniques developed for CP-nets to search for Nash equilibria of the considered games.
On the Feedback Capacity of Stationary Gaussian Channels
Venue: arXiv cs.IT 2005
Year: 2005

The capacity of stationary additive Gaussian noise channels with feedback is characterized as the solution to a variational problem. Toward this end, it is proved that the optimal feedback coding scheme is stationary. When specialized to the first-order autoregressive moving-average noise spectrum, this variational characterization yields a closed-form expression for the feedback capacity. In particular, this result shows that the celebrated Schalkwijk--Kailath coding scheme achieves the feedback capacity for the first-order autoregressive moving-average Gaussian channel, resolving a long-standing open problem studied by Butman, Schalkwijk--Tiernan, Wolfowitz, Ozarow, Ordentlich, Yang--Kavcic--Tatikonda, and others.
Capacity and Character Expansions: Moment generating function and other exact results for MIMO correlated channels
Venue: arXiv cs.IT 2005
Year: 2005

We apply a promising new method from the field of representations of Lie groups to calculate integrals over unitary groups, which are important for multi-antenna communications. To demonstrate the power and simplicity of this technique, we first re-derive a number of results that have been used recently in the community of wireless information theory, using only a few simple steps. In particular, we derive the joint probability distribution of eigenvalues of the matrix GG*, with G a semicorrelated Gaussian random matrix or a Gaussian random matrix with a non-zero mean (and G* its hermitian conjugate) . These joint probability distribution functions can then be used to calculate the moment generating function of the mutual information for Gaussian channels with multiple antennas on both ends with this probability distribution of their channel matrices G. We then turn to the previously unsolved problem of calculating the moment generating function of the mutual information of MIMO (multiple input-multiple output) channels, which are correlated at both the receiver and the transmitter. From this moment generating function we obtain the ergodic average of the mutual information and study the outage probability. These methods can be applied to a number of other problems. As a particular example, we examine unitary encoded space-time transmission of MIMO systems and we derive the received signal distribution when the channel matrix is correlated at the transmitter end.
Automatic Face Recognition System Based on Local Fourier-Bessel Features
Venue: arXiv cs.CV 2005
Year: 2005

We present an automatic face verification system inspired by known properties of biological systems. In the proposed algorithm the whole image is converted from the spatial to polar frequency domain by a Fourier-Bessel Transform (FBT). Using the whole image is compared to the case where only face image regions (local analysis) are considered. The resulting representations are embedded in a dissimilarity space, where each image is represented by its distance to all the other images, and a Pseudo-Fisher discriminator is built. Verification test results on the FERET database showed that the local-based algorithm outperforms the global-FBT version. The local-FBT algorithm performed as state-of-the-art methods under different testing conditions, indicating that the proposed system is highly robust for expression, age, and illumination variations. We also evaluated the performance of the proposed system under strong occlusion conditions and found that it is highly robust for up to 50% of face occlusion. Finally, we automated completely the verification system by implementing face and eye detection algorithms. Under this condition, the local approach was only slightly superior to the global approach.
Face Verification in Polar Frequency Domain: a Biologically Motivated Approach
Venue: arXiv cs.CV 2005
Year: 2005

We present a novel local-based face verification system whose components are analogous to those of biological systems. In the proposed system, after global registration and normalization, three eye regions are converted from the spatial to polar frequency domain by a Fourier-Bessel Transform. The resulting representations are embedded in a dissimilarity space, where each image is represented by its distance to all the other images. In this dissimilarity space a Pseudo-Fisher discriminator is built. ROC and equal error rate verification test results on the FERET database showed that the system performed at least as state-of-the-art methods and better than a system based on polar Fourier features. The local-based system is especially robust to facial expression and age variations, but sensitive to registration errors.
Applications of correlation inequalities to low density graphical codes
Venue: arXiv cs.IT 2005
Year: 2005

This contribution is based on the contents of a talk delivered at the Next-SigmaPhi conference held in Crete in August 2005. It is adressed to an audience of physicists with diverse horizons and does not assume any background in communications theory. Capacity approaching error correcting codes for channel communication known as Low Density Parity Check (LDPC) codes have attracted considerable attention from coding theorists in the last decade. Surprisingly strong connections with the theory of diluted spin glasses have been discovered. In this work we elucidate one new connection, namely that a class of correlation inequalities valid for gaussian spin glasses can be applied to the theoretical analysis of LDPC codes. This allows for a rigorous comparison between the so called (optimal) maximum a posteriori and the computationaly efficient belief propagation decoders. The main ideas of the proofs are explained and we refer to recent works for the more lengthy technical details.
The Hunting of the Bump: On Maximizing Statistical Discrepancy
Venue: arXiv cs.CG 2005
Year: 2005

Anomaly detection has important applications in biosurveilance and environmental monitoring. When comparing measured data to data drawn from a baseline distribution, merely, finding clusters in the measured data may not actually represent true anomalies. These clusters may likely be the clusters of the baseline distribution. Hence, a discrepancy function is often used to examine how different measured data is to baseline data within a region. An anomalous region is thus defined to be one with high discrepancy. In this paper, we present algorithms for maximizing statistical discrepancy functions over the space of axis-parallel rectangles. We give provable approximation guarantees, both additive and relative, and our methods apply to any convex discrepancy function. Our algorithms work by connecting statistical discrepancy to combinatorial discrepancy; roughly speaking, we show that in order to maximize a convex discrepancy function over a class of shapes, one needs only maximize a linear discrepancy function over the same set of shapes. We derive general discrepancy functions for data generated from a one- parameter exponential family. This generalizes the widely-used Kulldorff scan statistic for data from a Poisson distribution. We present an algorithm running in $O(\smash[tb]{\frac{1}ε n^2 \log^2 n})$ that computes the maximum discrepancy rectangle to within additive error $ε$, for the Kulldorff scan statistic. Similar results hold for relative error and for discrepancy functions for data coming from Gaussian, Bernoulli, and gamma distributions. Prior to our work, the best known algorithms were exact and ran in time $\smash[t]{O(n^4)}$.
Entropy based Nearest Neighbor Search in High Dimensions
Venue: arXiv cs.DS 2005
Year: 2005

In this paper we study the problem of finding the approximate nearest neighbor of a query point in the high dimensional space, focusing on the Euclidean space. The earlier approaches use locality-preserving hash functions (that tend to map nearby points to the same value) to construct several hash tables to ensure that the query point hashes to the same bucket as its nearest neighbor in at least one table. Our approach is different -- we use one (or a few) hash table and hash several randomly chosen points in the neighborhood of the query point showing that at least one of them will hash to the bucket containing its nearest neighbor. We show that the number of randomly chosen points in the neighborhood of the query point $q$ required depends on the entropy of the hash value $h(p)$ of a random point $p$ at the same distance from $q$ at its nearest neighbor, given $q$ and the locality preserving hash function $h$ chosen randomly from the hash family. Precisely, we show that if the entropy $I(h(p)|q,h) = M$ and $g$ is a bound on the probability that two far-off points will hash to the same bucket, then we can find the approximate nearest neighbor in $O(n^ρ)$ time and near linear $\tilde O(n)$ space where $ρ= M/\log(1/g)$. Alternatively we can build a data structure of size $\tilde O(n^{1/(1-ρ)})$ to answer queries in $\tilde O(d)$ time. By applying this analysis to the locality preserving hash functions in and adjusting the parameters we show that the $c$ nearest neighbor can be computed in time $\tilde O(n^ρ)$ and near linear space where $ρ\approx 2.06/c$ as $c$ becomes large.
A Unified Power Control Algorithm for Multiuser Detectors in Large Systems: Convergence and Performance
Venue: arXiv cs.IT 2005
Year: 2005

A unified approach to energy-efficient power control, applicable to a large family of receivers including the matched filter, the decorrelator, the (linear) minimum-mean-square-error detector (MMSE), and the individually and jointly optimal multiuser detectors, has recently been proposed for code-division-multiple-access (CDMA) networks. This unified power control (UPC) algorithm exploits the linear relationship that has been shown to exist between the transmit power and the output signal-to-interference-plus-noise ratio (SIR) in large systems. Based on this principle and by computing the multiuser efficiency, the UPC algorithm updates the users' transmit powers in an iterative way to achieve the desired target SIR. In this paper, the convergence of the UPC algorithm is proved for the matched filter, the decorrelator, and the MMSE detector. In addition, the performance of the algorithm in finite-size systems is studied and compared with that of existing power control schemes. The UPC algorithm is particularly suitable for systems with randomly generated long spreading sequences (i.e., sequences whose period is longer than one symbol duration).
Cryptographic Authentication of Navigation Protocols
Venue: arXiv cs.CR 2005
Year: 2005

We examine the security of existing radio navigation protocols and attempt to define secure, scalable replacements.
Practical Semantic Analysis of Web Sites and Documents
Venue: arXiv cs.IR 2005
Year: 2005

As Web sites are now ordinary products, it is necessary to explicit the notion of quality of a Web site. The quality of a site may be linked to the easiness of accessibility and also to other criteria such as the fact that the site is up to date and coherent. This last quality is difficult to insure because sites may be updated very frequently, may have many authors, may be partially generated and in this context proof-reading is very difficult. The same piece of information may be found in different occurrences, but also in data or meta-data, leading to the need for consistency checking. In this paper we make a parallel between programs and Web sites. We present some examples of semantic constraints that one would like to specify (constraints between the meaning of categories and sub-categories in a thematic directory, consistency between the organization chart and the rest of the site in an academic site). We present quickly the Natural Semantics, a way to specify the semantics of programming languages that inspires our works. Then we propose a specification language for semantic constraints in Web sites that, in conjunction with the well known ``make'' program, permits to generate some site verification tools by compiling the specification into Prolog code. We apply our method to a large XML document which is the scientific part of our institute activity report, tracking errors or inconsistencies and also constructing some indicators that can be used by the management of the institute.
Polar Polytopes and Recovery of Sparse Representations
Venue: arXiv cs.IT 2005
Year: 2005

Suppose we have a signal y which we wish to represent using a linear combination of a number of basis atoms a_i, y=sum_i x_i a_i = Ax. The problem of finding the minimum L0 norm representation for y is a hard problem. The Basis Pursuit (BP) approach proposes to find the minimum L1 norm representation instead, which corresponds to a linear program (LP) that can be solved using modern LP techniques, and several recent authors have given conditions for the BP (minimum L1 norm) and sparse (minimum L0 solutions) representations to be identical. In this paper, we explore this sparse representation problem} using the geometry of convex polytopes, as recently introduced into the field by Donoho. By considering the dual LP we find that the so-called polar polytope P of the centrally-symmetric polytope P whose vertices are the atom pairs +-a_i is particularly helpful in providing us with geometrical insight into optimality conditions given by Fuchs and Tropp for non-unit-norm atom sets. In exploring this geometry we are able to tighten some of these earlier results, showing for example that the Fuchs condition is both necessary and sufficient for L1-unique-optimality, and that there are situations where Orthogonal Matching Pursuit (OMP) can eventually find all L1-unique-optimal solutions with m nonzeros even if ERC fails for m, if allowed to run for more than m steps.
Design and Performance Analysis of a New Class of Rate Compatible Serial Concatenated Convolutional Codes
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we provide a performance analysis of a new class of serial concatenated convolutional codes (SCCC) where the inner encoder can be punctured beyond the unitary rate. The puncturing of the inner encoder is not limited to inner coded bits, but extended to systematic bits. Moreover, it is split into two different puncturings, in correspondence with inner code systematic bits and parity bits. We derive the analytical upper bounds to the error probability of this particular code structure and address suitable design guidelines for the inner code puncturing patterns. We show that the percentile of systematic and parity bits to be deleted strongly depends on the SNR region of interest. In particular, to lower the error floor it is advantageous to put more puncturing on inner systematic bits. Furthermore, we show that puncturing of inner systematic bits should be interleaver dependent. Based on these considerations, we derive design guidelines to obtain well-performing rate-compatible SCCC families. Throughout the paper, the performance of the proposed codes are compared with analytical bounds, and with the performance of PCCC and SCCC proposed in the literature.
Hiérarchisation des règles d'association en fouille de textes
Venue: arXiv cs.IR 2005
Year: 2005

Extraction of association rules is widely used as a data mining method. However, one of the limit of this approach comes from the large number of extracted rules and the difficulty for a human expert to deal with the totality of these rules. We propose to solve this problem by structuring the set of rules into hierarchy. The expert can then therefore explore the rules, access from one rule to another one more general when we raise up in the hierarchy, and in other hand, or a more specific rules. Rules are structured at two levels. The global level aims at building a hierarchy from the set of rules extracted. Thus we define a first type of rule-subsomption relying on Galois lattices. The second level consists in a local and more detailed analysis of each rule. It generate for a given rule a set of generalization rules structured into a local hierarchy. This leads to the definition of a second type of subsomption. This subsomption comes from inductive logic programming and integrates a terminological model.
On Minimal Pseudo-Codewords of Tanner Graphs from Projective Planes
Venue: arXiv cs.IT 2005
Year: 2005

We would like to better understand the fundamental cone of Tanner graphs derived from finite projective planes. Towards this goal, we discuss bounds on the AWGNC and BSC pseudo-weight of minimal pseudo-codewords of such Tanner graphs, on one hand, and study the structure of minimal pseudo-codewords, on the other.