Generalized linear models (GLMs) are used in high-dimensional machine learning, statistics, communications, and signal processing. In this paper we analyze GLMs when the data matrix is random, as relevant problems such compressed sensing, error-correcting codes, or benchmark neural networks. We evaluate mutual information (or “free entropy”) from which deduce Bayes-optimal estimation generalization errors. Our analysis applies to limit where both number of samples dimension large their ratio...

Abstract We examine a class of stochastic deep learning models with 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 independent orthogonally-invariant. (ii) extend particular cases in which this result is known rigorously exact by providing proof for two-layers networks Gaussian random weights,...

Continuum percolation models in which pairs of points a two-dimensional Poisson point process are connected if they within some range each other have been extensively studied. This paper considers variation connection between two depends not only on their Euclidean distance, but also the positions all process. model has recently proposed to interference radio communications networks. Our main result shows that, despite infinite-range dependencies, occurs when density λ is greater than...

Spatially-coupled low-density parity-check (LDPC) codes, which were first introduced as LDPC convolutional have been shown to exhibit excellent performance under low-complexity belief-propagation decoding. This phenomenon is now termed threshold saturation via spatial coupling. codes successfully applied in numerous areas. In particular, it was proven that spatially-coupled regular universally achieve capacity over the class of binary memoryless symmetric (BMS) channels Recently, potential...

We consider the estimation of a signal from knowledge its noisy linear random Gaussian projections, problem relevant in compressed sensing, sparse superposition codes or code division multiple access just to cite few. There has been number works considering mutual information for this using heuristic replica method statistical physics. Here we put these considerations on firm rigorous basis. First, show, Guerra-type interpolation, that formula yields an upper bound exact information....

Factorizing low-rank matrices has many applications in machine learning and statistics. For probabilistic models the Bayes optimal setting, a general expression for mutual information been proposed using heuristic statistical physics computations, proven few specific cases. Here, we show how to rigorously prove conjectured formula symmetric rank-one case. This allows express minimal mean-square-error characterize detectability phase transitions large set of estimation problems ranging from...

We consider the estimation of a signal from knowledge 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 number works considering mutual information for using replica method statistical physics. Here we put these considerations on firm rigorous basis. First, show, Guerra-Toninelli type interpolation, that formula yields an upper bound to exact...

The excellent performance of convolutional low-density parity-check codes is the result spatial coupling individual underlying across a window growing size, but much smaller than length codes. Remarkably, belief-propagation threshold coupled ensemble boosted to maximum-a-posteriori one system. We investigate generality this phenomenon beyond coding theory: we couple general graphical models into one-dimensional chain large systems. For later take Curie-Weiss, random field If-satisfiability,...

We consider rank-one non-symmetric tensor estimation and derive simple formulas for the mutual information. start by order 2 problem, namely matrix factorization. treat it completely in a simpler fashion than previous proofs using new type of interpolation method developed [1]. then show how to harness structure "layers" obtain formula information 3 problem from knowledge still same kind interpolation. Our proof technique straightforwardly generalizes allows rigorously at any recursive way.

In this contribution we give a pedagogic introduction to the newly introduced adaptive interpolation method prove in simple and unified way replica formulas for Bayesian optimal inference problems. Many aspects of can already be explained at level Curie-Weiss spin system. This provides new solution model which does not appear known. We then generalize analysis paradigmatic problem, namely rank-one matrix estimation, also refered as Wigner spike statistics. many pointers recent literature...

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

Heuristic tools from statistical physics have been used in the past to locate phase transitions and compute optimal learning generalization errors teacher-student scenario multi-layer neural networks. In this contribution, we provide a rigorous justification of these approaches for two-layers network model called committee machine. We also introduce version approximate message passing (AMP) algorithm machine that allows perform polynomial time large set parameters. find there are regimes...

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 general class of symmetric distributions for spreading sequences, in the limit large number users, prove an upper bound to capacity. The matches formula obtained by Tanaka replica method. We also show concentration various relevant quantities including mutual information and free energy. mathematical methods are quite allow...

We consider increasingly complex models of matrix denoising and dictionary learning in the Bayes-optimal setting, challenging regime where matrices to infer have a rank growing linearly with system size. This is contrast most existing literature concerned low-rank (i.e., constant-rank) regime. first class rotationally invariant problems whose mutual information minimum mean-square error are computable using techniques from random theory. Next, we analyze more learning. To do so introduce...

We derive asymptotically precise expressions for test and train errors of denoising score matching (DSM) in generative diffusion models. The function is parameterized by random features neural networks, with the target distribution being $d$-dimensional standard Gaussian. operate a regime where dimension $d$, number data samples $n$, $p$ tend to infinity while keeping ratios $\psi_n=\frac{n}{d}$ $\psi_p=\frac{p}{d}$ fixed. By characterizing errors, we identify regimes generalization...

We analyze the time reversed dynamics of generative diffusion models. If exact empirical score function is used in a regime large dimension and exponentially number samples, these models are known to undergo transitions between distinct dynamical regimes. extend this analysis compute for an analytically tractable manifold model where statistical data mixture lower dimensional Gaussians embedded higher space. so-called speciation collapse transition times, as ratio manifold-to-ambient space...

It is shown that a correlation inequality of statistical mechanics can be applied to linear low-density parity-check codes. Thanks this tool we prove that, under natural assumption, the exponential growth rate regular (LDPC) codes, computed exactly by iterative methods, at least on interval where it concave function relative weight code words. Then, considering communication over binary input additive white Gaussian noise channel with Poisson LDPC part GEXIT curve (associated MAP decoding)...

The aim of this paper is to show that spatial coupling can be viewed not only as a means build better graphical models, but also tool understand uncoupled models. starting point the observation some asymptotic properties models are easier prove in case coupling. In such cases, one then use so-called interpolation method transfer known results for spatially coupled one. Our main framework Low-density parity check (LDPC) codes, where we average entropy codeword conditioned on asymptotically...

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 set of correlation inequalities that first appeared in statistical mechanics Gaussian spin glasses. prove bounds on generalized extrinsic information transfer (EXIT) functions, are believed to be tight, discuss their the ones obtained by interpolation method.