We present a class of diffusion-based algorithms to draw samples from high-dimensional probability distributions given their unnormalized densities. Ideally, our methods can transport samples from a Gaussian distribution to a specified target distribution in finite time. Our approach relies on the stochastic interpolants framework to define a time-indexed collection of probability densities that bridge a Gaussian distribution to the target distribution. Subsequently, we derive a diffusion process that obeys the aforementioned probability density at each time instant. Obtaining such a diffusion process involves solving certain Hamilton-Jacobi-Bellman PDEs. We solve these PDEs using the theory of forward-backward stochastic differential equations (FBSDE) together with machine learning-based methods. Through numerical experiments, we demonstrate that our algorithm can effectively draw samples from distributions that conventional methods struggle to handle.

We analyze the time reversed dynamics of generative diffusion models. If the exact empirical score function is used in a regime of large dimension and exponentially large number of samples, these models are known to undergo transitions between distinct dynamical regimes. We extend this analysis and compute the transitions for an analytically tractable manifold model where the statistical model for the data is a mixture of lower dimensional Gaussians embedded in higher dimensional space. We compute the so-called speciation and collapse transition times, as a function of the ratio of manifold-to-ambient space dimensions, and other characteristics of the data model. An important tool used in our analysis is the exact formula for the mutual information (or free energy) of Generalized Linear Models.

We investigate the test risk of a continuous time stochastic gradient flow dynamics in learning theory. Using a path integral formulation we provide, in the regime of small learning rate, a general formula for computing the difference between test risk curves of pure gradient and stochastic gradient flows. We apply the general theory to a simple model of weak features, which displays the double descent phenomenon, and explicitly compute the corrections brought about by the added stochastic term in the dynamics, as a function of time and model parameters. The analytical results are compared to simulations of discrete time stochastic gradient descent and show good agreement.

The inference of a large symmetric signal-matrix$\boldsymbol{S} \in \mathbb {R}^{N\times N}$corrupted by additive Gaussian noise, is considered for two regimes of growth of the rank M as a function of N. For sub-linear ranks$M=\Theta (N^{\alpha })$with$\alpha \in (0,1)$the mutual information and minimum mean-square error (MMSE) are derived for two classes of signal-matrices: (a)$\boldsymbol{S} =\boldsymbol{X} \boldsymbol{X} ^{\intercal } $with entries of$\boldsymbol{X} \in \mathbb {R}^{N\times M}$independent identically distributed; (b)$\boldsymbol{S} $sampled from a rotationally invariant distribution. Surprisingly, the formulas match the rank-one case. Two efficient algorithms are explored and conjectured to saturate the MMSE when no statistical-to-computational gap is present: (1) Decimation Approximate Message Passing; (2) a spectral algorithm based on a Rotation Invariant Estimator. For linear ranks$M=\Theta (N)$the mutual information is rigorously derived for signal-matrices from a rotationally invariant distribution. Close connections with scalar inference in free probability are uncovered, which allow to deduce a simple formula for the MMSE as an integral involving the limiting spectral measure of the data matrix only. An interesting issue is whether the known information theoretic phase transitions for rank-one, and hence also sub-linear-rank, still persist in linear-rank. Our analysis suggests that only a smoothed-out trace of the transitions persists. Furthermore, the change of behavior between low and truly high-rank regimes only happens at the linear scale$\alpha = 1$.

We propose a rectangular rotational invariant estimator to recover a real matrix from noisy matrix observations coming from an arbitrary additive rotational invariant perturbation, in the large dimension limit. Using the Bayes-optimality of this estimator, we derive the asymptotic minimum mean squared error (MMSE). For the particular case of Gaussian noise, we find an explicit expression for the MMSE in terms of the limiting singular value distribution of the observation matrix. Moreover, we prove a formula linking the asymptotic mutual information and the limit of log-spherical integral of rectangular matrices. We also provide numerical checks for our results, which match our theoretical predictions and known Bayesian inference results.

In this work, we present a new approach to analyze the gradient flow for a positive semi-definite matrix denoising problem in an extensive-rank and high-dimensional regime. We use recent linear pencil techniques of random matrix theory to derive fixed point equations which track the complete time evolution of the matrix-mean-square-error of the problem. The predictions of the resulting fixed point equations are validated by numerical experiments. In this short note we briefly illustrate a few predictions of our formalism by way of examples, and in particular we uncover continuous phase transitions in the extensive-rank and high-dimensional regime, which connect to the classical phase transitions of the low-rank problem in the appropriate limit. The formalism has much wider applicability than shown in this communication.

We consider a statistical model for matrix factorization in a regime where the rank of the two hidden matrix factors grows linearly with their dimension and their product is corrupted by additive noise. Despite various approaches, statistical and algorithmic limits of such problems have remained elusive. We study a Bayesian setting with the assumptions that (a) one of the matrix factors is symmetric, (b) both factors as well as the additive noise have rotational invariant priors, (c) the priors are known to the statistician. We derive analytical formulas for Rotation Invariant Estimators to reconstruct the two matrix factors, and conjecture that these are optimal in the large-dimension limit, in the sense that they minimize the average mean-square-error. We provide numerical checks which confirm the optimality conjecture when confronted to Oracle Estimators which are optimal by definition, but involve the ground-truth. Our derivation relies on a combination of tools, namely random matrix theory transforms, spherical integral formulas, and the replica method from statistical mechanics.

