PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Phase Transitions in Compressed Sensing

Yihong Wu, Sergio Verdú

arXiv:1111.6822v2cs.ITmath.ST

TL;DR

Compressed sensing asks how measurement rate limits recovery fidelity for random analog signals under linear measurements. The paper analyzes optimal nonlinear, optimized linear, and random linear encoders with optimal decoders in noiseless and noisy settings. It finds that Gaussian sensing matrices can match optimal nonlinear phase transitions, while practical ℓ1 and AMP thresholds remain far from optimal in highly sparse regimes.

  • Problem

    The paper studies the fundamental tradeoff between measurement rate and reconstruction fidelity under constrained sensing matrices and noisy or noiseless observations.

  • Method

    The paper analyzes optimal nonlinear, optimal linear, and random linear encoders with corresponding optimal decoders for i.i.d. inputs, including Gaussian random sensing and high-SNR arguments.

  • Results

    Gaussian sensing matrices achieve the same phase-transition threshold as optimal nonlinear encoding for discrete-continuous mixtures, while ℓ1-minimization and AMP thresholds lie far from optimal in highly sparse regimes.

  • Takeaways & Limitations

    The phase-transition threshold is governed by the input’s information dimension, and conventional Gaussian random sensing can be optimal at this threshold.

  • Takeaways & Limitations

    The universal phase-transition optimality of random sensing matrices with non-Gaussian i.i.d. entries remains unknown, and singular distributions may lack simple dimension formulas.

Abstract

from arXiv · show

Compressed sensing deals with efficient recovery of analog signals from linear encodings. This paper presents a statistical study of compressed sensing by modeling the input signal as an i.i.d. process with known distribution. Three classes of encoders are considered, namely optimal nonlinear, optimal linear and random linear encoders. Focusing on optimal decoders, we investigate the fundamental tradeoff between measurement rate and reconstruction fidelity gauged by error probability and noise sensitivity in the absence and presence of measurement noise, respectively. The optimal phase transition threshold is determined as a functional of the input distribution and compared to suboptimal thresholds achieved by popular reconstruction algorithms. In particular, we show that Gaussian sensing matrices incur no penalty on the phase transition threshold with respect to optimal nonlinear encoding. Our results also provide a rigorous justification of previous results based on replica heuristics in the weak-noise regime.

1 Introduction

The paper frames compressed sensing as an information-theoretic study of the tradeoff between measurement rate and reconstruction fidelity for random i.i.d. signals. It compares optimal nonlinear, optimized linear, and random linear encoders with optimal decoders, including noiseless and noisy settings.

  • 1.1 Setup: The study compares optimal nonlinear, optimal linear, and random linear encoders under corresponding optimal decoding for known-distribution i.i.d. inputs.Noiseless decoding is required to be Lipschitz, while noisy decoding uses the MMSE estimator.
  • 1.2 Phase transition: The central goal is to characterize the minimum measurement rate needed for vanishing noiseless error or bounded noisy reconstruction sensitivity as dimension grows.The phase-transition threshold depends on the signal and noise statistics.
  • 1.4 Main contributions: The optimal phase-transition threshold for i.i.d. inputs is the input information dimension, including optimal linear encoding and Gaussian random measurements for discrete-continuous mixtures.For these mixtures, the threshold equals the weight of the analog component.
  • 1.4 Main contributions: Gaussian random sensing matrices incur no phase-transition penalty relative to optimal nonlinear encoders, supporting the conventional compressed-sensing setup.The result holds for arbitrary noise distributions with finite non-Gaussianness.
  • 1.4 Main contributions: The thresholds of ℓ1-minimization and AMP are far from the optimal boundary, especially in the highly sparse regime.The paper compares optimal thresholds with several practical reconstruction algorithms under various input distributions.

2 Three dimensions

This section introduces information, MMSE, and Minkowski dimensions as geometric and information measures used in the paper’s coding theorems. It emphasizes their relationships and the special behavior of discrete-continuous and singular distributions.

  • 2.1 Information dimension: Information dimension measures the growth rate of discretized entropy and equals the weight of the absolutely continuous component for discrete-continuous mixtures.For a discrete-continuous mixture, the information dimension is γ under the stated finite-entropy condition.
  • 2.1 Information dimension: For singular distributions, information dimension may lack a simple formula; the Cantor distribution has d(X) = log3 2 ≈0.63.The Cantor example is absolutely singular with respect to Lebesgue measure.
  • 2.2 MMSE dimension: MMSE dimension governs high-SNR MMSE asymptotics and coincides with information dimension for discrete-continuous mixtures.For such mixtures, both lower and upper MMSE dimensions equal γ.
  • 2.2 MMSE dimension: MMSE dimension need not exist, and for the Cantor distribution snr · mmse(X, snr) oscillates between approximately 0.62 and 0.64.The lower and upper MMSE dimensions can therefore be distinct.
  • 2.3 Minkowski dimension: Minkowski dimension characterizes the exponent governing covering-number growth and extends this geometric notion to probability measures.For the middle-third Cantor set, the Minkowski dimension is log3 2.

