PaperlayerView exact revision on arXiv

Source-linked AI summary

Universality in polytope phase transitions and message passing algorithms

Mohsen Bayati, Marc Lelarge, Andrea Montanari

arXiv:1207.7321v2math.PRcs.IT

TL;DR

The paper asks whether high-dimensional approximate message passing behavior and an associated polytope phase transition are universal beyond Gaussian matrices. It proves universality for polynomial AMP iterations using state-evolution analysis, and applies the result to polytope geometry and compressed sensing. The theorem covers broad random-matrix classes under sub-Gaussian and related assumptions, resolving a Donoho–Tanner conjecture.

  • Problem

    The paper investigates whether the high-dimensional behavior of approximate message passing and a related polytope phase transition remains insensitive to matrix-entry distributions beyond the Gaussian setting.

  • Method

    The paper analyzes polynomial AMP iterations, using an Onsager-inspired memory term, universality comparisons, and state evolution, with rectangular cases handled through a symmetric-matrix reduction.

  • Results

    The paper proves asymptotic universality of AMP finite-dimensional marginals and uses state evolution to establish universality of a polytope phase transition for broad random matrices.

  • Takeaways & Limitations

    The results provide a rigorous route for transferring Gaussian asymptotics to broad classes of random matrices and resolve a Donoho–Tanner conjecture on polytope neighborliness.

  • Takeaways & Limitations

    The polytope-neighborliness theorem assumes sub-Gaussian entries and an arbitrarily small Gaussian component, with the latter appearing to be a proof artifact for the lower bound.

Abstract

from arXiv · show

We consider a class of nonlinear mappings $\mathsf{F}_{A,N}$ in $\mathbb{R}^N$ indexed by symmetric random matrices $A\in\mathbb{R}^{N\times N}$ with independent entries. Within spin glass theory, special cases of these mappings correspond to iterating the TAP equations and were studied by Bolthausen [Comm. Math. Phys. 325 (2014) 333-366]. Within information theory, they are known as "approximate message passing" algorithms. We study the high-dimensional (large $N$) behavior of the iterates of $\mathsf{F}$ for polynomial functions $\mathsf{F}$, and prove that it is universal; that is, it depends only on the first two moments of the entries of $A$, under a sub-Gaussian tail condition. As an application, we prove the universality of a certain phase transition arising in polytope geometry and compressed sensing. This solves, for a broad class of random projections, a conjecture by David Donoho and Jared Tanner.

1. Introduction and main results.

The paper establishes universality for polynomial approximate message passing iterations and uses state evolution to analyze their high-dimensional behavior. It applies these results to prove universality of a polytope phase transition connected to compressed sensing for broad classes of random matrices.

  • Universality: As N →∞, finite-dimensional marginals of the AMP iterates become asymptotically insensitive to the distribution of matrix entries.The comparison concerns polynomial AMP instances whose matrix distributions differ while matching the required first two moments and regularity conditions.
  • State evolution: The iterates’ entries are asymptotically Gaussian with zero mean, with variance computed by a one-dimensional state-evolution recursion.State evolution characterizes the covariance structure of low-dimensional marginals in the high-dimensional limit.
  • Phase transitions in polytope geometry: The paper proves universality of a polytope phase transition for a broad class of random matrices with independent sub-Gaussian entries.The result extends beyond Gaussian matrices and addresses a conjecture by Donoho and Tanner.
  • AMP iteration: The memory term cancels leading correlations in the iteration by removing contributions from one-step-reversing trees.Without this term, the iterates are no longer approximately Gaussian as N →∞.
  • Phase transitions in polytope geometry: Polytope neighborliness is linked to sparsity-seeking methods for underdetermined linear systems, including compressed sensing.In high dimensions, natural random constructions can have neighborliness scaling linearly with dimension.
  • AMP iteration: The framework generalizes to rectangular matrices through a reduction that embeds a rectangular matrix as a submatrix of a symmetric matrix.This extension is needed for the application to high-dimensional polytope geometry.

