Eigenvectors of data matrices play an important role in many computational problems, ranging from signal processing to machine learning and control. For instance, algorithms that compute positions of the nodes of a wireless network on the basis of pairwise distance measurements require a few leading eigenvectors of the distances matrix. While eigenvector calculation is a standard topic in numerical linear algebra, it becomes challenging under severe communication or computation constraints, or in absence of central scheduling. In this paper we investigate the possibility of computing the leading eigenvectors of a large data matrix through gossip algorithms.

We use a generalization of the Lindeberg principle developed by S. Chatterjee to prove universality properties for various problems in communications, statistical learning and random matrix theory. We also show that these systems can be viewed as the limiting case of a properly defined sparse system. The latter result is useful when the sparse systems are easier to analyze than their dense counterparts. The list of problems we consider is by no means exhaustive. We believe that the ideas can be used in many other problems relevant for information theory.

We consider communication over binary-input memoryless output-symmetric channels using low-density parity-check codes and message-passing decoding. The asymptotic (in the length) performance of such a combination for a fixed number of iterations is given by density evolution. Letting the number of iterations tend to infinity we get the density evolution (DE) threshold, the largest channel parameter so that the bit error probability tends to zero as a function of the iterations. In practice, we often work with short codes and perform a large number of iterations. It is, therefore, interesting to consider what happens if in the standard analysis we exchange the order in which the blocklength and the number of iterations diverge to infinity. In particular, we can ask whether both limits give the same threshold. Although empirical observations strongly suggest that the exchange of limits is valid for all channel parameters, we limit our discussion to channel parameters below the DE threshold. Specifically, we show that as long as the message reliabilities are bounded and other technical conditions are met, the bit error probability vanishes up to a nontrivial threshold regardless of how the limit is taken. This threshold is equal to the DE threshold when the minimum degree of the variable nodes is at least five and strictly less than the DE threshold for smaller degrees.

We present inner bounds to the broadcast capacity region of two classes of information networks: Networks of Multiple Access Channels (MACs) and Networks of Deterministic Broadcast Channels (DBCs). Our achievability scheme is a separation based scheme consisting of a physical layer that involves “cleaning up” the constituent channels in the network to create a point-to-point wired overlay, and a network layer that involves routing over this wired overlay. It is shown that finding the optimal way to “clean-up” is equivalent to the problem of finding maximal flows in “polymatroidal” flow networks, an already solved problem. The resulting inner bounds are cut-set bounds evaluated over product input distributions and are tight for Networks of DBCs.

In this paper lossless compression with polar codes is considered. A polar encoding algorithm is developed and a method to design the code and compute the average compression rate for finite lengths is given. It is shown that the scheme achieves the optimal compression rate asymptotically. Furthermore, the proposed scheme has a very good performance at finite lengths. Both the encoding and decoding operations can be accomplished with complexity O(N log N) where N denotes the length of the code.

Using scaling laws, we obtain estimates of the block error probability of polar codes under successive cancellation decoding. For the binary erasure channel we present an upper and a lower bound for the scaling parameter. Numerically these two bounds match. We also present a scaling law for general binary discrete memoryless channels.

Polar codes are the first codes to provably achieve capacity on the symmetric binary-input discrete memoryless channel (B-DMC) with low encoding and decoding complexity. The parity check matrix of polar codes is high-density and we show that linear program (LP) decoding fails on the fundamental polytope of the parity check matrix. The recursive structure of the code permits a sparse factor graph representation. We define a new polytope based on the fundamental polytope of the sparse graph representation. This new polytope P is defined in a space of dimension O(N logN) where N is the block length. We prove that the projection of P in the original space is tighter than the fundamental polytope based on the parity check matrix. The LP decoder over P obtains the ML-certificate property. In the case of the binary erasure channel (BEC), the new LP decoder is equivalent to the belief propagation (BP) decoder operating on the sparse factor graph representation, and hence achieves capacity. Simulation results of SC (successive cancellation) decoding, LP decoding over tightened polytopes, and (ML) maximum likelihood decoding are provided. For channels other than the BEC, we discuss why LP decoding over P with a linear objective function is insufficient.

