OpenRaiser/Intern-Atlas huggingface dataset:
Rectangular Full Packed Format for Cholesky's Algorithm: Factorization, Solution and Inversion
Venue: arXiv cs.MS 2009
Year: 2009

We describe a new data format for storing triangular, symmetric, and Hermitian matrices called RFPF (Rectangular Full Packed Format). The standard two dimensional arrays of Fortran and C (also known as full format) that are used to represent triangular and symmetric matrices waste nearly half of the storage space but provide high performance via the use of Level 3 BLAS. Standard packed format arrays fully utilize storage (array space) but provide low performance as there is no Level 3 packed BLAS. We combine the good features of packed and full storage using RFPF to obtain high performance via using Level 3 BLAS as RFPF is a standard full format representation. Also, RFPF requires exactly the same minimal storage as packed format. Each LAPACK full and/or packed triangular, symmetric, and Hermitian routine becomes a single new RFPF routine based on eight possible data layouts of RFPF. This new RFPF routine usually consists of two calls to the corresponding LAPACK full format routine and two calls to Level 3 BLAS routines. This means {\it no} new software is required. As examples, we present LAPACK routines for Cholesky factorization, Cholesky solution and Cholesky inverse computation in RFPF to illustrate this new work and to describe its performance on several commonly used computer platforms. Performance of LAPACK full routines using RFPF versus LAPACK full routines using standard format for both serial and SMP parallel processing is about the same while using half the storage. Performance gains are roughly one to a factor of 43 for serial and one to a factor of 97 for SMP parallel times faster using vendor LAPACK full routines with RFPF than with using vendor and/or reference packed routines.
Power Adaptive Feedback Communication over an Additive Individual Noise Sequence Channel
Venue: arXiv cs.IT 2009
Year: 2009

We consider a real-valued additive channel with an individual unknown noise sequence. We present a simple sequential communication scheme based on the celebrated Schalkwijk-Kailath scheme, which varies the transmit power according to the power of the sequence, so that asymptotically the relation between the SNR and the rate matches the Gaussian channel capacity 1/2 log(1+SNR)for almost every noise sequence.
How to improve the accuracy of the discrete gradient method in the one-dimensional case
Venue: arXiv cs.NA 2009
Year: 2009

We present a new numerical scheme for one dimensional dynamical systems. This is a modification of the discrete gradient method and keeps its advantages, including the stability and the conservation of the energy integral. However, its accuracy is higher by several orders of magnitude.
Average Capacity Analysis of Continuous-Time Frequency-Selective Rayleigh Fading Channels with Correlated Scattering Using Majorization
Venue: arXiv cs.IT 2009
Year: 2009

Correlated scattering occurs naturally in frequency-selective fading channels and its impact on the performance needs to be understood. In particular, we answer the question whether the uncorrelated scattering model leads to an optimistic or pessimistic estimation of the actual average capacity. In the paper, we use majorization for functions to show that the average rate with perfectly informed receiver is largest for uncorrelated scattering if the transmitter is uninformed. If the transmitter knows the channel statistics, it can exploit this knowledge. We show that for small SNR, the behavior is opposite, uncorrelated scattering leads to a lower bound on the average capacity. Finally, we provide an example of the theoretical results for an attenuated Ornstein-Uhlenbeck process including illustrations.
Two-Bit Message Passing Decoders for LDPC Codes Over the Binary Symmetric Channel
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider quantized decoding of LDPC codes on the binary symmetric channel. The binary message passing algorithms, while allowing extremely fast hardware implementation, are not very attractive from the perspective of performance. More complex decoders such as the ones based on belief propagation exhibit superior performance but lead to slower decoders. The approach in this paper is to consider message passing decoders that have larger message alphabet (thereby providing performance improvement) as well as low complexity (thereby ensuring fast decoding). We propose a class of message-passing decoders whose messages are represented by two bits. The thresholds for various decoders in this class are derived using density evolution. The problem of correcting a fixed number of errors assumes significance in the error floor region. For a specific decoder, the sufficient conditions for correcting all patterns with up to three errors are derived. By comparing these conditions and thresholds to the similar ones when Gallager B decoder is used, we emphasize the advantage of decoding on a higher number of bits, even if the channel observation is still one bit.
On Optimal Secure Message Transmission by Public Discussion
Venue: arXiv cs.CR 2009
Year: 2009

