PaperlayerView exact revision on arXiv

Source-linked AI summary

Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing

David L. Donoho, Adel Javanmard, Andrea Montanari

arXiv:1112.0708v2cs.ITcond-mat.stat-mechmath.ST

TL;DR

The paper studies reconstructing a signal x from measurements y using band-diagonal sensing matrices. It analyzes Bayes-optimal AMP through state evolution and proves recovery above the signal’s Rényi information dimension, including k(n)+o(n) measurements for sparse signals and o(n) for discrete signals.

  • Problem

    Compressed sensing seeks to reconstruct x from the measured vector y and measurement matrix A, while sparse-recovery arguments based on support specification do not directly apply when measurements are not bounded-bit descriptions.

  • Method

    The paper constructs spatially coupled random matrix ensembles and uses Bayes-optimal AMP, with a deterministic state-evolution recursion guiding the algorithm analysis.

  • Results

    For undersampling rate δ > d(pX), AMP’s mean-squared error tends to zero as noise variance vanishes; sparse Bernoulli-Gaussian signals recover from k(n)+o(n) measurements, and discrete signals from o(n).

  • Takeaways & Limitations

    The measurements overhead for estimating the support is sublinear, so spatial coupling achieves near-support-sized measurement counts even when the support is of order n.

  • Takeaways & Limitations

    The robustness bound applies for δ > D(pX), and the asymptotic convergence rate is not claimed to be uniform in pX, with accuracy potentially requiring larger n as K increases.

Abstract

from arXiv · show

