PaperlayerView exact revision on arXiv

Source-linked AI summary

Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising

David Donoho, Iain Johnstone, Andrea Montanari

arXiv:1111.1041v2cs.ITmath.ST

TL;DR

Compressed sensing seeks precise limits for recovering sparse signals from underdetermined measurements. This paper develops AMP-based algorithms and a unifying formula linking their phase transitions to the minimax MSE of optimally tuned denoisers, including structured and nonconvex settings.

  • Problem

    Compressed sensing must characterize when sparse signals can be recovered accurately from undersampled measurements, including structured notions of sparsity.

  • Method

    The paper uses AMP with flexible denoisers and state evolution to derive phase-transition formulas for compressed sensing algorithms.

  • Results

    The phase-transition curve for AMP is given by the per-coordinate minimax MSE of the specified optimally tuned denoiser, with empirical confirmation for block soft thresholding and block James-Stein shrinkage.

  • Takeaways & Limitations

    AMP supports structured and nonconvex reconstruction methods whose phase transitions can outperform corresponding convex optimization approaches in their domains.

  • Takeaways & Limitations

    The general phase-transition relation is proved by assuming that state evolution accurately describes AMP behavior for large systems.

Abstract

from arXiv · show

Compressed sensing posits that, within limits, one can undersample a sparse signal and yet reconstruct it accurately. Knowing the precise limits to such undersampling is important both for theory and practice. We present a formula that characterizes the allowed undersampling of generalized sparse objects. The formula applies to Approximate Message Passing (AMP) algorithms for compressed sensing, which are here generalized to employ denoising operators besides the traditional scalar soft thresholding denoiser. This paper gives several examples including scalar denoisers not derived from convex penalization -- the firm shrinkage nonlinearity and the minimax nonlinearity -- and also nonscalar denoisers -- block thresholding, monotone regression, and total variation minimization. Let the variables eps = k/N and delta = n/N denote the generalized sparsity and undersampling fractions for sampling the k-generalized-sparse N-vector x_0 according to y=Ax_0. Here A is an n\times N measurement matrix whose entries are iid standard Gaussian. The formula states that the phase transition curve delta = delta(eps) separating successful from unsuccessful reconstruction of x_0 by AMP is given by: delta = M(eps| Denoiser), where M(eps| Denoiser) denotes the per-coordinate minimax mean squared error (MSE) of the specified, optimally-tuned denoiser in the directly observed problem y = x + z. In short, the phase transition of a noiseless undersampling problem is identical to the minimax MSE in a denoising problem.

1 Introduction

The paper extends AMP compressed sensing beyond unstructured sparsity and establishes a unifying phase-transition formula based on denoising minimax MSE. It applies this framework to separable, block, and nonseparable denoisers, including methods that outperform corresponding convex approaches.

  • Scope and framework: AMP extends compressed sensing to block and structured sparsity, convex and nonconvex penalization, and denoisers beyond scalar soft thresholding.The framework is designed for structured signal classes rather than only counting nonzero coordinates.
  • Scalar denoisers: Firm shrinkage has strictly lower minimax MSE than soft thresholding, yielding a slightly better optimally tuned AMP phase transition.The paper relates soft-thresholding AMP to LASSO and reports that firm-shrinkage AMP outperforms LASSO.
  • Scalar denoisers: Minimax shrinkage has strictly lower minimax MSE than firm shrinkage and a slightly better AMP phase transition than both soft and firm shrinkage.These scalar methods do not arise from the traditional convex penalization framework.
  • Structured denoisers: The same formula applies to nonseparable denoisers, with phase transitions identified for monotone regression and total variation denoising.The paper also connects these denoising transitions with AMP and convex optimization algorithms.
  • Phase-transition formula: The phase transition is predicted by the denoiser’s asymptotic minimax MSE and follows from the AMP state-evolution formalism.AMP succeeds above the predicted boundary, while the paper verifies the formula across several denoising settings.
  • Block sparsity: Positive-part James-Stein shrinkage approaches the ideal block-sparse transition δ > ε as block size grows, whereas block thresholding does not.The block-thresholding transition remains above the ideal limit even as B →∞.

2 Scalar-separable denoisers

