Statistical physics of inference: Thresholds and algorithms

Lenka Zdeborová; Florent Krzakala

Source-linked AI summary

Statistical physics of inference: Thresholds and algorithms

Lenka Zdeborová, Florent Krzakala

arXiv:1511.02476v5Nov 8, 2015cond-mat.stat-mechcs.DSstat.ML

TL;DR

The paper asks when noisy or partial observations contain enough information for useful inference and which algorithms can recover the underlying variables efficiently. It reviews statistical-physics tools, especially the planted spin-glass formulation, to relate inference thresholds to phase transitions and algorithm design. The review covers graph clustering and noisy linear estimation, including community detection and compressed sensing, while emphasizing that its teacher-student focus excludes model-selection problems.

Problem
The paper addresses when observations provide sufficient information for satisfactory recovery and how computationally efficient inference algorithms can be developed.
Method
The review uses replica and cavity methods, related message-passing algorithms, and the planted spin-glass formulation to study inference thresholds and algorithms.
Results
The review connects inference barriers with statistical-physics phase transitions and surveys applications in graph clustering and noisy linear estimation.
Takeaways & Limitations
The statistical-physics perspective provides physical insight for developing new algorithms, including belief propagation and approximate message passing, across the reviewed inference problems.
Takeaways & Limitations
The review focuses on teacher-student settings and does not analyze observations with no known generative system or model-selection problems.

Abstract

from arXiv · show

Many questions of fundamental interest in todays science can be formulated as inference problems: Some partial, or noisy, observations are performed over a set of variables and the goal is to recover, or infer, the values of the variables based on the indirect information contained in the measurements. For such problems, the central scientific questions are: Under what conditions is the information contained in the measurements sufficient for a satisfactory inference to be possible? What are the most efficient algorithms for this task? A growing body of work has shown that often we can understand and locate these fundamental barriers by thinking of them as phase transitions in the sense of statistical physics. Moreover, it turned out that we can use the gained physical insight to develop new promising algorithms. Connection between inference and statistical physics is currently witnessing an impressive renaissance and we review here the current state-of-the-art, with a pedagogical focus on the Ising model which formulated as an inference problem we call the planted spin glass. In terms of applications we review two classes of problems: (i) inference of clusters on graphs and networks, with community detection as a special case and (ii) estimating a signal from its noisy linear measurements, with compressed sensing as a case of sparse estimation. Our goal is to provide a pedagogical review for researchers in physics and other fields interested in this fascinating topic.

I. INTRODUCTION

This review connects statistical inference with statistical physics by interpreting information and computational thresholds as phase-transition phenomena. It develops this perspective through planted ensembles, spin-glass methods, and applications to network clustering and compressed sensing.

Scope and motivation: The review studies how statistical-physics concepts illuminate inference problems at the interface of data analysis and disordered systems.Its toolbox includes replica and cavity methods together with related message-passing algorithms.
Teacher-student and planted ensembles: The teacher-student scenario generates data from ground truth and a probabilistic model, allowing Bayesian-optimal recovery to be analyzed.The review presents this setting as a planted statistical ensemble of the corresponding physics model.
Planted spin glass: The planted spin glass provides a prototypical model in which Bayes-optimal inference translates into thermodynamics on the Nishimori line.The review then uses belief propagation and cavity methods to analyze phase diagrams of high-dimensional inference problems.
Applications and scope: The review focuses on network clustering and compressed sensing because recent inference–physics results in these applications were not yet well covered by other reviews.Neural networks and error-correcting codes are discussed only as limited or historical connections.
Core questions: Inference asks when noisy or partial observations contain enough information for satisfactory recovery, while algorithms ask whether recovery can be computationally efficient.The review treats these statistical and computational questions together.
Thresholds and algorithms: Phase transitions describe information thresholds, while transition order and metastability are linked to computational hardness.The review therefore examines whether algorithms can reach phase-transition boundaries.

2. Teacher-student scenario

The teacher-student scenario generates hidden ground-truth variables and observations from known or partially known distributions, then asks the student to infer the hidden variables. In the Bayes-optimal case, posterior samples share key statistical identities with the ground truth.