2. Universality of iterative algorithms: Sketch of main ideas.

The sketch explains how memory terms remove reversing-path contributions so polynomial AMP iterates match a Gaussian state-evolution prediction. A moment argument then establishes dependence only on the first two matrix-entry moments.

  • Without the memory term, reversing paths create a nonzero mean and produce Gaussian behavior inconsistent with the state-evolution prediction.At t = 2, the no-memory iterate converges to a Gaussian with mean 1 and variance 1, whereas state evolution predicts zero mean.
  • The memory term cancels one-step reversing paths, leaving residual terms that match the prediction of state evolution.For the linear example, the iteration becomes x_t+1 = A x_t − x_t−1.
  • For polynomial functions, coordinate expansions are indexed by rooted trees, with the proof using nonreversing-tree representations and auxiliary sequences.The argument introduces quantities z_t and y_t to compare the original iterates with message-passing processes.
  • The moment method shows that only terms where each matrix entry has degree at most two contribute, so the limiting distribution depends only on the first two moments.This establishes insensitivity to the detailed distribution of the independent matrix entries under the stated assumptions.

3. Notations and basic simplifications.

The notation section formalizes vectors, matrices, partitions, and converging AMP instances, while simplifying the proof by reducing auxiliary variables to Gaussian, Y-independent coordinates. The same construction embeds rectangular matrices into symmetric ones.

  • Vectors are treated as columns, transposes and norms use standard notation, and coordinates are indexed through [m] and componentwise vector representations.The section defines ℓp norms for vectors and corresponding operator norms for matrices.
  • The proof may assume Gaussian auxiliary variables and functions independent of Y by enlarging the state dimension and refining the partition.The resulting iteration preserves the original coordinates while tracking the auxiliary variables in additional coordinates.
  • Rectangular random matrices are covered by embedding them as submatrices of larger symmetric matrices, with only an immaterial overall rescaling.The enlarged construction preserves the original iteration on the relevant coordinates.

4. Proofs of Theorems 3 and 4.

The proofs establish universality for polynomial AMP iterations by representing iterates with tree expansions, comparing auxiliary recursions, and deriving state-evolution limits under regularity assumptions.

  • Proof strategy: The analysis introduces auxiliary message-passing sequences whose tree representations organize the polynomial dependence of iterates on matrix entries.The tree families encode vertex types, marks, generations, and nonbacktracking constraints.
  • Universality: Proposition 1 establishes universality of moments for polynomial AMP message variables when matrix distributions differ but match the required first two moments.The comparison applies to (C,d)-regular polynomial AMP sequences.
  • Proof strategy: An independent-matrix recursion has particularly simple state evolution and provides a good approximation to the original message-passing recursion.Proposition 2 formalizes the approximation through moment bounds with constants independent of N.
  • Proof strategy: The AMP orbit is linked to the message variables through further approximation bounds, with constants independent of N for fixed iteration and moment parameters.These bounds support transferring asymptotic conclusions from the auxiliary recursions to the AMP sequence.

5. Nonsymmetric matrices.