In a secure message transmission (SMT) scenario a sender wants to send a message in a private and reliable way to a receiver. Sender and receiver are connected by $n$ vertex disjoint paths, referred to as wires, $t$ of which can be controlled by an adaptive adversary with unlimited computational resources. In Eurocrypt 2008, Garay and Ostrovsky considered an SMT scenario where sender and receiver have access to a public discussion channel and showed that secure and reliable communication is possible when $n \geq t+1$. In this paper we will show that a secure protocol requires at least 3 rounds of communication and 2 rounds invocation of the public channel and hence give a complete answer to the open question raised by Garay and Ostrovsky. We also describe a round optimal protocol that has \emph{constant} transmission rate over the public channel.
Finite-Length Analysis of Irregular Expurgated LDPC Codes under Finite Number of Iterations
Venue: arXiv cs.IT 2009
Year: 2009

Communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding is considered. The average bit error probability of an irregular LDPC code ensemble after a fixed number of iterations converges to a limit, which is calculated via density evolution, as the blocklength $n$ tends to infinity. The difference between the bit error probability with blocklength $n$ and the large-blocklength limit behaves asymptotically like $α/n$, where the coefficient $α$ depends on the ensemble, the number of iterations and the erasure probability of the BEC\null. In [1], $α$ is calculated for regular ensembles. In this paper, $α$ for irregular expurgated ensembles is derived. It is demonstrated that convergence of numerical estimates of $α$ to the analytic result is significantly fast for irregular unexpurgated ensembles.
A Plotkin-Alamouti Superposition Coding Scheme for Cooperative Broadcasting in Wireless Networks
Venue: arXiv cs.IT 2009
Year: 2009

This paper deals with superposition coding for cooperative broadcasting in the case of two coordinated source nodes, as introduced in the seminal work of Bergmans and Cover in 1974. A scheme is introduced for two classes of destination (or relay) nodes: Close nodes and far nodes, as ranked by their spatial distances to the pair of transmitting nodes. Two linear codes are combined using the (u,u+v)-construction devised by Plotkin to construct two-level linear unequal error protection (LUEP) codes. However, instead of binary addition of subcode codewords in the source encoder, here modulated subcode sequences are combined at the destination (or relay) nodes antennae. Bergmans and Cover referred to this as over-the-air mixing. In the case of Rayleigh fading, additional diversity order as well as robustness to channel estimation errors are obtained when source nodes transmit pairs of coded sequences in accordance to Alamouti's transmit diversity scheme. We refer to this combination as a Plotkin-Alamouti scheme and study its performance over AWGN and Rayleigh fading channels with a properly partitioned QPSK constellation.
An e-Infrastructure for Collaborative Research in Human Embryo Development
Venue: arXiv cs.DC 2009
Year: 2009

Within the context of the EU Design Study Developmental Gene Expression Map, we identify a set of challenges when facilitating collaborative research on early human embryo development. These challenges bring forth requirements, for which we have identified solutions and technology. We summarise our solutions and demonstrate how they integrate to form an e-infrastructure to support collaborative research in this area of developmental biology.
Information-Theoretic Bounds for Multiround Function Computation in Collocated Networks
Venue: arXiv cs.IT 2009
Year: 2009