Teacher-student setup: The teacher samples ground-truth variables from a prior and generates observations using a likelihood model before giving the data and model information to the student.The student then infers the original variables from the observations and the available distributional information.
Teacher-student setup: The review studies high-dimensional settings with latent vectors, low-dimensional model parameters, separable priors, and observations that independently depend on variable subsets.These assumptions support factorized Bayesian formulations of the inference problem.
Bayesian information: In the Bayes-optimal case, the student receives the full and correct prior and likelihood; with mismatched parameters, the functional forms are correct but parameter values are unknown.The review distinguishes these cases according to the information supplied about the teacher’s distributions.
Bayesian information: Bayes optimality gives E[f(x1, x2)] = E[f(x*, x)], making the ground truth statistically interchangeable with a posterior sample under expectations.The review calls this simplification the Nishimori condition and notes that it generally fails under model mismatch.
Estimators: MAP maximizes the posterior, whereas MMSE minimizes posterior-averaged squared error and is obtained from posterior marginal means.MAP is generally easier to approach computationally, but lacks confidence intervals and can have overfitting issues.

5. The high-dimensional limit

The high-dimensional limit keeps the observation-to-variable ratio fixed while system size grows, exposing distinct information and computational thresholds. Statistical-physics methods provide a framework for analyzing these thresholds and related algorithms.

High-dimensional scaling: High-dimensional inference considers many variables and observations with α = M/N fixed as N →∞, making separating useful information from noise more challenging.Computational efficiency matters alongside solvability because the data and problem dimension can both be large.
Thresholds: For α < αc inference is impossible, for α > αs efficient algorithms exist, and αc < α < αs is information-theoretically possible but computationally harder.These regimes distinguish insufficient information from algorithmic difficulty.
Thresholds: A central objective is to determine αc and αs and develop algorithms that succeed with information levels as close as possible to αs.The review treats these thresholds as the main targets for statistical-physics analysis of inference.
Statistical-physics toolbox: The review applies spin-glass tools, including replica and cavity methods and message passing, to connect phase transitions with inference thresholds.It emphasizes recent applications of these methods to inference problems and associated algorithms.
Algorithms: Monte Carlo methods can provide exact answers after sufficiently long runs under ergodicity and balance, but their required time can be exponential in system size.The review contrasts this broad applicability with difficulty controlling the runtime needed for satisfactory precision.
Algorithms: Belief propagation is asymptotically exact for a class of mean-field spin glasses and supports exact analyses that variational mean field generally does not.It is described as similarly fast but generally more precise than variational mean-field methods.

4. Useful statistical physics concepts

Statistical-physics concepts clarify inference through thermodynamic limits, phase transitions, self-averaging, and spin models. The planted spin glass maps recovery to magnetization while exposing detectability boundaries.

Self-averaging: Self-averaging means that a quantity becomes independent of the particular disorder realization in the thermodynamic limit and depends only on its statistics.The formal condition is that deviations from the disorder average vanish in probability as N →∞.
Self-averaging: Under self-averaging, MMSE and MMO identities hold for typical realizations, equating their ground-truth errors or overlaps with quantities evaluated without ground-truth knowledge.This simplifies thermodynamic-limit analysis, although proving self-averaging rigorously is technically difficult.
Phase transitions: True phase transitions require a non-analyticity in free-energy density that can appear only after taking the thermodynamic limit N →∞.At finite system size, the free-energy density remains analytic.
Phase transitions: Inference thresholds can correspond to genuine phase transitions as increasing measurement information changes recoverability, while more generic rapid changes are called cross-overs.The review reserves phase transition or threshold for the sharper physics-based notion.
Planted spin glass: The planted spin glass makes the teacher-student posterior equal to an Ising-model Boltzmann distribution, allowing spin-glass knowledge to analyze inference.The inference goal becomes recovering the planted configuration rather than studying glassy behavior itself.
Planted spin glass: At ρ = 1, dense connected graphs permit recovery up to global flip symmetry, whereas at ρ = 1/2 the couplings contain no information and recovery is impossible.The intermediate regime 1/2 < ρ < 1 has a nontrivial phase diagram governing detectability.