3 Noiseless compressed sensing

The noiseless framework defines minimum achievable measurement rates under encoder and decoder regularity constraints, then establishes general converse and achievability results. For discrete-continuous inputs, linear encoding can attain the fundamental rate with Lipschitz decoders, including the sparse-signal case.

  • Definitions: The framework defines minimum ϵ-achievable rates for encoder-decoder classes under specified regularity conditions.The rates are denoted R∗(X, ϵ), R(X, ϵ), and ˆR(X, ϵ) according to the allowable encoder and decoder classes.
  • Geometric limits: Robust reconstruction is established as harder to achieve than linear compression, while low-Minkowski-dimension sets admit probabilistic linear embeddings.These results connect the compressed-sensing limits to geometric embedding properties.
  • Converse results: The results include general converse bounds for Lipschitz decoding and a strong converse for sufficiently low measurement rates.The converse applies to arbitrary random vectors, while the associated bounds specialize for i.i.d. inputs.
  • Linear encoding: For discrete-continuous mixtures, linear encoders and Lipschitz decoders can be constructed with decoder Lipschitz constants bounded independently of dimension.The bounded-constant guarantee is stated for rates above the information-dimension threshold.
  • Linear encoding: For discrete-continuous mixtures with finite-entropy discrete parts, linear encoding achieves the fundamental minimum rate, and roughly s measurements suffice for s-sparse recovery.This matches the stated result that s+1 measurements are necessary and sufficient probabilistically for s-sparse vectors.
  • Limitations and robustness: The bounded-Lipschitz construction relies specifically on the ℓ2 norm, Hilbert-space extension, and random-matrix singular-value behavior; robustness worsens near the fundamental rate.The decoder constant is described as growing exponentially in 1/(R−γ), and polynomial divergence near the limit remains unresolved.

4 Noisy compressed sensing

The noisy compressed-sensing analysis characterizes distortion, noise sensitivity, and phase transitions for optimal, linear, and random linear encoders. The phase-transition threshold equals the input information dimension broadly, while Gaussian random sensing achieves this threshold for discrete-continuous inputs.

  • 4.4 Least-favorable input: Gaussian distribution: Gaussian inputs simultaneously maximize the three distortion-rate functions under a variance constraint and provide upper bounds for non-Gaussian inputs.
  • 4.4 Least-favorable input: Gaussian distribution: For rates below one, optimal linear and random linear distortion converge to 1 − R, reflecting unrecoverable projection onto the sensing matrix’s nullspace.Random linear encoding additionally has strictly worse second-order asymptotics than optimal linear encoding.
  • 4.4 Least-favorable input: Gaussian distribution: At R = 1, random linear encoding has distortion σ(1 + o(1)), whereas optimized linear encoding achieves σ^2(1 + o(1)); random-matrix inversion can amplify noise power.The optimized value is achieved by choosing the identity encoding matrix.
  • The phase-transition thresholds of optimal encoding equal the input’s upper information dimension, and this equality extends to broad encoder classes under stated distributional conditions.For discrete-continuous mixtures, optimal linear and Gaussian random linear encoders also attain the threshold determined by the continuous-component weight.
  • 4.5 Non-Gaussian inputs: For rates above the mixture weight γ, Gaussian sensing has bounded worst-case noise sensitivity, and the conclusion extends to non-Gaussian noise with finite non-Gaussianness.The achievability argument uses a noiseless Lipschitz decoder as a suboptimal noisy estimator.
  • Gaussian random sensing matrices achieve the optimal transition threshold for any known discrete-continuous input mixture.The fundamental limit depends on the input distribution through the weight γ of its analog component; in the conventional sparsity model, the limit is γ.
  • 4.6 Results relying on replica heuristics: The replica-based general result applies to arbitrary input distributions but depends on the conjectured validity of the replica symmetry postulate.For discrete-continuous mixtures, it predicts threshold γ, matching the rigorously proven result; its added scope is singular input components.