We study the limits of communication efficiency for function computation in collocated networks within the framework of multi-terminal block source coding theory. With the goal of computing a desired function of sources at a sink, nodes interact with each other through a sequence of error-free, network-wide broadcasts of finite-rate messages. For any function of independent sources, we derive a computable characterization of the set of all feasible message coding rates - the rate region - in terms of single-letter information measures. We show that when computing symmetric functions of binary sources, the sink will inevitably learn certain additional information which is not demanded in computing the function. This conceptual understanding leads to new improved bounds for the minimum sum-rate. The new bounds are shown to be orderwise better than those based on cut-sets as the network scales. The scaling law of the minimum sum-rate is explored for different classes of symmetric functions and source parameters.
Weight Distribution of A p-ary Cyclic Code
Venue: arXiv cs.IT 2009
Year: 2009

For an odd prime $p$ and two positive integers $n\geq 3$ and $k$ with $\frac{n}{{\rm gcd}(n,k)}$ being odd, the paper determines the weight distribution of a $p$-ary cyclic code $\mathcal{C}$ over $\mathbb{F}_{p}$ with nonzeros $α^{-1}$, $α^{-(p^k+1)}$ and $α^{-(p^{3k}+1)}$, where $α$ is a primitive element of $\mathbb{F}_{p^n}$
On integral probability metrics, ϕ-divergences and binary classification
Venue: arXiv cs.IT 2009
Year: 2009

A class of distance measures on probabilities -- the integral probability metrics (IPMs) -- is addressed: these include the Wasserstein distance, Dudley metric, and Maximum Mean Discrepancy. IPMs have thus far mostly been used in more abstract settings, for instance as theoretical tools in mass transportation problems, and in metrizing the weak topology on the set of all Borel probability measures defined on a metric space. Practical applications of IPMs are less common, with some exceptions in the kernel machines literature. The present work contributes a number of novel properties of IPMs, which should contribute to making IPMs more widely used in practice, for instance in areas where $ϕ$-divergences are currently popular. First, to understand the relation between IPMs and $ϕ$-divergences, the necessary and sufficient conditions under which these classes intersect are derived: the total variation distance is shown to be the only non-trivial $ϕ$-divergence that is also an IPM. This shows that IPMs are essentially different from $ϕ$-divergences. Second, empirical estimates of several IPMs from finite i.i.d. samples are obtained, and their consistency and convergence rates are analyzed. These estimators are shown to be easily computable, with better rates of convergence than estimators of $ϕ$-divergences. Third, a novel interpretation is provided for IPMs by relating them to binary classification, where it is shown that the IPM between class-conditional distributions is the negative of the optimal risk associated with a binary classifier. In addition, the smoothness of an appropriate binary classifier is proved to be inversely related to the distance between the class-conditional distributions, measured in terms of an IPM.
Information science and technology as applications of the physics of signalling
Venue: arXiv cs.OH 2009
Year: 2009