We consider the estimation of a n×m matrix u∗v∗Tobserved through an additive Gaussian noise channel, a problem that frequently arises in statistics and machine learning. We investigate a scenario involving mismatched Bayesian inference in which the statistician is unaware of true prior and uses an assumed prior. We derive the exact analytic expression for the asymptotic mean squared error (MSE) in the large system size limit for the particular case of Gaussian priors and additive noise. Our formulas demonstrate that in the mismatched case, estimation is still possible. Additionally, the minimum MSE (MMSE) can be obtained by selecting a non-trivial set of parameters beyond the matched parameters. Our technique is based on the asymptotic behavior of spherical integrals for rectangular matrices. Our method can be extended to non-rotation-invariant distributions for the true prior but requires rotation invariance for the statistician’s assumed prior.

We consider a rank-one symmetric matrix corrupted by additive noise. The rank-one matrix is formed by an n-component unknown vector on the sphere of radius $\sqrt{n}$, and we consider the problem of estimating this vector from the corrupted matrix in the high dimensional limit of $n$ large, by gradient descent for a quadratic cost function on the sphere. Explicit formulas for the whole time evolution of the overlap between the estimator and unknown vector, as well as the cost, are rigorously derived. In the long time limit we recover the well known spectral phase transition, as a function of the signal-to-noise ratio. The explicit formulas also allow to point out interesting transient features of the time evolution. Our analysis technique is based on recent progress in random matrix theory and uses local versions of the semi-circle law.

Recent evidence has shown the existence of a so-called double-descent and even triple-descent behavior for the generalization error of deep-learning models. This important phenomenon commonly appears in implemented neural network architectures, and also seems to emerge in epoch-wise curves during the training process. A recent line of research has highlighted that random matrix tools can be used to obtain precise analytical asymptotics of the generalization (and training) errors of the random feature model. In this contribution, we analyze the whole temporal behavior of the generalization and training errors under gradient flow for the random feature model. We show that in the asymptotic limit of large system size the full time-evolution path of both errors can be calculated analytically. This allows us to observe how the double and triple descents develop over time, if and when early stopping is an option, and also observe time-wise descent structures. Our techniques are based on Cauchy complex integral representations of the errors together with recent random matrix methods based on linear pencils.

Recently, a new adaptive path interpolation method has been developed as a simple and versatile scheme to calculate exactly the asymptotic mutual information of Bayesian inference problems defined on dense factor graphs. These include random linear and generalized estimation, sparse superposition codes, and low-rank matrix / tensor estimation. For all these systems, the adaptive interpolation method directly proves that the replica-symmetric prediction is exact, in a simple and unified manner. When the underlying factor graph of the inference problem is sparse the replica prediction is considerably more complicated, and rigorous results are often lacking or obtained by rather complicated methods. In this work we show how to extend the adaptive path interpolation method to sparse systems. We concentrate on a censored block model, where hidden variables are measured through a binary erasure channel, for which we fully prove the replica prediction.

We consider the problem of estimating a rank-one nonsymmetric matrix under additive white Gaussian noise. The matrix to estimate can be written as the outer product of two vectors and we look at the special case in which both vectors are uniformly distributed on spheres. We prove a replica-symmetric formula for the average mutual information between these vectors and the observations in the high-dimensional regime. This goes beyond previous results which considered vectors with independent and identically distributed elements. The method used can be extended to rank-one tensor problems.

We determine statistical and computational limits for estimation of a rank-one matrix (the spike) corrupted by an additive gaussian noise matrix, in a sparse limit, where the underlying hidden vector (that constructs the rank-one matrix) has a number of non-zero components that scales sub-linearly with the total dimension of the vector, and the signal-to-noise ratio tends to infinity at an appropriate speed. We prove explicit low-dimensional variational formulas for the asymptotic mutual information between the spike and the observed noisy matrix and analyze the approximate message passing algorithm in the sparse regime. For Bernoulli and Bernoulli-Rademacher distributed vectors, and when the sparsity and signal strength satisfy an appropriate scaling relation, we find all-or-nothing phase transitions for the asymptotic minimum and algorithmic mean-square-errors. These jump from their maximum possible value to zero, at well defined signal-to-noise thresholds whose asymptotic values we determine exactly. In the asymptotic regime the statistical-to-algorithmic gap diverges indicating that sparse recovery is hard for approximate message passing.

We consider generalized linear models in regimes where the number of nonzero components of the signal and accessible data points are sublinear with respect to the size of the signal. We prove a variational formula for the asymptotic mutual information per sample when the system size grows to infinity. This result allows us to derive an expression for the minimum mean-square error (MMSE) of the Bayesian estimator when the signal entries have a discrete distribution with finite support. We find that, for such signals and suitable vanishing scalings of the sparsity and sampling rate, the MMSE is nonincreasing piecewise constant. In specific instances the MMSE even displays an all-or-nothing phase transition, that is, the MMSE sharply jumps from its maximum value to zero at a critical sampling rate. The all-or-nothing phenomenon has previously been shown to occur in high-dimensional linear regression. Our analysis goes beyond the linear case and applies to learning the weights of a perceptron with general activation function in a teacher-student scenario. In particular, we discuss an all-or-nothing phenomenon for the generalization error with a sublinear set of training examples.