B. Nishimori’s mapping via gauge transformation

A gauge transformation converts the planted spin glass into a ferromagnetically biased standard spin glass, making inference correspond to magnetization and enabling phase-diagram analysis. On the Nishimori line, this mapping connects thermodynamic phases to Bayes-optimal detectability, while its scope does not cover every planted model.

Gauge transformation: The gauge transformation turns the planted assignment into the ferromagnetic all-spins-up configuration and converts overlap with it into magnetization.The transformed model is a standard spin glass with iid interactions and ferromagnetic bias ρ.
Gauge transformation: The transformed model’s nonzero magnetization corresponds to inference better than random guessing, with local magnetizations related to the MMO estimator.The Nishimori line ρ = eβ/(2 cosh β) is the Bayes-optimal condition β = β∗.
Phase diagram: The phase diagram uses temperature and ferromagnetic bias to distinguish spin glass, ferromagnetic, paramagnetic, and mixed phases.For random regular graphs, the illustrated example has degree c = 3; the Nishimori line identifies Bayes-optimal inference.
Bayes-optimal inference: On the Nishimori line, the paramagnetic phase makes inference information-theoretically impossible because the observed couplings contain no useful information about the planted configuration.This occurs for β∗ < βc and ρ < ρc.
Bayes-optimal inference: Above the critical point, the ferromagnetic phase yields configurations correlated with the planted assignment, making inference possible and algorithmically tractable.Monte-Carlo sampling is given as an example of a tractable approach.
Algorithmic consequences: The second-order transition separates impossible inference from tractable inference, whereas mismatched or zero-temperature settings can introduce spin-glass behavior and difficult equilibration.The review states that the hard phase is absent in this planted Ising model but can occur with discontinuous transitions or parameter mismatch.
Scope: Bayes-optimal inference applies more broadly than models admitting this gauge transformation, so the mapping is explanatory rather than universal.The review explicitly notes that similar gauge transformations do not always exist.

1. The quenched and annealed average

The review distinguishes quenched averaging, which averages the logarithm of the partition sum, from annealed averaging, which averages the partition sum first. Their difference matters because rare disorder realizations can dominate annealed quantities, while quiet planting links planted and randomly quenched ensembles when free-energy densities coincide.

Quenched computations average the logarithm of the partition sum, whereas annealed computations average the partition sum before taking its logarithm.The quenched free energy is generally difficult to compute, while the annealed computation is easier but need not agree with it.
Rare, exponentially large fluctuations of the partition sum can make annealed averages differ substantially from typical quenched behavior.In the example, the typical free energy is f_quenched = 2, while the leading annealed value is f_annealed = 1.
The annealed average remains useful because logarithmic concavity yields the inequality underlying many proofs and the first moment method.The annealed computation can also be physically correct when disorder changes rapidly on timescales comparable to configuration changes.
In the planted ensemble, each disorder realization is sampled with probability proportional to its partition sum rather than uniformly.The planted configuration is simultaneously an equilibrium configuration of the posterior-derived Hamiltonian, avoiding the need for a long Monte Carlo equilibration.
Quiet planting occurs when planted and randomly quenched ensembles coincide at the level of free-energy densities, making planted instances statistically typical.Mean-field paramagnets provide a setting where self-averaging quenched and annealed free energies coincide, enabling equilibrium study through planting.

G. No replica symmetry breaking in Bayes-optimal inference.

On the Nishimori line, Bayes-optimal planted systems lack a static equilibrium spin-glass phase, although their dynamics can still exhibit one-step replica symmetry breaking. This property supports exact belief-propagation descriptions of posterior marginals, while mismatched models can develop glassy regions.