The section reduces scalar-separable minimax denoising to a scalar estimation problem and compares firm, soft, hard, and globally minimax shrinkage. These denoisers determine AMP phase transitions through their minimax MSE.

  • Scalar minimax reduction: The minimax MSE for separable denoisers reduces to a scalar estimation problem under the stated distribution-family conditions.The reduction follows from product and marginal closure properties of the signal class.
  • Firm shrinkage: Firm shrinkage is continuous like soft thresholding but leaves sufficiently large values unshrunk, like hard thresholding.It uses lower and upper thresholds τ1 and τ2, with soft and hard thresholding recovered as limiting cases.
  • Firm shrinkage: Over the presented sparsity range, firm thresholding has strictly lower minimax MSE than hard or soft thresholding.Its minimax MSE increases from 0 toward 1 as ε increases from 0 toward 1.
  • Minimax shrinkage: Optimizing over all measurable nonlinearities yields minimax MSE below both firm and soft thresholding, although improvements are typically 0.01 or smaller for ε ∈ (0.01, 0.25).The globally minimax shrinker is characterized through a least-favorable prior and computed numerically.
  • Empirical phase transition behavior: AMP typically succeeds above δ(ε|η)=M(ε|η) and fails below it, with simulations showing success fractions above 50% above the predicted boundary.Empirical offsets are small and decrease with increasing N, while the fitted transition sharpens with γ ≈ 1/3.

3 Block-separable denoisers

The paper extends AMP to block-structured sparsity using block-separable denoisers, characterizes their minimax risks, and compares block soft thresholding with James–Stein shrinkage. The predicted minimax-MSE curves correctly describe observed AMP phase transitions.

  • Block-separable denoisers partition x∈R^N into M=N/B blocks and apply the same single-block mapping independently to each block.
  • The block-sparse class contains distributions with, in expectation, at most Mε nonzero blocks.
  • Block soft thresholding: Block soft thresholding shrinks a block to zero when its norm is at most τ and otherwise moves it toward the origin by τ.
  • Block soft thresholding: The block-soft minimax MSE is monotone increasing and concave in ε, with limits 0 as ε→0 and 1 as ε→1.
  • Large-block behavior: The ideal block-oracle MSE is ε, whereas block soft thresholding remains considerably larger even as B→∞.
  • Block James–Stein: Positive-part James–Stein shrinkage approaches the ideal large-block MSE and its AMP phase-transition curve matches the observed separation between atypical and typical recovery.

4 Monotone regression

Monotone regression provides a highly non-separable denoiser for signals that are mostly constant and nondecreasing. Its asymptotic minimax MSE is characterized through interval-length distributions, and the resulting curve agrees satisfactorily with monoreg AMP phase transitions.

  • Denoiser and signal class: Monotone regression projects observations onto the cone of nondecreasing sequences and is highly non-separable.
  • Minimax MSE: The least favorable signal is constant on N(1−ε) positions and has large jumps at the remaining Nε increase points.
  • Minimax MSE: The risk at zero appears to scale as Θ(log N), suggesting the general upper bound is loose by a logarithmic factor.
  • Minimax MSE: The monotone-regression minimax MSE is obtained by maximizing weighted risk r(ℓ) over interval-length distributions satisfying the sparsity constraint.
  • AMP implementation: Monoreg AMP implements the denoiser with the pool-adjacent-violators algorithm.
  • Empirical phase transition: The empirical phase transition agrees satisfactorily with δ=M(ε|MonoReg), with agreement improving as the signal length increases.

5 Total variation minimization

The paper applies AMP and minimax analysis to total variation denoising for mostly constant signals with sparse change points. It characterizes the relevant minimax risks and reports good agreement between predicted and observed phase transitions.

  • Signal class and denoiser: The total variation setting models vectors that are mostly constant, allowing both increases and decreases at sparse change points.
  • Signal class and denoiser: The denoiser is total variation penalized least squares, also called fused LASSO, with tuning parameter τ.
  • Minimax MSE: The asymptotic minimax MSE is characterized over bounded change-point spacing through distributions of interval lengths and adjacent change-point types.
  • Minimax MSE: Numerical calculations suggest the relevant risk configuration satisfies r++(N;τ)≥r+−(N;τ).
  • Empirical phase transition: For random changepoints, the predicted phase-transition curve is compared with AMP simulations at N=200 and N=500, showing good agreement.
  • Empirical phase transition: Under the least favorable signal prior, TV-AMP recovery is compared against the minimax-MSE curve for N=100, 250, and 500.

6 Characterization of the phase transition using state evolution

The paper uses state evolution to characterize AMP recovery through a one-dimensional MSE recursion, then identifies the phase transition with minimax denoising error under stated assumptions.

  • State evolution: For generalized denoisers, the proof assumes state evolution and extends the framework from separable to non-separable denoisers.The extension covers block thresholding, monotone regression, and total variation denoising.
  • State evolution: State evolution models AMP through the recursion m_t+1 = Ψ(m_t), where Ψ is the denoiser’s per-coordinate MSE at noise level σ^2 = m/δ.The recursion starts from a problem-dependent initial condition and determines whether the MSE vanishes.
  • Phase transition: The state-evolution phase transition δSE(ε) separates zero-error convergence for δ > δSE(ε) from positive limiting error for δ < δSE(ε).The recovery prediction is stated under the assumptions of Lemma 6.1.
  • Minimax characterization: Theorem 6.1 identifies the phase transition with the optimally tuned minimax MSE M(ε|η) for nested, scale-invariant signal classes.The proof obtains matching lower and upper bounds, with the final quantity equal to M(ε).
  • Scope: The correspondence applies to soft, positive soft, block soft, James-Stein, monotone regression, total variation, firm, and global minimax denoisers.For these denoisers, the relevant state-evolution conclusions are established or supplied in the cited analysis.