We consider the estimation of a signal from the knowledge of its noisy linear random Gaussian projections. A few examples where this problem is relevant are compressed sensing, sparse superposition codes, and code division multiple access. There has been a number of works considering the mutual information for this problem using the replica method from statistical physics. Here we put these considerations on a firm rigorous basis. First, we show, using a Guerra-Toninelli type interpolation, that the replica formula yields an upper bound to the exact mutual information. Secondly, for many relevant practical cases, we present a converse lower bound via a method that uses spatial coupling, state evolution analysis and the I-MMSE theorem. This yields a single letter formula for the mutual information and the minimal-mean-square error for random Gaussian linear estimation of all discrete bounded signals. In addition, we prove that the low complexity approximate message-passing algorithm is optimal outside of the so-called hard phase, in the sense that it asymptotically reaches the minimal-mean-square error. In this work spatial coupling is used primarily as a proof technique. However our results also prove two important features of spatially coupled noisy linear random Gaussian estimation. First there is no algorithmically hard phase. This means that for such systems approximate message-passing always reaches the minimal-mean-square error. Secondly, in the limit of infinitely long coupled chain, the mutual information associated to spatially coupled systems is the same as the one of uncoupled linear random Gaussian estimation.

We rigorously derive a single-letter variational expression for the mutual information of the asymmetric two-groups stochastic block model in the dense graph regime. Existing proofs in the literature are indirect, as they involve mapping the model to a rank-one matrix estimation problem whose mutual information is then determined by a combination of methods (e.g., interpolation, cavity, algorithmic, spatial coupling). In this contribution we provide a self-contained direct method using only the recently introduced adaptive interpolation method.

We consider a statistical model for finite-rank symmetric tensor factorization and prove a single-letter variational expression for its mutual information when the tensor is of even order. The proof uses the adaptive interpolation method, for which rank-one matrix factorization is one of the first problems to which it was successfully applied. We show how to extend the adaptive interpolation to finite-rank symmetric tensors of even order, which requires new ideas with respect to the proof for the rank-one case. We also underline where the proof falls short when dealing with odd-order tensors.

Sparse superposition codes, or sparse regression codes, constitute a new class of codes, which was first introduced for communication over the additive white Gaussian noise (AWGN) channel. It has been shown that such codes are capacity-achieving over the AWGN channel under optimal maximum-likelihood decoding as well as under various efficient iterative decoding schemes equipped with power allocation or spatially coupled constructions. Here, we generalize the analysis of these codes to a much broader setting that includes all memoryless channels. We show, for a large class of memoryless channels, that spatial coupling allows an efficient decoder, based on the generalized approximate message-passing (GAMP) algorithm, to reach the potential (or Bayes optimal) threshold of the underlying (or uncoupled) code ensemble. Moreover, we argue that spatially coupled sparse superposition codes universally achieve capacity under GAMP decoding by showing, through analytical computations, that the error floor vanishes and the potential threshold tends to capacity, as one of the code parameters goes to infinity. Furthermore, we provide a closed-form formula for the algorithmic threshold of the underlying code ensemble in terms of Fisher information. Relating an algorithmic threshold to a Fisher information has theoretical as well as practical importance. Our proof relies on the state evolution analysis and uses the potential method developed in the theory of low-density parity-check (LDPC) codes and compressed sensing.

We introduce a technique for the analysis of general spatially coupled systems that are governed by scalar recursions. Such systems can be expressed in variational form in terms of a potential function. We show, under mild conditions, that the potential function is displacement convex and that the minimizers are given by the fixed points (FPs) of the recursions. Furthermore, we give the conditions on the system such that the minimizing FP is unique up to translation along the spatial direction. The condition matches with that of Kudekar et al.[20] for the existence of spatial FPs. Displacement convexity applies to a wide range of spatially coupled recursions appearing in coding theory, compressive sensing, random constraint satisfaction problems, as well as statistical-mechanics models. We illustrate it with applications to low-density parity-check (LDPC) and generalized LDPC codes used for the transmission on the binary erasure channel or general binary memoryless symmetric channels within the Gaussian reciprocal channel approximation as well as compressive sensing.

Generalized linear models (GLMs) arise in high-dimensional machine learning, statistics, communications and signal processing. % In this paper we analyze GLMs when the data matrix is random, as relevant in problems such as compressed sensing, error-correcting codes or benchmarks models in neural networks. % We evaluate the mutual information (or “free entropy”) from which we deduce the Bayes-optimal inference and generalization errors. Our analysis applies to the high-dimensional limit where both the number of samples and dimensions are large and their ratio is fixed. % Non-rigorous predictions for the optimal inference and generalization errors existed for special cases of GLMs, e.g. for the perceptron in the field of statistical physics based on the so-called replica method. Our present paper rigorously establishes those decades old conjectures and brings forward their algorithmic interpretation in terms of performance of the generalized approximate message-passing algorithm. % Furthermore, we tightly characterize, for many learning problems, regions of parameters for which this algorithm achieves the optimal performance, and locate the associated sharp phase transitions separating learnable and non-learnable regions.