In this paper, we consider code-division multiple-access (CDMA) communication over a binary input additive white Gaussian noise (AWGN) channel using random spreading. For a general class of symmetric distributions for spreading sequences, in the limit of a large number of users, we prove an upper bound to the capacity. The bound matches the formula obtained by Tanaka using the replica method. We also show concentration of various relevant quantities including mutual information and free energy. The mathematical methods are quite general and allow us to discuss extensions to other multiuser scenarios.

Polar codes were recently introduced by Arikan. They achieve the symmetric capacity of arbitrary binary-input discrete memoryless channels under a low complexity successive cancellation decoding scheme. The original polar code construction is closely related to the recursive construction of Reed-Muller codes and is based on the 2 × 2 matrix [1 0 : 1 1]. It was shown by Arikan Telatar that this construction achieves an error exponent of 1/2, i.e., that for sufficiently large blocklengths the error probability decays exponentially in the square root of the blocklength. It was already mentioned by Arikan that in principle larger matrices can be used to construct polar codes. In this paper, it is first shown that any ℓ × ℓ matrix none of whose column permutations is upper triangular polarizes binary-input memoryless channels. The exponent of a given square matrix is characterized, upper and lower bounds on achievable exponents are given. Using these bounds it is shown that there are no matrices of size smaller than 15×15 with exponents exceeding 1/2. Further, a general construction based on BCH codes which for large I achieves exponents arbitrarily close to 1 is given. At size 16 × 16, this construction yields an exponent greater than 1/2.

We consider lossy source compression of a binary symmetric source using polar codes and a low-complexity successive encoding algorithm. It was recently shown by Arikan that polar codes achieve the capacity of arbitrary symmetric binary-input discrete memoryless channels under a successive decoding strategy. We show the equivalent result for lossy source compression, i.e., we show that this combination achieves the rate-distortion bound for a binary symmetric source. We further show the optimality of polar codes for various multiterminal problems including the binary Wyner-Ziv and the binary Gelfand-Pinsker problems. Our results extend to general versions of these problems.

Polar codes, introduced recently by Arikan, are the first family of codes known to achieve capacity of symmetric channels using a low complexity successive cancellation decoder. Although these codes, combined with successive cancellation, are optimal in this respect, their finite-length performance is not record breaking. We discuss several techniques through which their finite-length performance can be improved. We also study the performance of these codes in the context of source coding, both lossless and lossy, in the single-user context as well as for distributed applications.

A generalization of Arıkan's polar code construction using transformations of the form G⊗nwhere G is an ℓ × ℓ matrix is considered. Necessary and sufficient conditions are given for these transformations to ensure channel polarization. It is shown that a large class of such transformations polarize binary-input memoryless channels.

Polar codes were recently introduced by Arıkan. They achieve the symmetric capacity of arbitrary binary-input discrete memoryless channels under a low complexity successive cancellation decoding strategy. The original polar code construction is closely related to the recursive construction of Reed-Muller codes and is based on the 2 × 2 matrix of the given equation. It was shown by Arıkan and Telatar that this construction achieves an error exponent of 1/2, i.e., that for sufficiently large blocklengths the error probability decays exponentially in the square root of the length. It was already mentioned by Arıkan that in principle larger matrices can be used to construct polar codes. A fundamental question then is to see whether there exist matrices with exponent exceeding 1/2. We characterize the exponent of a given square matrix and derive upper and lower bounds on achievable exponents. Using these bounds we show that there are no matrices of size less than 15 with exponents exceeding 1/2. Further, we give a general construction based on BCH codes which for large matrix sizes achieves exponents arbitrarily close to 1 and which exceeds 1/2 for size 16.