7 Phase transitions for other algorithms

This section connects AMP phase transitions with convex penalized reconstruction and tests the connection numerically for structured signals and nonstandard denoisers.

  • General correspondence: Formula (1.13) connects AMP recovery phase transitions with minimax mean squared error from statistical decision theory.When AMP converges with high probability, the same formula also links minimax decision theory with high-dimensional combinatorial geometry.
  • Penalized reconstruction: A convex penalty J defines an AMP-J algorithm whose denoiser is the proximal operator of J.Fixed points of AMP-J correspond to stationary points of the penalized problem, and to minimizers when J is convex.
  • Numerical verification: Figures 15–17 report phase transitions for block-sparse, monotone, and piecewise constant signals near the minimax-MSE curves predicted by (1.13).The comparisons use convex programs based on mixed ℓ2,1, monotone, and total-variation structure.
  • Nonconvex penalties: The minimax and firm thresholding denoisers correspond to nonconvex penalization schemes.Their implied penalties are nonconvex but seemingly close to ℓ1 penalization.
  • Interpretation and caveat: The minimax nonlinearity is somewhat complicated to implement, and its near-ℓ1 implied penalty challenges a general preference for nonconvex penalties.The paper also suggests that a different large-signal piecewise-linear rule may be competitive, but does not explore it in the firm family.

A Classical cases

The classical cases validate the phase-transition formula for several sparse and constrained signal models, including soft, positive-soft, capping, and positive-part denoisers.

  • Classical examples: The general formula was previously validated for simple sparse, nonnegative sparse, and box-constrained signals using corresponding AMP denoisers.The reviewed cases include soft thresholding, positive soft thresholding, and capping.
  • Non-scale-invariant classes: For non-scale-invariant classes such as box-constrained signals, the minimax definition additionally takes a supremum over the noise covariance.The resulting capping risk is denoted M(ε|Cap).
  • Minimax-risk calculation: For scale-invariant classes, minimax risks can be reduced to scalar estimation problems involving independent X and Gaussian noise Z.The calculation uses the fact that extremal distributions are mixtures of two-point distributions.
  • Explicit risks: The minimax risks for soft and positive-soft denoisers are given by parametric expressions in the optimally chosen threshold τ.The threshold is selected at the specified sparsity level.
  • Phase-transition rule: AMP succeeds with high probability when δ > M(ε|η) and fails with high probability when δ < M(ε|η).This identifies the noiseless AMP threshold with the denoiser’s minimax MSE.

B Calculation of minimax MSE

The paper computes minimax denoising risk by characterizing least-favorable distributions, bounding Fisher information numerically, and constructing the associated minimax denoiser.

  • Least-favorable distributions: The global minimax-risk calculation uses the class F1,ε and seeks the least-favorable distribution underlying the optimal denoiser.The minimax denoiser is the posterior expectation under that least-favorable prior.
  • Fisher-information formulation: For convex weakly compact classes, minimax risk is connected to Fisher information after Gaussian convolution.The posterior mean estimator supplies the minimax-optimal denoiser in this formulation.
  • Numerical construction: The numerical procedure uses a generalized Mallows-form tail with freely varying central masses and locations, producing a finite-dimensional family of candidate distributions.The tail approximation is used to estimate an upper bound while controlling numerical complexity.
  • Numerical accuracy: The computed lower and upper bounds on minimax MSE agree except possibly in the fourth decimal place across the reported cases.The bounds are based on numerical approximations to the Fisher-information quantities I− and I+.
  • Resulting denoiser: The near equality of the numerical bounds supports the approximate correctness of the Mallows-form least-favorable distribution.The resulting denoiser is then used in estimation and compressed-sensing experiments.
  • Visual diagnostics: The paper illustrates the least-favorable distributions and their mass-point locations in Figures 20 and 21.The figures visualize numerical minimizers and the approximately linear relation between mass-point locations and their indices.

C Convergence properties of AMP