A new adaptive path interpolation method has been recently developed as a simple and versatile scheme to calculate exactly the asymptotic mutual information of Bayesian inference problems defined on dense factor graphs. These include random linear and generalized estimation, superposition codes, or low rank matrix and tensor estimation. For all these systems the method directly proves in a unified manner that the replica symmetric prediction is exact. When the underlying factor graph of the inference problem is sparse the replica prediction is considerably more complicated and rigorous results are often lacking or obtained by rather complicated methods. In this contribution we extend the adaptive path interpolation method to sparse systems. We concentrate on a Censored Block Model, where hidden variables are measured through a binary erasure channel, for which we fully prove the replica prediction.

There has been definite progress recently in proving the variational single-letter formula given by the heuristic replica method for various estimation problems. In particular, the replica formula for the mutual information in the case of noisy linear estimation with random i.i.d. matrices, a problem with applications ranging from compressed sensing to statistics, has been proven rigorously. In this contribution we go beyond the restrictive i.i.d. matrix assumption and discuss the formula proposed by Takeda, Uda, Kabashima and later by Tulino, Verdu, Caire and Shamai who used the replica method. Using the recently introduced adaptive interpolation method and random matrix theory, we prove this formula for a relevant large sub-class of rotationally invariant matrices.

Heuristic tools from statistical physics have been used in the past to compute the optimal learning and generalization errors in the teacher-student scenario in multi- layer neural networks. In this contribution, we provide a rigorous justification of these approaches for a two-layers neural network model called the committee machine. We also introduce a version of the approximate message passing (AMP) algorithm for the committee machine that allows to perform optimal learning in polynomial time for a large set of parameters. We find that there are regimes in which a low generalization error is information-theoretically achievable while the AMP algorithm fails to deliver it; strongly suggesting that no efficient algorithm exists for those cases, and unveiling a large computational gap.

We examine a class of stochastic deep learning models with a tractable method to compute information-theoretic quantities. Our contributions are three-fold: (i) We show how entropies and mutual informations can be derived from heuristic statistical physics methods, under the assumption that weight matrices are independent and orthogonally-invariant. (ii) We extend particular cases in which this result is known to be rigorously exact by providing a proof for two-layers networks with Gaussian random weights, using the recently introduced adaptive interpolation method. (iii) We propose an experiment framework with generative models of synthetic datasets, on which we train deep neural networks with a weight constraint designed so that the assumption in (i) is verified during learning. We study the behavior of entropies and mutual information throughout learning and conclude that, in the proposed setting, the relationship between compression and generalization remains elusive.

We consider the dynamics of message passing for spatially coupled codes and, in particular, the set of density evolution equations that tracks the profile of decoding errors along the spatial direction of coupling. It is known that, for suitable boundary conditions and after a transient phase, the error profile exhibits a “solitonic behavior.” Namely, a uniquely shaped wavelike solution develops, which propagates with a constant velocity. Under this assumption, we derive an analytical formula for the velocity in the framework of a continuum limit of the spatially coupled system. The general formalism is developed for spatially coupled low-density parity-check codes on general binary memoryless symmetric channels, which form the main systems of interest in this paper. We apply the formula for special channels and illustrate that it matches the direct numerical evaluation of the velocity for a wide range of noise values. A possible application of the velocity formula to the evaluation of finite size scaling law parameters is also discussed. We conduct a similar analysis for general scalar systems and illustrate the findings with applications to compressive sensing and generalized low-density parity-check codes on the binary erasure or binary symmetric channels.

Consider random linear estimation with Gaussian measurement matrices and noise. One can compute infinitesimal variations of the mutual information under infinitesimal variations of the signal-to-noise ratio or of the measurement rate. We discuss how each variation is related to the minimum mean-square error and deduce that the two variations are directly connected through a very simple identity. The main technical ingredient is a new interpolation method called “sub-extensive interpolation method”. We use it to provide a new proof of an I-MMSE relation recently found by Reeves and Pfister [1] when the measurement rate is varied. Our proof makes it clear that this relation is intimately related to another I-MMSE relation also recently proved in [2]. One can directly verify that the identity relating the two types of variation of mutual information is indeed consistent with the one letter replica symmetric formula for the mutual information, first derived by Tanaka [3] for binary signals, and recently proved in more generality in [1, 2, 4, 5] (by independent methods). However our proof is independent of any knowledge of Tanaka's formula.

The generalized censored block model considers the problem of inferring hidden binary variables from observations that are outputs of pairwise measurements from a symmetric channel. We give an exact formula for the stability threshold of density evolution by using an analysis of the potential functional of the model. In this model the phase transition is continuous so that this threshold is also the one for partial recovery of hidden variables. The formula is valid for all symmetric channels and generalizes the one already known for binary symmetric channels. We also give a bound on the finite slope of the Bhattacharyya parameter at the stability threshold. Finally, we briefly discuss implications for a heuristic derivation of the replica formula for the conditional entropy of the model.