We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in coding theory. As demonstrated heuristically and numerically by Krzakala et al. \cite{KrzakalaEtAl}, message passing algorithms can effectively solve the reconstruction problem for spatially coupled measurements with undersampling rates close to the fraction of non-zero coordinates. We use an approximate message passing (AMP) algorithm and analyze it through the state evolution method. We give a rigorous proof that this approach is successful as soon as the undersampling rate $δ$ exceeds the (upper) Rényi information dimension of the signal, $\uRenyi(p_X)$. More precisely, for a sequence of signals of diverging dimension $n$ whose empirical distribution converges to $p_X$, reconstruction is with high probability successful from $\uRenyi(p_X)\, n+o(n)$ measurements taken according to a band diagonal matrix. For sparse signals, i.e., sequences of dimension $n$ and $k(n)$ non-zero entries, this implies reconstruction from $k(n)+o(n)$ measurements. For `discrete' signals, i.e., signals whose coordinates take a fixed finite set of values, this implies reconstruction from $o(n)$ measurements. The result is robust with respect to noise, does not apply uniquely to random signals, but requires the knowledge of the empirical distribution of the signal $p_X$.

1 Introduction and main results

The paper constructs spatially coupled sensing matrices and an AMP reconstruction method, proving recovery near the information-theoretic limit while characterizing noise robustness, signal generality, and scope limitations.

  • Main result: δ > d(pX) guarantees asymptotically successful AMP recovery for sequences whose empirical distribution converges to pX.The result holds for suitable spatially coupled sensing-matrix sequences and includes noiseless recovery.
  • Scope and assumptions: The guarantees apply beyond i.i.d. random signals because matrix columns are exchangeable and the analysis uses empirical-distribution convergence.The estimator assumes knowledge of the empirical signal distribution pX and noise level σ2.
  • Construction and analysis: The method uses spatially coupled matrices, Bayes-optimal AMP, separable denoisers based on pX, and state evolution.The AMP memory term is essential because the sensing matrix remains fixed across iterations.
  • Noise robustness: MSEAMP(S; σ2) ≤ Cσ2 when δ > D(pX), establishing robustness to noisy measurements.The constant C depends on pX and δ, and the bound applies under the paper’s broad noise-model conditions.
  • Limitations: The convergence statements are asymptotic and non-uniform in pX, with accuracy potentially requiring larger n as distributional complexity increases.The paper also notes that it does not prove the stronger iteration-to-infinity noiseless guarantee.
  • Sparse signals: m(n) = k(n)+o(n) measurements suffice for recovering Bernoulli-Gaussian signals with k(n) nonzero entries.This matches the information-theoretic measurement count up to a sublinear overhead.
  • Discrete signals: m(n) = o(n) spatially coupled measurements suffice for i.i.d. signals with discrete coordinate distributions.Discrete-valued signals have zero Rényi information dimension under the stated setting.

2 Matrix and algorithm construction

The paper constructs spatially coupled sensing matrices by lifting a block-level variance matrix into Gaussian blocks, then analyzes AMP through a multidimensional state-evolution recursion. Special parameter choices yield reconstruction guarantees when the undersampling rate exceeds either lower or upper Rényi information dimension.

  • Spatial coupling: The spatially coupled construction uses a roughly row-stochastic nonnegative matrix W whose suitable parameterization imposes the characteristic band-diagonal support.The construction takes limits M, N →∞ with M = Nδ before Lr, Lc →∞.
  • Matrix ensemble: Each block-level entry Wr,c is lifted into an M × N block of independent Gaussian entries with variance Wr,c/M.Uniform random reordering of rows and columns ensures exchangeability, while W controls the band-diagonal structure.
  • Matrix ensemble: The sensing ensemble partitions rows and columns into Lr and Lc equal-sized groups, with n = NLc and m = MLr.The block dimensions are M by N, and the undersampling ratio is obtained by taking M = Nδ.
  • AMP and state evolution: AMP is analyzed by state evolution, which tracks coordinate-wise reconstruction errors ψ and residual noise variances φ and is asymptotically exact for the ensemble.The multidimensional state contains individualized MSEs and measurement-coordinate residual variances; denoisers are tuned using precomputed state evolution values.
  • AMP and state evolution: The AMP iteration applies a scaled matched filter, a separable denoiser, and an Onsager memory term to update estimates and residuals.The scaling uses Qt because the sensing entries are independent but have unequal variances.
  • Guarantees: When δ > d(pX), suitable parameters make AMP’s asymptotic MSE arbitrarily small, while δ > D(pX) gives a finite stability guarantee under the modified scheme.The theorems select L0, L, ρ, t0, and noise thresholds or a stability constant, with asymptotic limits specified for ℓ = Lρ, ρ, and L0.
  • Guarantees: The finite-dimensional results follow by restricting the AMP estimate to the first n coordinates, with the normalized error ratio converging to one.The proof uses n = NLc and N →∞, so n′/n ≤ (1 + Lc/n) →1.

3 Advantages of spatial coupling

Spatial coupling uses heteroscedastic band-diagonal matrices and oversampling to make AMP converge to the ideal fixed point where standard AMP can fail.

  • Construction: Spatially coupled matrices use independent heteroscedastic entries and oversample the first 2ρ−1N signal coordinates.These components form the paper’s proposed construction.
  • Standard ensemble: For standard matrices, Bayes optimal AMP converges to an incorrect large-error fixed point when δ < ˜δ(pX).The recursion also has a smaller correct fixed point, but state evolution selects the bad one from the usual initialization.
  • Spatial coupling: For d(pX) < δ < ˜δ(pX), spatial coupling drives the recursion to the ideal fixed point for nearly all positions.The exception concerns coordinates near the boundaries.
  • Denoising: Spatial coupling does not outperform the best fixed point of the standard recursion, so denoisers with larger MSE lead to worse performance.The posterior expectation denoiser is useful because it minimizes the relevant mean square error at each iteration.
  • Limitation: With soft thresholding, the homoscedastic state evolution has a unique stable fixed point, suggesting no spatial-coupling improvement for that AMP variant.The paper reports numerical confirmation of this expectation and connects it to LASSO or ℓ1 reconstruction.

4 Key lemmas and proof of the main theorems

The proof reduces AMP analysis to deterministic state evolution, then establishes recursion bounds under conditions on the undersampling rate and signal distribution.

  • Proof strategy: State evolution is the crucial proof tool, reducing analysis of AMP to a deterministic recursion.This reduction is the central analytical strategy.
  • Theorem setup: For a sequence of instances with empirical parameters converging to (pX, σ2), the construction supports almost-sure state-evolution conclusions for every fixed iteration.The sensing dimensions scale with M/N approaching δ.
  • Relation to prior work: The state-evolution lemma is presented as a generalization of earlier work, while the paper supplies heuristic intuition for the recursion.A formal proof in a more general setting is referenced separately.
  • Key lemmas: The technical core is a lemma characterizing the behavior of the state evolution recursion.Its proof is deferred to Section 7 before the main results are established.
  • Key lemmas: The recursion analysis uses a shape function W and distinguishes conditions δ > d(pX) and δ > D(pX).The corresponding lemmas provide the conditions needed for the main theorem proofs.
  • Proof details: The theorem proofs combine the recursion lemma with monotonicity of mmse, properties of φa(t), and stochasticity of the coupling matrix.Expected-error claims follow through additional limiting arguments.

5 Numerical experiments

Numerical experiments illustrate the traveling-wave profile, test iteration-wise state-evolution predictions, and examine the phase transition of spatially coupled AMP.

  • Setup: The experiments use Bernoulli-Gaussian signals with ε = 0.1, σ = 0.01, ρ = 0.1, M = 6, N = 50, L = 500, and L0 = 5.The signal coordinates are sampled independently from pX.
  • Evolution of the AMP algorithm: Oversampling the first 2ρ−1N = 1000 coordinates makes their profile reach order σ2, initiating progressive reconstruction.The low-error region propagates through the coordinates as a traveling wave.
  • Evolution of the AMP algorithm: After t = 800 iterations, the profile is uniformly of order σ2.The profile reaches successive coordinates after earlier components are effectively removed from the measurements.
  • Evolution of the AMP algorithm: State evolution predicts AMP’s empirical mean square error at each iteration, with both errors decreasing linearly versus t.The comparison uses M = 30 Monte Carlo instances and error bars for the empirical AMP error.
  • Phase diagram: The phase-transition experiments evaluate ε ∈ {0.1, 0.2, 0.3, 0.4, 0.5} using logit fits.The results are reported as consistent with the information-theoretic lower bound δ > d(pX) = ε.

6 State evolution: an heuristic derivation

The heuristic derivation explains state evolution by temporarily resampling independent matrices, characterizing Gaussian effective noise, and identifying the memory term needed for fixed-matrix AMP.

  • Scope of derivation: The paper presents this derivation as heuristic intuition, while the rigorous state-evolution result is attributed to broader prior work.The discussion parallels earlier derivations for i.i.d. sensing matrices.
  • Modified recursion: The derivation temporarily replaces the fixed sensing matrix with an independent copy at each iteration and removes the memory term.This modified recursion is analytically convenient but is not a practical algorithm.
  • Modified recursion: With resampled matrices, independence from the current iterate makes the effective matrix-vector products easier to characterize.The auxiliary matrices are i.i.d. from the spatially coupled ensemble.
  • Gaussian effective noise: The central-limit argument yields approximately Gaussian entries and an effective observation X + τt(g(i))^1/2Z.Here Z is standard normal and independent of X.
  • State evolution: Applying the denoiser to this effective observation produces the next-iterate error distribution used to derive the state-evolution recursion.The derivation links the coordinate error to ηt,s(X + τt(s)^1/2Z) − X.
  • Fixed-matrix AMP: For the actual fixed-matrix AMP, the memory term bt ⊙ rt−1 cancels asymptotic dependencies between A and xt.Without that term, state evolution does not apply to the naive iteration.

7 Analysis of state evolution: Proof of Lemma 4.2

The proof analyzes spatially coupled AMP through progressively simplified state-evolution descriptions and a free-energy argument. When undersampling exceeds the information dimension, this argument rules out large fixed points and yields small continuum-state solutions under suitable conditions.

  • State-evolution reductions: The original state evolution is bounded by a modified sequence that is easier to analyze.The modified sequence dominates the original after a finite iteration offset.
  • Continuum approximation: The continuum state evolution replaces vectors with functions, whose bounds translate back into bounds on the modified state vectors.For later iterations, the continuum states are nondecreasing Lipschitz functions of position.
  • Free-energy argument: The proof constructs a free energy whose stationary points coincide with fixed points of continuum state evolution.A large fixed point can then be perturbed so that free energy decreases, contradicting stationarity.
  • Small-state conclusion: If δ exceeds the upper information dimension, sufficiently small noise and sufficiently large system length force continuum solutions to be O(σ2).The contradiction argument applies under the hypotheses of Lemma 7.20, including monotonicity, Lipschitz continuity, and a lower bound involving mmse.
  • State-evolution properties: The state-evolution sequences decrease over iterations and increase with the noise variance.These monotonicity properties support the comparison arguments used throughout the proof.
  • Supporting bounds: The analysis also establishes finite-time bounds, lower bounds, and regularity properties for the state-evolution variables.Examples include lower bounds involving mmse and comparison results for boundary regions.

C Proof of Lemma 7.12

This proof establishes local Lipschitz continuity of the Bayes-optimal AMP estimate at each fixed iteration by induction, bounding changes in the state-evolution terms.

  • Local Lipschitz continuity: For every fixed iteration t, the Bayes-optimal AMP estimate x_t(y) is locally Lipschitz continuous in y.The proof proceeds by induction on t, with the base case at t = 1 and the induction step controlling both terms in the update.
  • Inductive bounds: The induction bounds the mmse contribution using a uniform derivative bound on the relevant interval.The arguments of mmse are at most 2/σ2, allowing a constant bound on its derivative.
  • Inductive bounds: The spatial-kernel contribution is controlled by bounded derivatives and Riemann-sum convergence, producing an error bound proportional to ρ.The stated bound is C3ρ/(δσ4) for an appropriate constant C3.

D Proof of Proposition 7.19

The proof derives the stated small-noise bound by combining a small-φ estimate with the relation between the fixed-point scale and σ2.

  • Small-noise estimate: For sufficiently small σ, the fixed-point quantity φ* is bounded by 2σ2 and therefore lies within the range where the small-φ estimate applies.The proof substitutes φ* into the preceding bound to obtain the desired estimate.
  • Small-noise estimate: The resulting bound contains the gap 2 + δ − d(pX) and a logarithmic factor involving 2σ2.This expresses how the estimate depends on the undersampling rate, information dimension, and noise level.

E Proof of Claim 7.21

The proof shows that a nondecreasing continuum fixed point must contain an interval of prescribed length on which φ remains above a threshold above φ*.

  • Threshold interval: If φ(θℓ−1) were below κ/2 + φ*, monotonicity would contradict the assumption used in the claim.Therefore φ(x) ≥ κ/2 + φ* throughout the terminal interval [θℓ−1, ℓ−1].
  • Threshold interval: Choosing ℓ0 = K/(1 − θ) ensures that the terminal interval has length at least K.This supplies the interval [x1, x2] required by Claim 7.21.

F Proof of Proposition 7.22

The proof establishes monotonicity, boundedness, and Lipschitz continuity properties of ς2, then uses interval-wise integral bounds to prove the proposition.

  • Properties of ς2: ς2(x) is non-increasing, equals σ2 for x ≥1, and satisfies σ2 ≤ς2(x) < 2σ2 when δL0 > 3.For x ≤−1, it is given by σ2 + (1/δ) mmse(L0/(2σ2)).
  • Properties of ς2: ς2(x)/σ2 is Lipschitz continuous, with constant C < 1 when L0δ > 3.There exists C such that |ς2(α1) −ς2(α2)| < Cσ2|α2 −α1|.
  • Integral decomposition: The proof splits the integral across five intervals and bounds each contribution separately using the established properties.The intervals are [−1, −1+a), [−1+a, x0+a), [x0+a, x2), [x2, ℓ−1), and the remaining stated range.
  • Integral decomposition: On x ≥x2, φa(x) and φ(x) coincide, while on [−1+a, x0+a), φa(x)=φ(x−a).These identities enable direct simplification or comparison of the corresponding integral terms.

G Proof of Proposition 7.23

The proof decomposes ˜EW into three terms and bounds each using properties of φa, monotonicity of I, Lipschitz control, and auxiliary remarks.

  • Term decomposition: ˜EW(φa) is decomposed as ˜EW,1(φa) + ˜EW,2(φa) + ˜EW,3(φa).The subsequent argument treats these components separately.
  • Bounding ˜EW,1: For x2 ≤x, φa(x)=φ(x), while for x1 < x < x2, κ/2 < φa(x) ≤φ(x) ≤ΦM.The proof also reparameterizes φa using α=(x2−x1)/(x2−x1−a) and β=(ax2)/(x2−x1−a).
  • Bounding ˜EW,1: The ˜EW,1 difference is bounded using bounded-Lipschitz behavior of W and the inequality φ(z)−1 ≤2/κ on [x1,x2].Monotonicity of I also makes one difference term nonpositive.
  • Remaining terms: On [−1+a,x0+a), the proof uses φa(z)=φ(z−a), and combines the resulting bounds with Eqs. (154), (157), and (159).The final proposition follows after using Eqs. (156), (160), and (161).
  • Bounding ˜EW,3: For y ∈[−1,−1+a), φa(y) is below 2σ2, while φa(y) ≥σ2 implies I(W ∗φa(y)−1) ≤I(σ−2).The bound uses monotonicity of I and Remark G.1.

H Proof of Proposition 7.24

The proof bounds the right-hand side through Proposition 7.19 and a lower bound on V, then chooses σ sufficiently small to obtain a σ-independent estimate.

  • Term reduction: The first and third terms on the right-hand side of Eq. (163) are zero.The remaining term is then bounded separately.
  • Upper bound: For σ ∈(0,σ2], Proposition 7.19 supplies an upper bound used in controlling the remaining term.This is the main auxiliary estimate invoked at this stage.
  • Upper bound: Because φ(x)>κ/2 on [x0,x2], V(φ(x)) ≥(δ/2) log φ >(δ/2) log(κ/2).This lower bound contributes to the control of the right-hand side.
  • Small-σ choice: Choosing σ0 sufficiently small ensures the desired inequality for all σ ∈(0,σ0], and the resulting right-hand side is independent of σ.The independence is stated explicitly after Eq. (168).

I Proof of Claim 7.26

The proof chooses parameters using Lemma 7.20, derives a contradiction from the assumed crossing of φ1, and obtains bounds over a central interval.

  • Parameter selection: The argument assumes the condition used in Claim 7.21 and chooses σ small enough that φ∗<φ1.It then sets κ=(φ1−φ∗)(1−θ)/2 and invokes Lemma 7.20.
  • Parameter selection: Lemma 7.20 provides ℓ0 and σ0 under the selected parameters.These thresholds support the subsequent integral and interval estimates.
  • Contradiction argument: Assuming φ(µℓ−1) reaches φ1 leads to a contradiction after substituting the expression for µ.The contradiction establishes the claimed upper bound on the relevant interval.
  • Final interval bound: For x ∈[θℓ−1,µℓ−1], the proof obtains Cσ2(1−α)<φ(x)<φ1 and sets (µ−θ)ℓ=(1−θ)ℓ/2.Taking ℓ>max{ℓ0,2K/(1−θ)} completes the result.

J Proof of Proposition 7.27

The proof of Proposition 7.27 proceeds by establishing Eqs. (118) and (119) through a sequence of inequalities justified by prior results and a condition on φ(x).

  • The proof begins by establishing Eq. (118).
  • The second inequality uses the condition Cσ2/2 < φ(x) for x ∈ [x1, x2].
  • The proof then proceeds to establish Eq. (119).
  • The first inequality is justified by Remark F.1.
  • Another first inequality follows from Eq. (115) and Claim 7.26.
Loading 1112.0708v2…