5 Comparisons to LASSO and AMP algorithms

The paper compares LASSO, AMP, and linear-programming decoders with optimal phase-transition thresholds in noiseless and noisy compressed sensing. These popular algorithms are often substantially suboptimal, especially for sparse signals and discrete structures.

  • 5.2 Noiseless measurements: LP and AMP thresholds are severely suboptimal unless γ is close to one, compared with the optimal threshold γ across three signal models.Figure 6 plots the suboptimal thresholds against the optimal threshold.
  • 5.2 Noiseless measurements: For highly sparse signals, ℓ1 and AMP decoders require on the order of 2s log_e measurements, whereas an optimal decoder requires only s measurements.The suboptimal algorithms therefore have an asymptotically larger measurement requirement in the sparse regime.
  • 5.2 Noiseless measurements: For simple signals, the LP and AMP threshold approaches 1/2 rather than zero as γ → 0 because feasibility decoding ignores the signal’s discrete structure.The feasibility decoder selects any compatible vector in the hypercube, so typical saturation at 0 or 1 is not enforced.
  • 5.3 Noisy measurements: For discrete-continuous mixtures, LASSO and AMP retain threshold R±(γ), while the optimal threshold is γ.The same threshold comparison applies to the noisy phase-transition boundary when the continuous component is absolutely continuous.
  • 5.3 Noisy measurements: At γ = 0.1, the LASSO phase-transition threshold is approximately 3.3 times the optimal threshold.Figure 7 compares asymptotic noise sensitivities of the optimal decoder and LASSO/AMP for the sparse signal model.

6 Proofs

The proofs establish threshold results using geometric properties of Gaussian random matrices, affine-subspace coverings, and Lipschitz decoding arguments. They also identify a limitation for irregular distributions such as the Cantor distribution.

  • 6.1 Auxiliary results: For Gaussian ensembles, the least singular value is positive almost surely, removing the discrete-ensemble atom-at-zero term from the general sub-Gaussian bound.This gives a sharper auxiliary estimate specialized to Gaussian sensing matrices.
  • 6.1 Auxiliary results: Gaussian random matrices preserve affine-subspace geometry with bounds depending on subspace dimension rather than its basis, supporting the injective Lipschitz decoders used in the proofs.The auxiliary lemmas combine smallest-singular-value bounds, affine-subspace estimates, and Lipschitz extension.
  • Proofs of Section 3 results: Theorem 6 is proved by concentrating discrete-continuous input vectors on exponentially many affine subspaces whose dimensions do not exceed the measurement rate.The achievability argument uses Lemma 3 and the fact that the relevant affine-subspace dimension is controlled by γ.
  • 6.3 Proofs of results in Section 4: The proof of Gaussian random-encoding achievability constructs a Lipschitz decoder whose error event has probability o(1) whenever R > γ.The resulting estimator yields finite worst-case noise sensitivity above the information-dimension threshold.
  • 6.3 Proofs of results in Section 4: For Cantor-distributed inputs, even O(σ^2) reconstruction error can have a limiting normalized sensitivity strictly between the information and MMSE dimensions.The limiting value approaches d(X) = log_3 2 in the stated example.

7 Concluding remarks

The paper studies compressed sensing statistically by modeling signals as random processes and compares optimal nonlinear, optimal linear, and random linear encoders. It finds that Gaussian sensing achieves the optimal phase-transition threshold for discrete-continuous mixtures, while several scope boundaries and open questions remain.

  • Framework: The study uses a statistical Shannon framework with i.i.d. random inputs rather than worst-case guarantees for individual sparse signals.The framework analyzes fundamental limits under known input statistics and corresponding optimal decoders.
  • Limitations: The analysis assumes i.i.d. inputs with a common distribution known to both encoder and decoder, leaving sources with memory for future work.The fundamental limits apply asymptotically, although some noiseless results are non-asymptotic.
  • Framework: The phase-transition thresholds cover reconstruction error probability in noiseless observations and normalized MMSE in noisy observations across three encoder classes.The encoder classes are optimal nonlinear, optimal linear, and random linear, each paired with an optimal decoder.
  • Main findings: Gaussian sensing matrices achieve the same phase-transition threshold as optimal nonlinear encoding for any discrete-continuous mixture.The result is universal over noise distributions with finite non-Gaussianness, and the limit depends on input statistics only through the analog-component weight.
  • Scope and mechanism: Gaussian sensing relies on least-singular-value bounds and rotational invariance that are not generally available for discrete ensembles.The least-singular-value density bound is known in the Gaussian case, while the stated lemma can fail for ensembles such as Rademacher matrices.
  • Main findings: The work rigorously proves phase-transition thresholds for mixture distributions and shows agreement with earlier replica-symmetry predictions.This connects the paper’s rigorous results to prior weak-noise analyses based on replica heuristics.