The paper extends AMP analysis to bipartite, nonsymmetric instances by reducing them to symmetric ones, then proves a state-evolution description for their trajectories.

  • State evolution: The nonsymmetric setting is introduced as a special case of the broader framework, with two positive-semidefinite covariance recursions and an additional two-times recursion.These recursions provide the state-evolution quantities used to characterize coordinates at one or two iteration times.
  • Instance and orbit: Bipartite AMP instances use independent rectangular matrix entries, polynomial componentwise functions, and independent Gaussian-mixture vertex labels.The matrix has mean-zero, variance-controlled sub-Gaussian entries; the orbit consists of coupled vectors updated through linear operators and nonlinearities.
  • State evolution: Theorem 6 states that fixed-time AMP observables converge to expectations under jointly Gaussian effective variables with covariances determined by state evolution.For distinct iteration times, the initial condition requires an additional finite-mixture-of-Gaussians assumption, and the Gaussian variables are independent of the corresponding labels.
  • Reduction to symmetry: The proof embeds each bipartite instance into a symmetric instance whose orbit contains the bipartite orbit, then applies the symmetric universality theorem.The construction partitions the indices into two blocks, assigns block-specific labels, and encodes the rectangular matrix through a symmetric block structure.
  • Scope: The construction leaves one nonlinear definition unused because its value is irrelevant to the purposes of the argument.This is an explicit scope boundary of the instance specification, not a claim about the full algorithmic dynamics.
  • Stability: Gaussian perturbations change AMP trajectories continuously: for every fixed iteration, the perturbed and unperturbed orbits remain controlled by a constant independent of dimension.The proof uses polynomial tree representations and preserves sub-Gaussian scaling after adding an independent Gaussian matrix.

6. Proof of universality of polytope neighborliness.

The paper connects AMP state evolution to ℓ1 recovery and polytope neighborliness, proving a sharp threshold for random sub-Gaussian sensing matrices under specified assumptions.

  • Compressed sensing connection: Compressed sensing reconstructs x0 from underdetermined observations y = Ax0 by solving an ℓ1 convex program, and recovery depends on the support of x0.This support-based recovery event is closely related to the neighborliness of the associated random polytope.
  • Polytope neighborliness: The theorem implies the Donoho–Tanner weak-neighborliness characterization through randomized supports, monotonicity in support size, and concentration arguments.The proof translates high-probability recovery statements into fractions of successful supports and then invokes the neighborliness theorem.
  • Assumptions: Theorem 8 assumes independent sub-Gaussian sensing entries with mean zero, variance 1/m, and an independent Gaussian component, covering both identically and non-identically distributed cases.The signal may be fixed with asymptotic sparsity ratio ρ or have independent entries whose nonzero probability is ρδ.
  • Phase transition: ρ < ρ∗(δ) yields ℓ1 success with high probability, whereas ρ > ρ∗(δ) yields failure with high probability.The probability is over the sensing matrix and, in the random-signal case, the signal itself.
  • Proof strategy: AMP analysis supplies the subgradient and singular-value conditions needed for successful ℓ1 recovery below the threshold.Above the threshold, the iterative construction produces a feasible vector with smaller ℓ1 norm, ruling out recovery of x0.

APPENDIX A: PROOFS OF PROPOSITIONS 6 AND 7

Appendix A proves the propositions by applying the general AMP theorem, after extending it to polynomial versions of the reconstruction iteration.

  • Proof reduction: The appendix derives Propositions 6 and 7 from Theorem 6 using a corollary for iterations with general polynomial nonlinearities.This bridges the reconstruction recursion and the polynomial AMP framework required by the main theorem.
  • Setup: The proof begins with the measurement relation y = Ax0 for vectors and matrices satisfying the stated hypotheses.This initializes the appendix’s reformulation of the reconstruction problem in AMP-compatible variables.

A.1. A general corollary.

The general corollary rewrites the reconstruction iteration as polynomial AMP and identifies a recursively defined Gaussian state evolution governing fixed-time observables.

  • Polynomial reformulation: The construction rescales the signal using the diagonal matrix of squared column norms and then iterates polynomial coordinatewise nonlinearities.The transformed initialization and auxiliary variables put the recursion into the AMP form used by the general theorem.
  • State evolution: A doubly indexed state-evolution array is defined recursively from Gaussian variables whose covariance entries are the array elements themselves.The boundary condition is eR0,0 = E{X2}/δ, and the recursion uniquely determines all eRs,t.
  • Convergence: For fixed iteration times and Lipschitz test functions, the AMP observables converge in probability to expectations over the signal distribution and correlated Gaussian variables.The Gaussian covariance is supplied by the recursively defined state-evolution array.
  • Proof matching: The proof matches the transformed recursion to the bipartite AMP theorem by choosing labels, linear operators, and an initial condition that encode the reconstruction problem.The resulting limits coincide with the appendix’s state-evolution equations after redefining the test function.