Bayes-optimal planted systems have no static replica symmetry breaking at equilibrium on the Nishimori line.The overlap-based definition of a static glass phase is incompatible with the Nishimori-line properties described here.
Belief propagation exactly describes posterior marginals even when a dynamical one-step replica symmetry breaking phase appears.The absence of static glassiness therefore does not imply simple dynamics.
On the Nishimori line, the overlap with the planted configuration equals the overlap between two typical posterior configurations, including their overlap distributions.This provides a direct correspondence between planted-signal alignment and posterior-to-posterior similarity.
In sparse Bayes-optimal systems, two-point correlations decay, whereas they could not decay in a static spin-glass phase.This gives a complementary rigorous argument excluding an equilibrium transition to static glassiness.
Mismatching the prior, model, or parameters opens the possibility of glassiness, with replica-symmetry-breaking regions appearing away from the Bayes-optimal setting.The cited discussion specifically identifies such regions when β ≠ β∗.

C. Properties of the randomly-quenched ensemble

The randomly-quenched Viana–Bray model is analyzed with belief propagation, cavity methods, and population dynamics to characterize its phases and critical behavior. The paramagnetic solution becomes unstable at a threshold, beyond which the Bethe approximation fails and replica-symmetry breaking is required.

The Viana–Bray model is a diluted Ising spin glass on an Erdős–Rényi graph with independently random ±1 interactions.
Belief propagation is iterated on graph instances, while population dynamics approximates the message distribution on an infinite fixed-degree random graph.Population dynamics represents P(u) with a population of M message values and can approximate it to arbitrary precision.
Population dynamics computes the free energy per site from the converged message distribution.
At low β, the model has a stable paramagnetic fixed point with all cavity messages equal to zero; at high β, iterations fail to converge on a single graph, signaling long-range correlations.
The paramagnetic phase becomes unstable when c tanh^2 β ≥ 1, as obtained by analyzing perturbation growth and the spin-glass susceptibility.
For β < βc the paramagnetic fixed point describes the model, whereas for β > βc the Bethe approximation fails and replica symmetry breaking is needed.

D. Phase diagram of the planted spin glass

The planted spin glass exhibits phase-transition structures that determine detectability and algorithmic difficulty. Continuous transitions can make inference tractable once possible, whereas discontinuous transitions create distinct information-theoretic, hard, and easy regimes.

For the planted spin glass, the ferromagnetic transition condition determines when the system polarizes toward the planted configuration.
On the Nishimori line, this transition is exactly the boundary between no detectability and recovery.
At β = atanh(1/√c), the spin-glass, ferromagnetic, and Bayes-optimal conditions meet at a multicritical point.
For Bayes-optimal temperatures above the transition, the planted ensemble is quiet: its paramagnetic fixed point is unique and it matches the randomly-quenched ensemble.
Phase-transition order: The hard phase is absent for the second-order planted Ising spin glass but appears broadly in problems with first-order transitions, including community detection and compressed sensing.
First-order transitions: In first-order transitions, the equilibrium transition marks information-theoretic recovery, but random initialization can trap BP or MCMC in a metastable paramagnetic state.
Planted coloring: Planted coloring has four regimes: undetectable paramagnetic, undetectable clustered, hard detectable, and easy detectable phases separated by cd, cc, and cs.
Constraint satisfaction: For at least 2-transitive constraint satisfaction problems, the hard phase spans the entire region with linearly many constraints, while tractability is predicted at N^(r/2) constraints.

IV. FROM PHYSICS INSIGHT TO NEW ALGORITHMIC IDEAS

The review turns statistical-physics analysis into algorithms for inference, using phase transitions and message-passing structure to guide algorithmic design. It illustrates this program through planted spin glasses, TAP dynamics, spatial coupling, and spectral methods.

Algorithmic contributions: Phase diagrams of planted inference problems motivate algorithmic contributions, illustrated through the planted spin glass model.The review explicitly connects its practical algorithmic question to the statistical-physics analysis of phase transitions.
Algorithmic contributions: Replica and cavity calculations can serve as algorithms as well as tools for analyzing inference phase diagrams.The review traces this perspective to survey propagation and related message-passing methods.
Spectral algorithms: For the non-backtracking matrix, the planted assignment correlates with the leading eigenvector signs when β∗> βc.Below βc, the spectrum remains inside a circle of radius √c; above it, an informative real eigenvalue c tanh β∗ emerges outside the circle.
Algorithmic barriers: The hard detectable phase can block both Monte Carlo and belief propagation in a metastable paramagnetic state, while the spinodal transition remains a barrier for known algorithms.Planted XOR-SAT shows that similar phenomenology does not by itself establish a universal polynomial-time barrier.
Spatial coupling: Spatial coupling seeds a magnetic-field region that produces a nucleation wave invading the system in time proportional to the number of blocks.The construction uses a stronger field in a small seed region and a weaker field elsewhere.
TAP equations: Correct time indices restore TAP convergence on sufficiently dense systems, resolving earlier non-convergence reports outside the glassy phase.State evolution describes the algorithm, and the fixed point gives the replica-symmetric magnetizations and overlap where that solution is correct.