Adopting the scientific method a theoretical model is proposed as foundation for information science and technology, extending the existing theory of signaling: a fact f becomes known in a physical system only following the success of a test f, tests performed primarily by human sensors and applied to (physical) phenomena within which further tests may be performed. Tests are phenomena and classify phenomena. A phenomenon occupies both time and space, facts and inferences having physical counterparts which are phenomena of specified classes. Identifiers such as f are conventional, assigned by humans; a fact (f', f'') reports the success of a test of generic class f', the outcome f'' of the reported application classifying the successful test in more detail. Facts then exist only within structures of a form dictated by constraints on the structural design of tests. The model explains why responses of real time systems are not uniquely predictable and why restrictions, on concurrency in performing inferences within them, are needed. Improved methods, based on the model and applicable throughout the software life-cycle, are summarised in the paper. No report of similar work has been found in the literature.
Pyro-Align: Sample-Align based Multiple Alignment system for Pyrosequencing Reads of Large Number
Venue: arXiv cs.DS 2009
Year: 2009

Pyro-Align is a multiple alignment program specifically designed for pyrosequencing reads of huge number. Multiple sequence alignment is shown to be NP-hard and heuristics are designed for approximate solutions. Multiple sequence alignment of pyrosequenceing reads is complex mainly because of 2 factors. One being the huge number of reads, making the use of traditional heuristics,that scale very poorly for large number, unsuitable. The second reason is that the alignment cannot be performed arbitrarily, because the position of the reads with respect to the original genome is important and has to be taken into account.In this report we present a short description of the multiple alignment system for pyrosequencing reads.
FRFD MIMO Systems: Precoded V-BLAST with Limited Feedback Versus Non-orthogonal STBC MIMO
Venue: arXiv cs.IT 2009
Year: 2009

Full-rate (FR) and full-diversity (FD) are attractive features in MIMO systems. We refer to systems which achieve both FR and FD simultaneously as FRFD systems. Non-orthogonal STBCs can achieve FRFD without feedback, but their ML decoding complexities are high. V-BLAST without precoding achieves FR but not FD. FRFD can be achieved in V-BLAST through precoding given full channel state information at the transmitter (CSIT). However, with limited feedback precoding, V-BLAST achieves FD, but with some rate loss. Our contribution in this paper is two-fold: $i)$ we propose a limited feedback (LFB) precoding scheme which achieves FRFD in $2\times 2$, $3\times 3$ and $4\times 4$ V-BLAST systems (we refer to this scheme as FRFD-VBLAST-LFB scheme), and $ii)$ comparing the performances of the FRFD-VBLAST-LFB scheme and non-orthogonal STBCs without feedback (e.g., Golden code, perfect codes) under ML decoding, we show that in $2\times 2$ MIMO system with 4-QAM/16-QAM, FRFD-VBLAST-LFB scheme outperforms the Golden code by about 0.6 dB; in $3\times 3$ and $4\times 4$ MIMO systems, the performance of FRFD-VBLAST-LFB scheme is comparable to the performance of perfect codes. The FRFD-VBLAST-LFB scheme is attractive because 1) ML decoding becomes less complex compared to that of non-orthogonal STBCs, 2) the number of feedback bits required to achieve the above performance is small, 3) in slow-fading, it is adequate to send feedback bits only occasionally, and 4) in most practical wireless systems feedback channel is often available (e.g., for adaptive modulation, rate/power control).
On finitely recursive programs
Venue: arXiv cs.AI 2009
Year: 2009

Disjunctive finitary programs are a class of logic programs admitting function symbols and hence infinite domains. They have very good computational properties, for example ground queries are decidable while in the general case the stable model semantics is highly undecidable. In this paper we prove that a larger class of programs, called finitely recursive programs, preserves most of the good properties of finitary programs under the stable model semantics, namely: (i) finitely recursive programs enjoy a compactness property; (ii) inconsistency checking and skeptical reasoning are semidecidable; (iii) skeptical resolution is complete for normal finitely recursive programs. Moreover, we show how to check inconsistency and answer skeptical queries using finite subsets of the ground program instantiation. We achieve this by extending the splitting sequence theorem by Lifschitz and Turner: We prove that if the input program P is finitely recursive, then the partial stable models determined by any smooth splitting omega-sequence converge to a stable model of P.
Weighted $\ell_1$ Minimization for Sparse Recovery with Prior Information
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we study the compressed sensing problem of recovering a sparse signal from a system of underdetermined linear equations when we have prior information about the probability of each entry of the unknown signal being nonzero. In particular, we focus on a model where the entries of the unknown vector fall into two sets, each with a different probability of being nonzero. We propose a weighted $\ell_1$ minimization recovery algorithm and analyze its performance using a Grassman angle approach. We compute explicitly the relationship between the system parameters (the weights, the number of measurements, the size of the two sets, the probabilities of being non-zero) so that an iid random Gaussian measurement matrix along with weighted $\ell_1$ minimization recovers almost all such sparse signals with overwhelming probability as the problem dimension increases. This allows us to compute the optimal weights. We also provide simulations to demonstrate the advantages of the method over conventional $\ell_1$ optimization.
Approaching the linguistic complexity
Venue: arXiv cs.CL 2009
Year: 2009