Recently, a new class of codes, called sparse superposition or sparse regression codes, has been proposed for communication over the AWGN channel. It has been proven that they achieve capacity using power allocation and various forms of iterative decoding. Empirical evidence has also strongly suggested that the codes achieve capacity when spatial coupling and approximate message passing decoding are used, without need of power allocation. In this note we prove that state evolution (which tracks message passing) indeed saturates the potential threshold of the underlying code ensemble, which approaches in a proper limit the optimal threshold. Our proof uses ideas developed in the theory of low-density parity-check codes and compressive sensing.

We consider the dynamics of belief propagation decoding of spatially coupled Low-Density Parity-Check codes. It has been conjectured that after a short transient phase, the profile of “error probabilities” along the spatial direction of a spatially coupled code develops a uniquely-shaped wavelike solution that propagates with constant velocity ν. Under this assumption and for transmission over general Binary Memoryless Symmetric channels, we derive a formula for ν. We also propose approximations that are simpler to compute and support our findings using numerical data.

We recently proved threshold saturation for spatially coupled sparse superposition codes on the additive white Gaussian noise channel [1]. Here we generalize our analysis to a much broader setting. We show for any memoryless channel that spatial coupling allows generalized approximate message-passing (GAMP) decoding to reach the potential (or Bayes optimal) threshold of the code ensemble. Moreover in the large input alphabet size limit: i) the GAMP algorithmic threshold of the underlying (or uncoupled) code ensemble is simply expressed as a Fisher information; ii) the potential threshold tends to Shannon's capacity. Although we focus on coding for sake of coherence with our previous results, the framework and methods are very general and hold for a wide class of generalized estimation problems with random linear mixing.

We consider spatially coupled systems governed by a set of scalar density evolution equations. Such equations track the behavior of message-passing algorithms used, for example, in coding, sparse sensing, or constraint-satisfaction problems. Assuming that the “profile” describing the average state of the algorithm exhibits a solitonic wave-like behavior after initial transient iterations, we derive a formula for the propagation velocity of the wave. We illustrate the formula with two applications, namely Generalized LDPC codes and compressive sensing.

Factorizing low-rank matrices has many applications in machine learning and statistics. For probabilistic models in the Bayes optimal setting, a general expression for the mutual information has been proposed using heuristic statistical physics computations, and proven in few specific cases. Here, we show how to rigorously prove the conjectured formula for the symmetric rank-one case. This allows to express the minimal mean-square-error and to characterize the detectability phase transitions in a large set of estimation problems ranging from community detection to sparse PCA. We also show that for a large set of parameters, an iterative algorithm called approximate message-passing is Bayes optimal. There exists, however, a gap between what currently known polynomial algorithms can do and what is expected information theoretically. Additionally, the proof technique has an interest of its own and exploits three essential ingredients: the interpolation method introduced in statistical physics by Guerra, the analysis of the approximate message-passing algorithm and the theory of spatial coupling and threshold saturation in coding. Our approach is generic and applicable to other open problems in statistical estimation where heuristic statistical physics predictions are available.

We report on a novel technique called spatial coupling and its application in the analysis of random constraint satisfaction problems (CSP). Spatial coupling was invented as an engineering construction in the area of error correcting codes where it has resulted in efficient capacity-achieving codes for a wide range of channels. However, this technique is not limited to problems in communications, and can be applied in the much broader context of graphical models. We describe here a general methodology for applying spatial coupling to random constraint satisfaction problems and obtain lower bounds for their (rough) satisfiability threshold. The main idea is to construct a distribution of geometrically structured random K-SAT instances – namely the spatially coupled ensemble – which has the same (rough) satisfiability threshold, and is at the same time algorithmically easier to solve. Then by running well-known algorithms on the spatially coupled ensemble we obtain a lower bound on the (rough) satisfiability threshold of the original ensemble. The method is versatile because one can choose the CSP, there is a certain amount of freedom in the construction of the spatially coupled ensemble, and also in the choice of the algorithm. In this work we focus on random K-SAT but we have also checked that the method is successful for Coloring, NAE-SAT and XOR-SAT. We choose Unit Clause propagation for the algorithm which is analyzed over the spatially coupled instances. For K = 3, for instance, our lower bound is equal to 3.67 which is better than the current bounds in the literature. Similarly, for graph 3-colorability we get a bound of 2.22 which is also better than the current bounds in the literature.

The aim of this paper is to show that spatial coupling can be viewed not only as a means to build better graphical models, but also as a tool to better understand uncoupled models. The starting point is the observation that some asymptotic properties of graphical models are easier to prove in the case of spatial coupling. In such cases, one can then use the so-called interpolation method to transfer known results for the spatially coupled case to the uncoupled one. Our main use of this framework is for Low-density parity check (LDPC) codes, where we use interpolation to show that the average entropy of the codeword conditioned on the observation is asymptotically the same for spatially coupled as for uncoupled ensembles. We give three applications of this result for a large class of LDPC ensembles. The first one is a proof of the so-called Maxwell construction stating that the MAP threshold is equal to the area threshold of the BP GEXIT curve. The second is a proof of the equality between the BP and MAP GEXIT curves above the MAP threshold. The third application is the intimately related fact that the replica symmetric formula for the conditional entropy in the infinite block length limit is exact.

