PaperlayerView exact revision on arXiv

Source-linked AI summary

The dynamics of message passing on dense graphs, with applications to compressed sensing

Mohsen Bayati, Andrea Montanari

arXiv:1001.3448v4cs.ITcs.LGmath.ITmath.STstat.TH

TL;DR

AMP was effective for sparse-signal reconstruction, but state evolution had been supported by heuristics and simulations. This paper proves state evolution in the large-system limit for Gaussian sensing matrices using a conditioning-based analysis, establishing it for dense-graph algorithms despite their short loops.

  • Problem

    State evolution had been supported by heuristic arguments and simulations, while AMP reconstruction dynamics motivated a rigorous large-system result.

    Source: §1 · pp. 1–2

  • Method

    The proof uses Gaussian conditioning to analyze AMP despite the dependence between the iterates and the fixed sensing matrix.

    Source: §1.3 · p. 5, §3.1 · p. 11

  • Results

    State evolution holds asymptotically in the large-system limit for random sensing matrices with Gaussian entries.

    Source: §1 · p. 2

  • Takeaways & Limitations

    State evolution is an analogue of density evolution for dense graphs, whose factor graph is complete bipartite rather than locally tree-like.

    Source: §1 · pp. 2–3

    Theorem 1 does not cover the β → ∞ case because it corresponds to the discontinuous function ηt(x) = sign(x).

    Source: §2.3 · p. 10

Abstract

from arXiv · show

Approximate message passing algorithms proved to be extremely effective in reconstructing sparse signals from a small number of incoherent linear measurements. Extensive numerical experiments further showed that their dynamics is accurately tracked by a simple one-dimensional iteration termed state evolution. In this paper we provide the first rigorous foundation to state evolution. We prove that indeed it holds asymptotically in the large system limit for sensing matrices with independent and identically distributed gaussian entries. While our focus is on message passing algorithms for compressed sensing, the analysis extends beyond this setting, to a general class of algorithms on dense graphs. In this context, state evolution plays the role that density evolution has for sparse graphs. The proof technique is fundamentally different from the standard approach to density evolution, in that it copes with large number of short loops in the underlying factor graph. It relies instead on a conditioning technique recently developed by Erwin Bolthausen in the context of spin glass theory.

1 Introduction and main results

The paper gives rigorous asymptotic support for state evolution in AMP with Gaussian sensing matrices and extends the analysis to a broader class of algorithms on dense graphs. It frames state evolution as the dense-graph analogue of density evolution and addresses graph structures with many short loops.

1 Introduction and main results

  • State evolution holds asymptotically for AMP with Gaussian sensing matrices, providing rigorous support for findings previously based on heuristics and numerical simulations.The proof also overcomes the locally tree-like limitation of standard density-evolution arguments for dense graphs.Source: §1 · pp. 2–3

1.4 Related literature

  • State evolution is the dense-graph analogue of density evolution, and the analysis also applies to broader message-passing algorithms, including multi-user detection.The paper connects its results to replica-method analyses and a specific decoupling principle.Source: §1 · p. 2, §1.4 · p. 7

1.1 Main result

  • Theorem 1 formalizes AMP state evolution under Gaussian sensing, signal and noise moment conditions, with scalar-Gaussian variables specifying the limiting behavior.The setting assumes n/N converges to a positive finite value.Source: §1.1 · p. 4

1.2 Universality

  • The proof relies heavily on Gaussian matrix entries; broader universality is expected, but its domain remains an open problem.State evolution is proved for affine denoisers in a broader class of random matrices.Source: §1.2 · p. 4

1.3 State evolution: the basic intuition

  • With the matrix fixed across iterations, correlations between A and the iterates matter; the Onsager term asymptotically cancels them, unlike iterative soft thresholding.State evolution does not hold for iterative soft thresholding, even in the large-system limit.Source: §1.3 · p. 6

2 Examples

State evolution turns the theorem into predictions for estimation error across linear estimation, sparse-signal recovery, and multi-user detection. These examples also connect AMP’s performance to established estimators and extend the state-evolution setting to dense signatures.

2 Examples

  • State evolution predicts AMP’s mean square error and, more generally, ℓp distances for p ≤ k.The examples apply Theorem 1 to specific observables.Source: §2 · p. 7

2.1 Linear estimation

  • For a Gaussian signal prior, optimal AMP uses linear scalar estimators and is asymptotically equivalent to the MMSE linear estimator.The state-evolution prediction also suggests a route to deriving the Marcenko-Pastur law from the MMSE as a function of noise variance [MP67].Source: §2.1 · pp. 7–8

2.2 Compressed sensing via soft thresholding

  • For soft thresholding, state evolution predicts asymptotic MSE and identifies a threshold choice yielding the best AMP algorithm for worst-case sparse-vector estimation.The choice is close to scalar minimax-optimal soft thresholding for very sparse sources; state evolution also offers a minimax approach to adapting nonlinearities to signal classes.Source: §2.2 · p. 9