V. CLUSTERING OF NETWORKS AND COMMUNITY DETECTION

The review formulates community detection as Bayesian inference in the stochastic block model and analyzes it through statistical-physics methods. Belief propagation is asymptotically exact in the Bayes-optimal setting, while parameter learning and mismatched inference introduce practical limitations.

Problem formulation: Community detection assigns graph nodes to groups, typically seeking many within-group edges and few between-group edges.The review places this task within the broader clustering problem and contrasts it with spectral-relaxation approaches.
Problem formulation: The sparse stochastic block model specifies group proportions and edge probabilities cab/N, making hidden communities a planted inference problem.Bayesian inference averages over assignments consistent with the model, while statistical physics interprets the averages through a Potts glass.
Bayesian inference: The maximum-mean-overlap estimator is computed from local magnetizations of the corresponding Potts model.This connects the estimator of the planted assignment directly to the statistical-physics representation.
Parameter learning: For unknown model parameters, expectation-maximization learning can depend strongly on initialization and become trapped in a local partition-function maximum.The method iteratively maximizes the partition function while imposing Nishimori conditions.
Finite-size behavior: BP and Gibbs sampling are comparable in the large-size limit, but finite systems can exhibit different fixed-point and convergence behavior.BP may retain distinct fixed points from different initializations even when Gibbs sampling behaves differently.
Bayesian inference: Belief propagation provides an asymptotically exact analysis of Bayes-optimal inference in the stochastic block model.Gibbs sampling and BP are both asymptotically exact for computing marginals and expectations in this setting.

C. Examples of phase transitions in the SBM

The SBM exhibits distinct inference phases whose locations depend strongly on graph structure and group parameters. Equal average degree yields especially clear detectability transitions, while general cases require case-by-case analysis.

Phase structure: Equal average degree across groups is the hardest SBM setting because degree histograms then provide no assignment information.When group degrees differ, degree information can help reveal the communities.
Phase structure: The uniform BP fixed point exists when cabnb = c for every group, enabling quiet planting and the associated phase-transition picture.This condition makes the average degree identical across groups.
Community detectability: When |cin − cout| exceeds the detectability threshold, BP detects communities with asymptotically Bayes-optimal overlap; below it, BP fails.Depending on parameters and transition order, a hard phase can separate detectability from the spinodal threshold.
Community detectability: For planted coloring, the transition is second order for q ≤3 and first order for q ≥4, with spinodal threshold cs = (q −1)2.At large q, cd = q(log q + log log q) + O(1) and cc = 2q log q −log q −2 log 2 + o(1).
Phase-transition scope: When group average degrees differ, BP phase transitions become smeared: second-order transitions disappear and first-order transitions shrink toward a multicritical point.The equal-degree condition is therefore central to the sharp transition picture.

D. Spectral redemption for clustering sparse networks

Linearizing belief propagation yields a non-backtracking spectral method for sparse-network clustering. Its informative eigenvalues match BP thresholds under equal group degrees, while the method also extends beyond the basic SBM setting.