The main objective of this paper is to explore the precise relationship between the Bethe free energy (or entropy) and the Shannon conditional entropy of graphical error correcting codes. The main result shows that the Bethe free energy associated with a low-density parity-check code used over a binary symmetric channel in a large noise regime is, with high probability, asymptotically exact as the block length grows. To arrive at this result, we develop new techniques for rather general graphical models based on the loop sum as a starting point and the polymer expansion from statistical mechanics. The true free energy is computed as a series expansion containing the Bethe free energy as its zeroth-order term plus a series of corrections. It is easily seen that convergence criteria for such expansions are satisfied for general high-temperature models. We apply these general results to the ensembles of low-density generator-matrix and parity-check codes. While the application to generator-matrix codes follows standard high temperature methods, the case of parity-check codes requires non-trivial new ideas, because the hard constraints correspond to a zero-temperature regime. Nevertheless, one can combine the polymer expansion with expander and counting arguments to show that the difference between the true and Bethe free energies vanishes with high probability in the large block length limit.

We investigate an encoding scheme for lossy compression of a binary symmetric source based on simple spatially coupled low-density generator-matrix codes. The degree of the check nodes is regular and the one of code-bits is Poisson distributed with an average depending on the compression rate. The performance of a low complexity belief propagation guided decimation algorithm is excellent. The algorithmic rate-distortion curve approaches the optimal curve of the ensemble as the width of the coupling window grows. Moreover, as the check degree grows both curves approach the ultimate Shannon rate-distortion limit. The belief propagation guided decimation encoder is based on the posterior measure of a binary symmetric test-channel. This measure can be interpreted as a random Gibbs measure at a temperature directly related to the noise level of the test-channel. We investigate the links between the algorithmic performance of the belief propagation guided decimation encoder and the phase diagram of this Gibbs measure. The phase diagram is investigated thanks to the cavity method of spin glass theory which predicts a number of phase transition thresholds. In particular, the dynamical and condensation phase transition temperatures (equivalently test-channel noise thresholds) are computed. We observe that: 1) the dynamical temperature of the spatially coupled construction saturates toward the condensation temperature and 2) for large degrees the condensation temperature approaches the temperature (i.e., noise level) related to the information theoretic Shannon test-channel noise parameter of rate-distortion theory. This provides heuristic insight into the excellent performance of the belief propagation guided decimation algorithm. This paper contains an introduction to the cavity method.

Potential functionals have been introduced recently as an important tool for the analysis of coupled scalar systems (e.g. density evolution equations). In this contribution we investigate interesting properties of this potential. Using the tool of displacement convexity we show that, under mild assumptions on the system, the potential functional is displacement convex. Furthermore, we give the conditions on the system such that the potential is strictly displacement convex in which case the minimizer is unique.

Spatially-coupled low-density parity-check (LDPC) codes, which were first introduced as LDPC convolutional codes, have been shown to exhibit excellent performance under low-complexity belief-propagation decoding. This phenomenon is now termed threshold saturation via spatial coupling. Spatially-coupled codes have been successfully applied in numerous areas. In particular, it was proven that spatially-coupled regular LDPC codes universally achieve capacity over the class of binary memoryless symmetric (BMS) channels under belief-propagation decoding. Recently, potential functions have been used to simplify threshold saturation proofs for scalar and vector recursions. In this paper, potential functions are used to prove threshold saturation for irregular LDPC and low-density generator-matrix codes on BMS channels, extending the simplified proof technique to BMS channels. The corresponding potential functions are closely related to the average Bethe free entropy of the ensembles in the large-system limit. These functions also appear in statistical physics when the replica method is used to analyze optimal decoding.

We investigate an encoding scheme for lossy compression based on spatially coupled Low-Density GeneratorMatrix codes. The degree distributions are regular, or are Poisson on the code-bit side and check-regular which allows use for any compression rate. The performance of a low complexity Belief Propagation Guided Decimation algorithm is excellent, and for large check degrees it gets close to Shannon's rate-distortion limit. We investigate links between the algorithmic performance and the phase diagram of a relevant random Gibbs measure. The associated dynamical and condensation thresholds are computed within the framework of the cavity method. We observe that: (i) the dynamical threshold of the spatially coupled construction saturates towards the condensation threshold; (ii) for large degrees the condensation threshold approaches the information theoretic test-channel parameter of rate-distortion theory. This provides heuristic insight into the excellent performance of the BPGD algorithm.

The aim of this paper is to show that spatial coupling can be viewed not only as a means to build better graphical models, but also as a tool to better understand uncoupled models. The starting point is the observation that some asymptotic properties of graphical models are easier to prove in the case of spatial coupling. In such cases, one can then use the so-called interpolation method to transfer results known for the spatially coupled case to the uncoupled one. Our main application of this framework is to LDPC codes, where we use interpolation to show that the average entropy of the codeword conditioned on the observation is asymptotically the same for spatially coupled as for uncoupled ensembles. We use this fact to prove the so-called Maxwell conjecture for a large class of ensembles. In a first paper last year, we have successfully implemented this strategy for the case of LDPC ensembles where the variable node degree distribution is Poisson. In the current paper we now show how to treat the practically more relevant case of general left degree distributions. In particular, regular ensembles fall within this framework. As we will see, a number of technical difficulties appear when compared to the simpler case of Poisson-distributed degrees. For our arguments to hold we need symmetry to be present. For coding, this symmetry follows from the channel symmetry; for general graphical models the required symmetry is called Nishimori symmetry.