Appendix A Proof of the middle inequality in (46)

This appendix establishes the middle inequality in (46) using concentration and power-constraint properties for random measurement matrices.

  • Conclusion: Continuity of L(X, R, σ2) allows sending ϵ down to zero and yields the second inequality in (46).
  • Proof: The proof uses convergence in probability to one as signal dimension grows to establish the relevant high-probability matrix event.The event probability is obtained through the weak law of large numbers.
  • Assumption: The matrix assumption is that A has i.i.d. entries with zero mean and variance 1.
  • Proof: For every matrix in the high-probability event, scaling A by 1+ϵ satisfies the power constraint used in the proof.

Appendix B Distortion-rate tradeoff of Gaussian inputs

Appendix B derives the minimal-distortion expressions in (53)–(55), completing the proof of Theorem 8.

  • Proof: The appendix derives the expressions for minimal distortion that complete the proof of Theorem 8.

B.1 Optimal encoder

The optimal-encoder subsection obtains the relevant expression by substituting the Gaussian i.i.d. source rate-distortion function into equation (40).

  • Derivation: Substituting the standard Gaussian i.i.d. source rate-distortion function into (40) yields the equality in (53).

B.2 Optimal linear encoder

The optimal linear encoder is analyzed through the eigenvalues of H^T H, with separate cases for measurement rates above and below one. For R < 1, the improved lower bound is achieved by retaining the first k coordinates and discarding the rest.

  • Gaussian analysis: For jointly Gaussian X_n and measurement noise, the conditional distribution remains Gaussian and the optimal estimator is linear.The conditional covariance and estimator follow from the Gaussian model and the matrix inversion lemma.
  • Optimization: The best encoding matrix H is selected by optimizing the distortion using the eigenvalues of H^T H.Writing H^T H = U^TΛU reduces the analysis to its eigenvalues under the power constraint.
  • Case R < 1: For R < 1, the lower bound is unattainable because rank(H^T H) ≤ k < n forces at least n − k eigenvalues to zero.Equality would require all eigenvalues to equal R, which is impossible when k < n.
  • Case R < 1: For R < 1, the improved lower bound is achieved by keeping the first k coordinates of X_n and discarding the rest.This construction establishes the equality claimed for the corresponding distortion expression.

B.3 Random linear encoder

The random linear encoder is analyzed through the limiting eigenvalue distribution of its sensing matrix. The Marčenko–Pastur law yields the asymptotic distortion formula, which agrees with the replica-based expression in the Gaussian case.

  • Asymptotic analysis: The empirical eigenvalue distribution of (1/R)A^T A converges almost surely to the Marčenko–Pastur law as n →∞.This convergence enables evaluation of the asymptotic distortion for random linear encoding.
  • Asymptotic analysis: Applying dominated convergence and integrating against the limiting law produces the asymptotic distortion formula for the random linear encoder.The required integrand is continuous and bounded.
  • Replica comparison: In the Gaussian case, the random-linear distortion formula coincides with the expression obtained from the replica symmetry postulate.The paper verifies the equivalence by substituting the unique positive solution and simplifying algebraically.

Appendix C LASSO noise sensitivity for fixed input distributions

The appendix derives optimized LASSO noise sensitivity in the weak-noise regime for fixed input distributions. It characterizes the LASSO MSE through a scalar equation and establishes distinct behavior above and below the phase-transition threshold.

  • LASSO characterization: The LASSO decoder’s MSE follows from the scalar-equivalent characterization, while optimizing over the penalty parameter is equivalent to optimizing over α.The soft-thresholding estimator defines the scalar denoising step.
  • Weak-noise result: For R > R±(γ), the LASSO MSE is characterized by a unique solution for τ^2 and has a fixed-α weak-noise expansion.The expansion is given in terms of γ, α, Φ(−α), and ϕ(α).
  • Weak-noise result: The optimized LASSO noise sensitivity formula is obtained by combining the scalar characterization with the weak-noise asymptotics.The resulting expression holds for any Q with no mass at zero.
  • Threshold behavior: If R < R±(γ), the asymptotic distortion remains strictly positive as measurement noise vanishes for every choice of λ.This establishes the below-threshold weak-noise boundary for the considered input distributions.
Loading 1111.6822v2…