Method: Linearized BP motivates clustering with the non-backtracking matrix defined on directed edges.The method constructs eigenvectors of this operator and uses them to represent and cluster nodes.
Method: The algorithm estimates the number of groups by counting large real eigenvalues before clustering the corresponding node vectors.Node vectors are formed by summing incoming-edge eigenvector components and clustered with methods such as k-means.
Thresholds: The non-backtracking spectrum is bounded by a bulk circle on random sparse graphs, unlike traditional matrices that may be unbounded with constant average degree.This spectral separation supports identifying informative real eigenvalues.
Thresholds: For equal average degree, non-backtracking eigenvalues outside the bulk carry community information and coincide with the BP spinodal threshold.In the assortative case, the informative eigenvalue is (cin − cout)/q and merges into the bulk below the spinodal transition.
Comparisons: Compared with BP, non-backtracking spectral clustering needs neither model parameters nor the number of groups and runs in time linear in the number of groups.BP achieves slightly better overlap, whereas the spectral method offers these computational and information requirements advantages.
Extensions: The method generalizes to sparse hypergraphs and planted constraint-satisfaction problems, including cases where the constraint form is unknown.The review also describes applications to matrix completion and percolation.
Real networks: On benchmark real networks, non-backtracking spectra retain properties derived for the SBM, detecting communities with overlap comparable to other spectral methods.The number of real eigenvalues outside the bulk appears to indicate the number of communities.

VI. LINEAR ESTIMATION AND COMPRESSED SENSING

Linear estimation infers an unknown vector from noisy, possibly nonlinear element-wise transformations of known linear measurements. The review connects Bayesian formulations, sparse priors, compressed sensing, and message-passing algorithms.

Generalized linear estimation: Linear estimation recovers an unknown N-dimensional vector from M observations generated through a known matrix and output function.The goal is to infer x from y, F, and fout, which may include additive noise or thresholding.
Sparse estimation: LASSO promotes sparse coefficients through an ℓ1-based fit-sparsity trade-off that can be solved efficiently by linear programming.Its regularization parameter λ controls the balance between data fit and sparsity.
Bayesian methods: Bayesian statistical-physics methods extend beyond convex relaxations to sparsity-inducing priors that linear programming cannot handle.The framework is presented for generalized linear estimation, although tractable analyses focus mainly on random matrix classes.
Compressed sensing: Compressed sensing seeks accurate signal recovery from fewer measurements because many signals are compressible and acquisition costs can be substantial.Applications include medical imaging, where reducing measurement time, cost, or radiation exposure is desirable.
Compressed sensing: ℓ1 reconstruction exactly recovers signals with probability one above the Donoho-Tanner line α > αℓ1(ρ) > ρ in the large-system limit.Here ρ = K/N is signal density and α = M/N is the measurement rate.
Message passing: Approximate message passing provides the algorithmic route linking statistical-physics analyses to linear estimation and compressed sensing.Its generalized form accommodates arbitrary element-wise output functions.

2. From r-BP to G-AMP

G-AMP is obtained by simplifying belief-propagation messages while preserving their leading-order marginal behavior. The resulting iterative algorithm uses means, variances, and matrix multiplications, with an Onsager correction important for convergence.

From r-BP to G-AMP: Weak dependence of messages on the target node allows r-BP to simplify into TAP-like equations without changing leading-order marginals.The simplification is the transition from standard belief propagation to TAP equations.
G-AMP equations: G-AMP tracks variable means a_i and variances c_i while conserving the leading-order behavior of approximate posterior marginals.Its derivation starts from the message-passing representation and preserves the relevant marginal quantities.
Algorithm: The G-AMP procedure initializes y, a0, v0, and g0, then iteratively updates estimated marginals until convergence.The algorithm outputs the converged a and v values.
Convergence: The Onsager reaction term uses the previous iteration index t − 1, a feature described as crucial for convergence.The updates can be implemented entirely with matrix multiplications, facilitating fast linear-algebra implementations.

3. The potential

The G-AMP potential is tied to Bethe free energy and supports analysis of both algorithmic fixed points and inference performance. In idealized random-matrix settings, convergence and state evolution connect the algorithm to asymptotic Bayes-optimal error.