A.2. Proofs of Propositions 6 and 7.

The proofs construct polynomial approximations and associated state-evolution orbits, then combine probabilistic convergence estimates across increasing instance sizes to establish the propositions.

  • Polynomial construction: The argument uses weighted polynomial approximation to construct polynomials satisfying the required state-evolution relations.Theorem 9 supplies polynomial approximations, with approximation accuracy controlled by a small parameter ξ.
  • Convergence at fixed depth: For fixed iteration depth, the proof applies the main convergence corollary to the constructed polynomial dynamics.The propositions are proved for t in a fixed finite range, with Proposition 7 following by the same construction.
  • Diagonalization: A diagonal construction selects increasing instance sizes and assigns each size range an orbit whose approximation error tends to zero.The sequence βℓ tends to zero, and the sizes nℓ are chosen sufficiently large so the desired bounds hold with probability at least 1−βℓ.
  • Error control: The remaining covariance and variance estimates follow by choosing ξ sufficiently small and then letting the approximation index grow slowly.The proof closes using bounds on σ²_t and a triangular-inequality argument.
  • Moment bounds: Tree representations and edge-counting bounds control the relevant expectations by showing that nonvanishing contributions have sufficiently negative powers of n.Identifying repeated tree vertices yields a graph whose edges must be covered multiple times for the expectation to be nonzero.

APPENDIX B: PROOF OF LEMMA 5

The proof establishes the recovery claim by comparing a minimizer with a subgradient certificate and controlling its error through restricted matrix properties.

  • Subgradient setup: The proof sets the recovery error to r ≡ bx−x0 and uses a subgradient v associated with the support of x0.On the support S, the subgradient equals sign(x0,i), while on the complementary set it is bounded in magnitude by one.
  • Block decomposition: Partitioning S(c) into ordered blocks permits the error to be controlled blockwise using the assumptions on A and the support structure.The blocks have sizes between n^c/2 and n^c when such a partition exists.
  • Restricted matrix control: The restricted singular-value assumption gives σmin(AS+) ≥ c2, which is used together with the preceding bounds to control the residual.The resulting inequality is ∥r∥2 ≤ C2ε∥r∥2.
  • Exact recovery: If C2ε < 1, the self-bounding inequality forces r = 0, proving exact recovery.The proof chooses ε0 = 1/[2C2(c1,c2,c3)] to ensure this condition.

APPENDIX C: ASYMPTOTIC ANALYSIS OF STATE EVOLUTION: PROOF OF LEMMA 6

This appendix analyzes the state-evolution recursion through auxiliary functions Gε and F, characterizing their minima and relating them to the phase boundary.

  • State evolution: The state evolution is expressed using expectations over a sparse variable X and an independent standard Gaussian Z.The function F depends on the signal distribution pX and enters the recursion for σ²_t.
  • Recursion geometry: The state-evolution map is monotone increasing and concave in σ² for fixed threshold scaling.These properties are supplied by Lemma 7 and support the subsequent asymptotic analysis.
  • Properties of Gε: The function Gε is strictly convex, has a unique minimizer α∗(ε), and diverges as α approaches infinity.Its minimum is therefore attained at a unique finite threshold.
  • Boundary derivation: The appendix derives the phase boundary relation by comparing the minimizer of Gε with the state-evolution characterization.The coordinate change from (ρ,δ) to (δ,ε) is used for the analysis.
  • Phase boundary: The phase boundary is characterized by whether ρ exceeds ρ∗(δ), equivalently through an inequality involving Gε and δ.Lemma 9 states the equivalence for ρ,δ ∈[0,1] with δ∈(ε,1).

C.1. Proof of Lemma 6(a): ρ < ρ∗(δ).