3 Proof

The proof adapts Bolthausen’s conditioning technique, together with Gaussian conditioning and linear-algebra tools, to establish a general recursion result that recovers AMP as a special case. Its induction establishes the base and later-step properties for the sequences B_t and H_{t+1}, including Gaussian variance limits and covariance identities.

3.1 The conditioning technique: an informal description

  • Conditioning on past iterates turns the matrix observations into linear constraints; Gaussian conditioning and cancellation of the non-Gaussian term with −λtmt−1 yield Gaussianity.Rather than finding the conditional distribution of the iterate given the matrix, the method characterizes the matrix given the observed history; triangular-array strong laws control the remaining terms.Source: §3.1 · p. 11

3.2 A general result

  • Under the stated Gaussian-matrix and empirical-distribution assumptions, Theorem 2 gives almost-sure pseudo-Lipschitz convergence to quantities determined by state evolution.The limiting variables include independent X0 and W and a standard Gaussian Z; the state-evolution recursion determines σt and τt.Source: §3.2 · p. 12

3.3 Corollary of Theorem 2: AMP and Theorem 1

  • The AMP algorithm is a special case of the general recursion, and Theorem 1 follows by applying Theorem 2 with the Lipschitz denoiser.The transformed test function remains pseudo-Lipschitz, allowing Theorem 2 to give the claimed almost-sure limit.Source: §3.3 · p. 12, §3.4 · p. 13

3.5 Definitions and notations

  • The proof conditions on a filtration of previously computed iterates to characterize the conditional laws of bt and ht+1, using projection coefficients with finite limits.The filtration includes the initial signal and noise, and the method characterizes the matrix conditional on this history.Source: §3.5 · pp. 13–14

3.6 Main technical Lemma

  • The main technical lemma establishes Gaussian-coordinate empirical behavior and bounded, deterministic limits, and its part (b) yields Theorem 2.The proof of Theorem 2 applies the lemma to functions derived from the test function ψ.Source: §3.6 · pp. 14–15, §3.6.1 · p. 16

3.7 Useful probability facts

  • Gaussian-sequence probability facts provide conditional-variance formulas and bounds under positive conditional variances, moment bounds, and a nonconstant Lipschitz function.These facts support the later induction arguments.Source: §3.7 · p. 17

3.7.1 Linear algebra facts

  • Linear-algebra lemmas show that lower bounds on successive vector components orthogonal to earlier spans control the Gram matrix’s smallest eigenvalue, and that this bound persists in an elementwise limit.The limit claim assumes the matrices’ smallest eigenvalues are eventually bounded below by a positive constant.Source: §3.7.1 · pp. 17–18

3.8 Conditional distributions

  • Conditioning on A Q_{t1} and A* M_{t2} yields a conditional law for A described by its conditional expectation and a projected independent Gaussian matrix.The conditional-distribution result applies when (t1, t2) is (t, t) or (t + 1, t); the proof applies a Gaussian conditioning formula to the linear constraints.Source: §3.8 · p. 18

3.8.1 Proof of Lemma 11

  • The proof of Lemma 11 obtains the conditional expectation by minimizing the Frobenius norm subject to the linear constraints, then verifies the projected residual operator.The Lagrange-multiplier equations need not uniquely determine their parameters, but yield the stated conditional expectation.Source: §3.8.1 · pp. 19–20

3.9 Proof of Lemma 1

  • The proof of Lemma 1 proceeds by induction, establishing base properties and then deriving B_t and H_{t+1} from earlier B and H properties.The induction is organized into four main steps and tracks several properties from Lemma 1.Source: §3.9 · p. 20

3.9.1 Step 1: B0

  • The base case B_0 uses Gaussian independence, moment bounds, and limit theorems to establish empirical convergence and the associated derivative identity.The empirical distribution of (b_0, w) converges to that of (σ_0 Z, W), and the proof derives the corresponding identity involving ϕ′.Source: §3.9.1 · pp. 20–22

3.9.2 Step 2: H1

  • For H_1, the proof establishes weak convergence of the empirical distribution of (h_1, x_0) to (τ_0 Z, X_0) and the corresponding derivative identity.It also shows that the squared norm of h_1 converges almost surely to τ_0^2.Source: §3.9.2 · pp. 23–24

3.9.3 Step 3: Bt

  • For B_t, the proof uses lower eigenvalue bounds to control inverse matrices and invokes Gaussian conditional-variance bounds to establish the needed positive variances.The argument relies on the induction hypotheses for earlier B and H properties.Source: §3.9.3 · pp. 24–25
  • For B_t, induction establishes finite limits for normalized q-vector quantities and verifies the Gaussian variance σ_t^2, with covariance limits linked to inner products of b-vectors.The proof also derives the covariance identity using jointly Gaussian variables and the induction hypotheses.Source: §3.9.3 · pp. 30–31