The XOR-satisfiability (XORSAT) problem deals with a system of n Boolean variables and m clauses. Each clause is a linear Boolean equation (XOR) of a subset of the variables. A K-clause is a clause involving K distinct variables. In the random K-XORSAT problem a formula is created by choosing m K-clauses uniformly at random from the set of all possible clauses on n variables. The set of solutions of a random formula exhibits various geometrical transitions as the ratio m/n varies. We consider a coupled K-XORSAT ensemble, consisting of a chain of random XORSAT models that are spatially coupled across a finite window along the chain direction. We observe that the threshold saturation phenomenon takes place for this ensemble and we characterize various properties of the space of solutions of such coupled formulae.

Spatial coupling has recently emerged as a powerful paradigm to construct graphical models that work well under low-complexity message-passing algorithms. Although much progress has been made on the analysis of spatially coupled models under message passing, there is still room for improvement, both in terms of simplifying existing proofs as well as in terms of proving additional properties. We introduce one further tool for the analysis, namely the concept of displacement convexity. This concept plays a crucial role in the theory of optimal transport and it is also well suited for the analysis of spatially coupled systems. In cases where the concept applies, displacement convexity allows functionals of distributions which are not convex to be represented in an alternative form, so that they are convex with respect to the new parametrization. The alternative convex structure can then often be used to prove the uniqueness of the minimizer of this functional. As a proof of concept we consider spatially coupled (l, r)-regular Gallager ensembles when transmission takes place over the binary erasure channel. In particular, we first show the existence of an optimal profile which minimizes the potential functional governing this system. This profile characterizes the “decoding wave” of the spatially coupled system. We then show that the potential function of the coupled system is displacement convex. Due to some translational degrees of freedom the convexity by itself falls short of establishing the uniqueness of the minimizing profile. But as we will discuss it is an important step in this direction.

We study a new encoding scheme for lossy source compression based on spatially coupled low-density generatormatrix codes. We develop a belief-propagation guided-decimation algorithm, and show that this algorithm allows to approach the optimal distortion of spatially coupled ensembles. Moreover, using the survey propagation formalism, we also observe that the optimal distortions of the spatially coupled and individual code ensembles are the same. Since regular low-density generatormatrix codes are known to achieve the Shannon rate-distortion bound under optimal encoding as the degrees grow, our results suggest that spatial coupling can be used to reach the rate-distortion bound, under a low complexity belief-propagation guided-decimation algorithm.

Investigations on spatially coupled codes have lead to the conjecture that, in the infinite size limit, the average input-output conditional entropy for spatially coupled low-density parity-check ensembles, over binary memoryless symmetric channels, equals the entropy of the underlying individual ensemble. We give a self-contained proof of this conjecture for the case when the variable degrees have a Poisson distribution and all check degrees are even. The ingredients of the proof are the interpolation method and the Nishimori identities. We explain why this result is an important step towards proving the Maxwell conjecture in the theory of low-density parity-check codes.

The loop series provides a formal way to write down corrections to the Bethe entropy (and/or free energy) of graphical models. We provide methods to rigorously control such expansions for low-density parity-check codes used over a highly noisy binary symmetric channel. We prove that in the asymptotic limit of large size, with high probability, the Bethe expression gives an exact formula for the entropy (per bit) of the input word conditioned on the output of the channel. Our methods also apply to more general models.

Convolutional Low-Density-Parity-Check (LDPC) ensembles have excellent performance. Their iterative threshold increases with their average degree, or with the size of the coupling window in randomized constructions. In the latter case, as the window size grows, the Belief Propagation (BP) threshold attains the maximum-a-posteriori (MAP) threshold of the underlying ensemble. In this contribution we show that a similar phenomenon happens for the growth rate of coupled ensembles. Loosely speaking, we observe that as the coupling strength grows, the growth rate of the coupled ensemble comes close to the concave hull of the underlying ensemble's growth rate. For ensembles randomly coupled across a window the growth rate actually tends to the concave hull of the underlying one as the window size increases. Our observations are supported by the calculations of the combinatorial growth rate, and that of the growth rate derived from the replica method. The observed concavity is a general feature of coupled mean field graphical models and is already present at the level of coupled Curie-Weiss models. There, the canonical free energy of the coupled system tends to the concave hull of the underlying one. As we explain, the behavior of the growth rate of coupled ensembles is exactly analogous.