For ρ<ρ∗(δ), the state evolution is studied through normalized covariances and limiting threshold functions, yielding convergence properties of the recursion.

  • Auxiliary map: The auxiliary function Fα,ε is increasing and convex, with Fα,ε(1)=1, supporting the fixed-point argument.Its monotonicity and convexity are established through the Ornstein–Uhlenbeck representation.
  • Covariance dynamics: The analysis defines normalized covariances Qt ≡ Rt,t−1/(σtσt−1) and uses Gaussian representations to track their evolution.The covariance variables satisfy |Qt|≤1 and, by induction, Qt≥0.
  • Small-noise limit: In the relevant parameter range, σt tends to zero, so the rescaled signal variable converges to a three-point limit supported at 0 and ±∞.The limiting distribution retains the zero mass 1−ε and separates positive and negative nonzero mass.
  • Covariance convergence: The limiting covariance map is increasing and satisfies Fα,ε(q)>q for q∈[0,1), forcing the covariance limit to equal one.Taking a convergent subsequence of Qt gives Q∗=1 and therefore Qt→1.
  • Rate control: Under the stated distributional regularity condition, the finite-time recursion approaches its limiting counterpart with bounds controlled by exponentially decaying terms.The corollary supplies constants B,B′,b depending on pX for these comparisons.

C.2. Proof of Lemma 6(b): ρ > ρ∗(δ).

The proof analyzes a scalar recursion and its stationary point to establish the claims in Lemma 6(b). It also shows convergence of the associated correlation sequence and derives the required probability and expectation statements.

  • Proof of Lemma 6(b1), (b2): For α > αmin(ε,δ), there is a unique σ∗(δ,pX) separating regions where F(σ²,ασ) exceeds or falls below σ².The argument uses concavity of σ² ↦ F(σ²,ασ), F(0,0)=0, and a derivative larger than 1 at zero.
  • Proof of Lemma 6(b1), (b2): At α = α0, continuity gives P{|X + σ∗Z| ≥ ασ∗} = δ, proving claim (b2).The proof first establishes that the limiting probability exceeds δ as α approaches αmin.
  • Proof of Lemma 6(b1), (b2): The limiting map Q ↦ Fα,δ,pX(Q) is increasing and convex, with Fα,δ,pX(Q) > Q on [0,1), so Qt converges to 1.Consequently, the adjacent-time quantity Rt,t−1 converges to σ².
  • Proof of Lemma 6(b3): For pX = (1−ε)δ0 + εγ and δ ∈ (ε,δ∗(ε)), the proof reduces claim (b3) to showing E{|η(X + σ∗Z; ασ∗)|} < E{|X|}.Part (b1) supplies the limiting expectation involving σt and σ∗.
  • Proof of Lemma 6(b1), (b2): The stationary point is given by σ = σ∗(δ,pX) and θ = θ∗(δ,pX) ≡ α0(δ,pX)σ∗(δ,pX).The text identifies this as the unique saddle point of the relevant function.

APPENDIX D: REFERENCE RESULTS

This appendix records a calculus fact and a minimum-singular-value estimate for perturbed rectangular matrices. The matrix result applies to deterministic matrices with bounded operator norm plus Gaussian perturbations.

  • Reference results: The appendix invokes a calculus fact based on concavity of f(x) = ln(x) for x > 0.The proof treats the cases x ≥ s and x < s separately and derives an exponential inequality.
  • Reference results: The minimum-singular-value estimate is cited from, Theorem 1.1, as a result for perturbed rectangular matrices.It is presented as an auxiliary estimate used by the paper.
  • Reference results: Theorem 10 concerns M × N matrices with N ≤ (1−a)M, a deterministic B satisfying ∥B∥2 ≤ 1/a, and Gaussian G with entries N(0,1/M).The theorem assumes independent and identically distributed entries in G.
  • Reference results: Theorem 10 states that constants a1 and a2 depend only on a and remain bounded for a > 0.The displayed probability bound is not included in the supplied passage.
Loading 1207.7321v2…