The section characterizes AMP convergence and its empirical phase-transition behavior. Above the predicted threshold, error decays exponentially; below it, the mean squared error remains large.

  • AMP’s empirical phase transition is fairly insensitive to γ and t when t ≳100 and γ ≲0.05.The paper relates this robustness to theoretical and empirical evidence of exponential convergence.
  • For ε = 0.05 with soft thresholding, error decays exponentially when δ exceeds M(ε|η) ≈0.0239.The curves correspond to several δ values near the predicted phase-transition location.
  • For δ below M(ε|η), the mean squared error remains large rather than decaying toward zero.The same simulations show a clear separation around the predicted threshold.
  • The risk analysis for block denoisers uses rotational invariance to reduce dependence on µ to dependence on its norm.The risk is increasing in ∥µ∥ and has limiting value R(∞; τ) = B + τ^2.

D.2 Proof of Lemma 3.3

The proof analyzes large-block asymptotics of the minimax risk by normalizing the risk and identifying its optimizing threshold scale. The resulting minimizer agrees with Lemma 3.3.

  • As B →∞, the minimax threshold level τ is shown to have a specific asymptotic order.The proof proceeds through compactness and normalized-risk arguments.
  • The proof defines normalized risk eR_B(µ; τ) = R(µ; τ)/B and analyzes its limiting behavior.The normalized risk depends implicitly on B.
  • Calculus gives the minimizing constant c* = 1 − ε.This optimization yields the asymptotic expression stated in the proof.
  • The resulting expression coincides with the statement of Lemma 3.3.The remaining claims are justified using the limiting risk at infinity and the central limit theorem.

E Non-convergence of state evolution

This section proves that superquadratic risk can prevent state evolution from converging to zero below the predicted threshold. Numerical checks establish the required superquadratic behavior for firm and minimax denoisers.

  • Superquadratic behavior of the risk function implies non-convergence of state evolution for a corresponding signal distribution.The result is developed through a lower-bound argument for the denoisers studied in the paper.
  • The lemma assumes superquadratic risk, R(µ*) ≥ δ, and δ ≥ ε to establish a positive fixed-point lower bound.Under these conditions, the state-evolution map admits m_fp > 0.
  • Numerical evaluations show that the risk functions for firm and minimax denoisers are superquadratic on (0, µ*(ε)).The computations evaluate the risk on grids of ε and µ using least-favorable µ values; sample results appear in Figures 23 and 24.

F.1 Proof of Lemma 4.1, part (b)

The section derives risk properties for monotone regression and documents numerical procedures for validating phase-transition predictions. It also reports that empirical offsets are well described by a power-law decay.

  • Proof limitation: The analysis-only optimization problem requires knowledge of the signal’s discrete derivative and therefore is not itself an algorithm.The constraint is Δv_i ≥ −tΔµ_i for each i.
  • Localized monotone regression: As t →∞, the constrained monotone-regression problem becomes a localized regression problem with constraints only on non-increasing portions of the signal.Constraints with positive signal differences become irrelevant in the limit.
  • Localized monotone regression: The risk at infinity for monotone regression equals the corresponding local risk.This follows by analyzing the limiting solution and its uniformly bounded higher moments.
  • Proof decomposition: The monotone-regression optimization separates into independent problems on constant segments, each equivalent to monotone regression on that segment.The segment risks combine to give the desired global expression.
  • Empirical offsets: The empirical study tests whether offsets shrink and transitions steepen as N increases.The fitted offset is defined so that zero corresponds to exact agreement with M(ε|η).
  • Empirical offsets: γ = 1/3 adequately describes empirical phase-transition offsets, with R^2 exceeding 0.995.The fit uses model (H.1) for soft and firm thresholding across phase-transition results.

H.2 Transitions sharpen

The appendix models empirical transition steepness across signal sizes, sparsity levels, and denoisers, finding that it grows approximately as the square root of N. This scaling provides an adequate fit to the observed steepness parameters.

  • Steepness model: The empirical steepness parameter bβ(N, ε, η) is fitted with a power-law model in N across sparsity levels and denoisers.The fitted model is bβ(N, ε, η) = c(ε, η) N^γ + Error.
  • Interpretation: As N increases, the model expects transitions to become increasingly abrupt between complete failure and complete success.The transition regimes are described relative to the empirical phase-transition parameter c PT(N, ε, η).
  • Steepness model: The fitted model compares raw empirical steepness values with predictions for soft, firm, and minimax denoisers.The comparison is shown in Figure 26.

I.3 Proof of Lemma 6.2

The proof reduces starshapedness of the state-evolution mapping to monotonicity of the denoiser risk function. This criterion is then connected to previously established or separately proved risk monotonicity results.

  • Proof of Lemma 6.2: The state evolution mapping is starshaped for all distributions ν if and only if the risk function µ 7→R(µ) is monotone increasing.
  • Proof of Lemma 6.2: Risk monotonicity is established for soft thresholding, positive soft thresholding, monotone regression, total variation denoising, block soft thresholding, and James-Stein denoising.
Loading 1111.1041v2…