We analyze the rank-frequency distributions of words in selected English and Polish texts. We compare scaling properties of these distributions in both languages. We also study a few small corpora of Polish literary texts and find that for a corpus consisting of texts written by different authors the basic scaling regime is broken more strongly than in the case of comparable corpus consisting of texts written by the same author. Similarly, for a corpus consisting of texts translated into Polish from other languages the scaling regime is broken more strongly than for a comparable corpus of native Polish texts. Moreover, based on the British National Corpus, we consider the rank-frequency distributions of the grammatically basic forms of words (lemmas) tagged with their proper part of speech. We find that these distributions do not scale if each part of speech is analyzed separately. The only part of speech that independently develops a trace of scaling is verbs.
Feedback Capacity of the Gaussian Interference Channel to Within 1.7075 Bits: the Symmetric Case
Venue: arXiv cs.IT 2009
Year: 2009

We characterize the symmetric capacity to within 1.7075 bits/s/Hz for the two-user Gaussian interference channel with feedback. The result makes use of a deterministic model to provide insights into the Gaussian channel. We derive a new outer bound to show that a proposed achievable scheme can achieve the symmetric capacity to within 1.7075 bits for all channel parameters. From this result, we show that feedback provides unbounded gain, i.e., the gain becomes arbitrarily large for certain channel parameters. It is a surprising result because feedback has been so far known to provide only power gain (bounded gain) in the context of multiple access channels and broadcast channels.
Joint source-channel with side information coding error exponents
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we study the upper and the lower bounds on the joint source-channel coding error exponent with decoder side-information. The results in the paper are non-trivial extensions of the Csiszar's classical paper [5]. Unlike the joint source-channel coding result in [5], it is not obvious whether the lower bound and the upper bound are equivalent even if the channel coding error exponent is known. For a class of channels, including the symmetric channels, we apply a game-theoretic result to establish the existence of a saddle point and hence prove that the lower and upper bounds are the same if the channel coding error exponent is known. More interestingly, we show that encoder side-information does not increase the error exponents in this case.
A Constructive Generalization of Nash Equilibrium
Venue: arXiv cs.GT 2009
Year: 2009

In a society of multiple individuals, if everybody is only interested in maximizing his own payoff, will there exist any equilibrium for the society? John Nash proved more than 50 years ago that an equilibrium always exists such that nobody would benefit from unilaterally changing his strategy. Nash Equilibrium is a central concept in game theory, which offers the mathematical foundation for social science and economy. However, the original definition is declarative without including a solution to find them. It has been found later that it is computationally difficult to find a Nash equilibrium. Furthermore, a Nash equilibrium may be unstable, sensitive to the smallest variation of payoff functions. Making the situation worse, a society with selfish individuals can have an enormous number of equilibria, making it extremely hard to find out the global optimal one. This paper offers a constructive generalization of Nash equilibrium to cover the case when the selfishness of individuals are reduced to lower levels in a controllable way. It shows that the society has one and only one equilibrium when the selfishness is reduced to a certain level. When every individual follows the iterative, soft-decision optimization process presented in this paper, the society converges to the unique equilibrium with an exponential rate under any initial conditions. When it is a consensus equilibrium at the same time, it must be the global optimum. The study of this paper suggests that, to build a good, stable society (including the financial market) for the benefit everyone in it, the pursuing of maximal payoff by each individual should be controlled at some level either by voluntary good citizenship or some proper regulations.
Deceptiveness and Neutrality - the ND family of fitness landscapes
Venue: arXiv cs.AI 2009
Year: 2009

When a considerable number of mutations have no effects on fitness values, the fitness landscape is said neutral. In order to study the interplay between neutrality, which exists in many real-world applications, and performances of metaheuristics, it is useful to design landscapes which make it possible to tune precisely neutral degree distribution. Even though many neutral landscape models have already been designed, none of them are general enough to create landscapes with specific neutral degree distributions. We propose three steps to design such landscapes: first using an algorithm we construct a landscape whose distribution roughly fits the target one, then we use a simulated annealing heuristic to bring closer the two distributions and finally we affect fitness values to each neutral network. Then using this new family of fitness landscapes we are able to highlight the interplay between deceptiveness and neutrality.