The potential: Belief-propagation equations can be interpreted as minimizing a Bethe free energy through a variational formulation.The associated distributions involve Kullback-Leibler divergences and fixed-point normalization terms.
Performance and convergence: When G-AMP converges, its mean-squared-error performance is usually considerably better than that of other existing algorithms.The cited convergence guarantees apply to large systems with random iid matrices and matched or convex-relaxation priors.
Performance and convergence: AMP convergence is not guaranteed for mismatched signal distributions, non-random matrices, or other settings outside the idealized assumptions.The review motivates robustness research because finite-size mismatch and matrix structure can destabilize iterations.
Stabilization: Adaptive damping, sequential updates, mean removal, and parameter learning together form a state-of-the-art G-AMP implementation.These features are introduced to stabilize iterations while retaining performance and speed.
State evolution: State evolution analyzes AMP performance in the large-size limit for matrices with independent entries and has rigorous results for AMP and G-AMP.In the Bayes-optimal case, it yields the asymptotic minimum mean-squared error.
State evolution: For an AMP estimator, the mean-squared error is MSE = ρx^2 − m_t and can be evaluated by iterating state evolution from an uninformed initialization.The initialization is m_t=0 = ρ^2x^2.

2. Free energy

The potential analysis reveals phase transitions separating information-theoretic recovery from algorithmically accessible recovery. For compressed sensing, spatial coupling removes the algorithmic barrier and enables AMP to reach the information-theoretic threshold.

Phase transitions: AMP reconstruction exhibits a first-order transition whose location depends on the distribution of nonzero signal elements.The transition is plotted against signal density ρ and measurement rate α = M/N.
Phase transitions: The Bayesian spinodal transition is better than the ℓ1 transition for the considered signal distributions, although no generic proof is given.The comparison concerns the measurement-rate threshold for reconstruction.
Phase transitions: Binary perceptron recovery becomes information-theoretically possible above α ≈ 1.245, while G-AMP succeeds only beyond α ≈ 1.49.These thresholds illustrate distinct information and algorithmic transitions.
Algorithmic barriers: For the unchanged compressed-sensing graphical model, the first-order transition creates a barrier conjectured to be unbeatable by polynomial-time algorithms.The barrier separates efficient recovery from the information-theoretic limit.
Spatial coupling: Spatially coupled measurement matrices allow AMP to reconstruct whenever α > ρ, reaching the information-theoretic limit; threshold saturation was later proven rigorously.The matrix uses a block-structured variance pattern.
Spatial coupling: Spatial coupling removes the spinodal transition by using a higher-rate first block as a nucleation seed whose effect propagates through neighboring blocks.This mechanism mirrors spatial coupling in the Curie-Weiss model.
Applications: Spatially coupled sparse superposition codes with AMP are reported to be fast, reliable, and capable of reaching the Shannon limit for the AWGN channel as L becomes large.These codes use an L-dimensional constrained-variable version of the compressed-sensing setting.

F. Non-random matrices and non-separable priors

The review extends statistical-physics inference beyond idealized settings through structured priors and non-random measurement matrices, while identifying gaps between optimal predictions and current algorithms. Applications and broader analysis show both practical promise and substantial robustness challenges.

Non-separable priors: Structured priors can improve AMP by incorporating information about correlations or signal-support patterns.Examples include hybrid AMP and restricted Boltzmann machines used to model structured signal classes.
Non-random matrices: Non-random measurement matrices are important because ℓ1-minimization works for a broader matrix class than random matrices.The review highlights extensions of statistical-physics approaches toward correlated and more general matrix ensembles.
Applications: Belief propagation within belief propagation yields a fast CT reconstruction method with better reconstruction and noise robustness than competing convex-relaxation algorithms.The approach exploits the fact that a one-dimensional line is a tree, allowing exact partition-function computation with belief propagation.
Applications: The reviewed techniques can estimate a strongly scattering material’s full complex-valued transmission matrix up to a global phase using real-valued inputs and outputs.The result illustrates an application of the inference techniques beyond their idealized theoretical settings.
Matrix factorization: Matrix factorization admits both AMP and replica analyses, and relevant cases show ideal performance substantially exceeding that of current algorithms.This gap suggests considerable room for improving algorithmic efficiency, while phase transitions may separate information-theoretic and algorithmic thresholds.
Limitations and challenges: Message-passing algorithms often rely on correlation-decay assumptions that rarely hold on real datasets, sometimes causing algorithmic failure.The review identifies robustness and adaptation to generic problems as important unresolved challenges.