3.9.4 Step 4: Ht+1

  • For H_{t+1}, induction establishes the Gaussian variance τ_t^2 and relates covariance limits to inner products of h-vectors.The variance is verified through the limiting second moment of g_t(b_t, w), while the covariance argument uses jointly Gaussian variables.Source: §3.9.4 · p. 33

3.10 Proof of Corollary 1

The proof reduces the corollary to checking convergence for products of bounded Lipschitz test functions. This check follows from Theorem 1.

3.10 Proof of Corollary 1

  • It is sufficient to verify the claim for test functions that factor into products of functions of paired coordinates.The component functions ψ_i are bounded and Lipschitz.Source: §3.10 · pp. 33–34
  • Theorem 1 supplies this factorized-test-function case, completing the proof.Source: §3.10 · p. 34

4 Symmetric Case

The symmetric-case analysis studies an iteration built from a symmetric Gaussian matrix and a Lipschitz function. Its stated asymptotic conditions include a limiting inner-product identity, and the proof uses the conditioning technique from Theorem 2.

4 Symmetric Case

  • The symmetric-case theorem considers an iteration with G = A* + A, Gaussian matrix entries, a Lipschitz function f, and deterministic initialization.The setup specifies m_0 = 0 and a fixed deterministic m_1.Source: §4 · p. 34
  • Bolthausen had proved the theorem for f(x) = tanh(βx+h) with ⟨m_1,m_1⟩ = τ².Source: §4 · p. 34
  • The proof is described as similar to the proof of Theorem 2 and uses the same conditioning trick.The authors omit the proof to avoid repetition.Source: §4 · p. 34

A AMP algorithm: An heuristic derivation

This appendix heuristically derives the AMP iteration from standard message passing to build intuition; the derivation is explicitly not used in the proof of Theorem 1.

A AMP algorithm: An heuristic derivation

B Strong law of large number for triangular arrays

The section verifies conditions from Hu and Taylor to establish an almost-sure strong law for a triangular array.

B Strong law of large number for triangular arrays

C Proof of Lemma 2

The proof reduces the lemma to an inequality and establishes it by showing that the relevant function decreases.

C Proof of Lemma 2

D Proof of probability and linear algebra lemmas

The appendix provides proofs of two probability lemmas stated in Section 3.7.

D.1 Proof of Lemma 5

The proof establishes convergence by truncating the test function and controlling the discarded tail with the assumed bounded kth moment.

D.1 Proof of Lemma 5

  • Truncating the pseudo-Lipschitz function yields a bounded continuous function to which weak convergence applies.The proof decomposes ψ into ψ_B and its remainder.Source: §D.1 · pp. 38–39
  • The assumed convergence of kth moments and dominated convergence make the remainder's expected tail vanish as B grows.The pseudo-Lipschitz growth bound controls the tail by a function dominated by L(1 + |V|^k).Source: §D.1 · p. 39

D.2 Proof of Lemma 6

The proof uses a Skorokhod coupling to establish almost-sure convergence of the derivatives, then bounded convergence to obtain convergence of their expectations.

D.2 Proof of Lemma 6

  • A Skorokhod construction gives almost-sure convergence of the paired random variables, and absolute continuity places the limit in F's differentiability domain almost surely.Source: §D.2 · p. 39
  • The coupled derivatives converge almost surely and are bounded because F is Lipschitz, so their expectations converge by bounded convergence.Source: §D.2 · p. 39

D.3 Proof of Lemma 8

The proof argues by contradiction: failure would force a degeneracy in the Gaussian vector that conflicts with the assumed positive conditional variance.

D.3 Proof of Lemma 8

  • A hypothetical failure yields a covariance matrix for which the matrix of expected products of ℓ(Z_i, Y) is singular.The proof obtains this implication using the Schur complement formula.Source: §D.3 · p. 40
  • Singularity forces a nontrivial linear dependence among the ℓ(Z_i, Y), which implies a degenerate Gaussian vector and contradicts the positive conditional variance assumption.The Lipschitz combination is nonconstant, so it is nonzero on a set of positive Lebesgue measure.Source: §D.3 · p. 40

D.4 Proof of Lemma 9

The proof proceeds by induction over t, using Gram–Schmidt orthonormalization to establish the thesis from a bound on the resulting triangular matrix.

D.4 Proof of Lemma 9

  • The proof establishes the thesis by induction over t, taking the case t = 1 as trivial and assuming the claim for t − 1 vectors.The vectors are assumed to satisfy ∥vi∥2/n ≤ K for a constant K independent of n.Source: §D.4 · p. 40
  • For V with columns v1, . . . , vt, the proof writes C = V ∗V/n and uses Gram–Schmidt to construct an upper-triangular A and orthonormal U satisfying U = V A.The columns ui of U are defined as the orthonormalized vectors.Source: §D.4 · p. 40
  • The proof concludes that σmax(A) ≤ c′′′n−1/2, with c′′′ depending on n, and invokes Eq. (D.4) to obtain the thesis.Source: §D.4 · p. 41

Related papers

Loading 1001.3448v4…