We consider communication over the binary erasure and the binary additive white gaussian noise channels using fixed linear block codes and also appropriate ensembles of such codes. We show concentration of the magnetization over the channel realizations and also over the code ensembles. The result has various implications. For the binary erasure channel, the result implies the concentration of the fraction of bits in error over the randomness in both noise and code realization, and that of the bit error probability under MAP decoding over the code ensemble. For both channels it implies concentration of the generalized EXIT function over code ensembles. Finally our results partly show that there is no replica symmetry breaking.

We consider communication over a family of binary-input memoryless output-symmetric channels using low-density parity-check codes under message passing decoding. The asymptotic (in the length) performance of such a combination for a fixed number of iterations is given by density evolution. It is customary to define the threshold of density evolution as the maximum channel parameter for which the bit error probability under density evolution converges to zero as a function of the iteration number. In practice we often work with short codes and perform a large number of iterations. It is therefore interesting to consider what happens if in the standard analysis we exchange the order in which the blocklength and the number of iterations diverge to infinity. In particular, we can ask whether both limits give the same threshold. Although empirical observations strongly suggest that the exchange of limits is valid for all channel parameters, we limit our discussion to channel parameters below the density evolution threshold. Specifically, we show that under some suitable technical conditions the bit error probability vanishes below the density evolution threshold regardless of how the limit is taken.

We consider source coding over Aref networks. In particular we consider the following two problems: (i) multicasting correlated sources to a set of receivers, (ii) broadcasting sources to their respective receivers. For the first problem we show necessary and sufficient conditions for reliable multicast. For the second problem we show sufficient conditions for reliable broadcast. We further show that these conditions are also necessary when the sources are independent.

We consider communication over a binary erasure channel with low density parity check codes and optimal maximum a posteriori decoding. It is known that the problem of computing the average conditional entropy, over such code ensembles, in the asymptotic limit of large block length is closely related to computing the free energy of a mean field spin glass in the thermodynamic limit. Tentative, but explicit, formulas for these quantities have been derived thanks to the replica method (of spin glass theory) and are generally conjectured to be exact. In this contribution we show that the replica formulas are indeed exact in the case of Poissonian low density parity check ensembles. Our methods use ideas coming from the recent progress in the rigorous analysis of the Sherrington-Kirkpatrick model and their applications to the theory of error correcting codes.

We prove the concentration of the capacity, in the large system limit, for a code division multiple access system over an additive white Gaussian noise channel, with Gaussian signature sequences and binary input symbols. The probabilistic tools that are used are quite powerful and could have applications in many other similar situations.

An important quantity in the analysis of MAP decoding for LDPC codes is the conditional entropy of the input given the output. There exist conjectured formulas for this entropy derived from the replica technique and one sided bounds derived with the help of the interpolation method. In this paper we compute exactly such a quantity for a simpler spin model which retains the essential features of the communications problem. The result is a step towards a proof of the conjectured replica formula for the conditional entropy under MAP decoding

Accurate, reliable timestamping which is also convenient and inexpensive is needed in many important areas including real-time network applications and network measurement.Recently the TSC register, which counts CPU cycles in popular PC architectures, was proposed as the basis of a new software clock which in terms of rate performance performs as well as more expensive GPS alternatives.Smooth and precise clock rate is essential to measure time differences accurately.We show how to define a TSC based clock which is also accurate with respect to absolute time.The clock is calibrated by processing, in a novel way, timestamps contained in the usual flow of Network Time Protocol (NTP) packets between a NTP server and the existing software clock, and TSC timestamps made independently on the host side.Using real measurements over 4 months, validated with a GPS synchronized hardware timing solution, the algorithm measured absolute time with a median error of only 30 microseconds when using a nearby stratum-1 NTP server.Results for two other servers are given.We also provide new algorithms for the robust determination of clock rate.We exploit the reliability of the available hardware to design synchronization algorithms which are inherently robust to many factors including packet loss, server outages, route changes, temperature environment, and network congestion.