The subject of this paper is transmission over a general class of binary-input memoryless symmetric channels using error correcting codes based on sparse graphs, namely, low-density generator-matrix and low-density parity-check codes. The optimal (or ideal) decoder based on the posterior measure over the code-bits and its relationship to the suboptimal belief propagation decoder are investigated. We consider the correlation (or covariance) between two code-bits, averaged over the noise realizations, as a function of the graph distance for the optimal decoder. Our main result is that this correlation decays exponentially fast for given low-density generator-matrix codes and a high enough noise parameter and also for given low-density parity-check codes and a low enough noise parameter. This has many consequences. Appropriate performance curves—called generalized extrinsic information transfer (GEXIT) functions—of the belief propagation and optimal decoders match in high/low noise regimes. This means that in high/low noise regimes the performance curves of the optimal decoder can be computed by density evolution. Another interpretation is that the replica predictions of spin-glass theory are exact. Our methods are rather general and use cluster expansions first developed in the context of mathematical statistical mechanics.

The excellent performance of convolutional low-density parity-check codes is the result of the spatial coupling of individual underlying codes across a window of growing size, but much smaller than the length of the individual codes. Remarkably, the belief-propagation threshold of the coupled ensemble is boosted to the maximum-a-posteriori one of the individual system. We investigate the generality of this phenomenon beyond coding theory: we couple general graphical models into a one-dimensional chain of large individual systems. For the later we take the Curie-Weiss, random field Curie-Weiss, If-satisfiability, and Q-coloring models. We always find, based on analytical as well as numerical calculations, that the message passing thresholds of the coupled systems come very close to the static ones of the individual models. The remarkable properties of convolutional low-density parity-check codes are a manifestation of this very general phenomenon.

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.

Consider transmission over a binary additive white gaussian noise channel using a fixed low-density parity check code. We consider the posterior measure over the code bits and the corresponding correlation between two codebits, averaged over the noise realizations. We show that for low enough noise variance this average correlation decays exponentially fast with the graph distance between the code bits. One consequence of this result is that for low enough noise variance the GEXIT functions (further averaged over a standard code ensemble) of the belief propagation and optimal decoders are the same.

Consider communication over a binary-input memoryless output-symmetric channel with low-density parity-check (LDPC) codes and maximumaposteriori(MAP) decoding. The replica method of spin glass theory allows to conjecture an analytic formula for the average input-output conditional entropy per bit in the infinite block length limit. Montanari proved a lower bound for this entropy, in the case of LDPC ensembles with convex check degree polynomial, which matches the replica formula. Here we extend this lower bound to any irregular LDPC ensemble. The new feature of our work is an analysis of the second derivative of the conditional input-output entropy with respect to noise. A close relation arises between this second derivative and correlation or mutual information of codebits. This allows us to extend the realm of the ldquointerpolation method,rdquo in particular, we show how channel symmetry allows to control the fluctuations of the ldquooverlap parametersrdquo.

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 binary input memoryless output symmetric channel with low density generator matrix 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 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 solution is indeed exact in the high noise regime, where it coincides with density evolution equations. Our method uses ideas coming from high temperature expansions in spin glass theory.

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.

It is shown that a correlation inequality of statistical mechanics can be applied to linear low-density parity-check codes. Thanks to this tool we prove that, under a natural assumption, the exponential growth rate of regular low-density parity-check (LDPC) codes, can be computed exactly by iterative methods, at least on the interval where it is a concave function of the relative weight of code words. Then, considering communication over a binary input additive white Gaussian noise channel with a Poisson LDPC code we prove that, under a natural assumption, part of the GEXIT curve (associated to MAP decoding) can also be computed exactly by the belief propagation algorithm. The correlation inequality yields a sharp lower bound on the GEXIT curve. We also make an extension of the interpolation techniques that have recently led to rigorous results in spin glass theory and in the SAT problem

We consider communication over binary-input memoryless symmetric channels with low-density parity-check (LDPC) codes. The relationship between maximum a posteriori and belief propagation decoding is investigated using a set of correlation inequalities that first appeared in statistical mechanics of Gaussian spin glasses. We prove bounds on generalized extrinsic information transfer (EXIT) functions, that are believed to be tight, and discuss their relationship with the ones obtained by the interpolation method.

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

Consider communication over a binary input memoryless output symmetric channel with LDPC codes and MAP decoding. Recently Montanari proved that the replica solution is a lower bound to the conditional entropy for a class of LDPC ensembles. Here we extend this lower bound to any irregular LDPC ensemble for the BEC, BIAWGNC, BSC. Our work combines an analysis of the second derivative of the conditional entropy with respect to the noise and the interpolation method

We consider communication over binary input memoryless symmetric channels with low density parity check codes. The relationship between maximum a posteriori and belief propagation GEXIT functions is investigated using a set of correlation inequalities of statistical mechanics for Gaussian spin glasses. We use these to prove bounds that are believed to be tight and point out their close connection with the ones obtained by the interpolation method invented in the context of spin glasses.

It is shown that a correlation inequality of statistical mechanics can be applied to low-density parity-check codes. Thanks to this tool we prove that the growth rate of regular LDPC codes, can be exactly calculated by iterative methods, at least on the interval where it is a concave function of the relative weight of code words. We also consider communication over a binary input additive white Gaussian noise channel with a Poisson LDPC code and prove that (at least part of) the GEXIT curve (associated to MAP decoding) can also be computed exactly by the belief propagation decoder. In both problems, the correlation inequality yields sharp lower bounds. We also use a non trivial extension of the interpolation techniques that have recently led to rigorous results in spin glass theory and in the SAT problem