The Noise-Sensitivity Phase Transition in Compressed Sensing

DOI10.1109/TIT.2011.2165823MaRDI QIDQ5272314zbMATH OpenOpenAlexFDO

Authors David Donoho, Arian Maleki, Andrea Montanari

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.1218

Mathematics Subject Classification ID

Detection theory in information and communication theory (94A13)

Abstract: Consider the noisy underdetermined system of linear equations: y=Ax0 + z0, with n x N measurement matrix A, n < N, and Gaussian white noise z0 ~ N(0,sigma^2 I). Both y and A are known, both x0 and z0 are unknown, and we seek an approximation to x0. When x0 has few nonzeros, useful approximations are obtained by l1-penalized l2 minimization, in which the reconstruction hxl solves min || y - Ax||^2/2 + lambda ||x||_1. Evaluate performance by mean-squared error (MSE = E ||hxl - x0||_2^2/N). Consider matrices A with iid Gaussian entries and a large-system limit in which n,N oinfty with n/N o delta and k/n o ho. Call the ratio MSE/sigma^2 the noise sensitivity. We develop formal expressions for the MSE of hxl, and evaluate its worst-case formal noise sensitivity over all types of k-sparse signals. The phase space 0 < delta, ho < 1 is partitioned by curve ho = hoMSE(delta) into two regions. Formal noise sensitivity is bounded throughout the region ho < hoMSE(delta) and is unbounded throughout the region ho > hoMSE(delta). The phase boundary ho = hoMSE(delta) is identical to the previously-known phase transition curve for equivalence of l1 - l0 minimization in the k-sparse noiseless case. Hence a single phase boundary describes the fundamental phase transitions both for the noiseless and noisy cases. Extensive computational experiments validate the predictions of this formalism, including the existence of game theoretical structures underlying it. Underlying our formalism is the AMP algorithm introduced earlier by the authors. Other papers by the authors detail expressions for the formal MSE of AMP and its close connection to l1-penalized reconstruction. Here we derive the minimax formal MSE of AMP and then read out results for l1-penalized reconstruction.

Cited in

(41)

• Debiasing the Lasso: optimal sample size for Gaussian designs
• Overcoming the limitations of phase transition by higher order analysis of regularization techniques
• The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning
• Precise statistical analysis of classification accuracies for adversarial training
• A phase transition for finding needles in nonlinear haystacks with LASSO artificial neural networks
• LASSO risk and phase transition under dependence
• Which bridge estimator is the best for variable selection?
• Asymptotic risk and phase transition of \(l_1\)-penalized robust estimator
• Universality in polytope phase transitions and message passing algorithms
• Accuracy assessment for high-dimensional linear regression
• Fundamental limits of weak recovery with applications to phase retrieval
• A simple homotopy proximal mapping algorithm for compressive sensing
• Performance comparisons of greedy algorithms in compressed sensing.
• Optimal Phase Transitions in Compressed Sensing
• Sharp MSE bounds for proximal denoising
• Evaluation of generalized degrees of freedom for sparse estimation by replica method
• Statistical mechanics analysis of thresholding 1-bit compressed sensing
• High dimensional robust M-estimation: asymptotic variance via approximate message passing
• Recovering structured signals in noise: least-squares meets compressed sensing
• Nearly optimal minimax estimator for high-dimensional sparse linear regression
• Compressed Sensing Performance Bounds Under Poisson Noise
• Sensitivity to Basis Mismatch in Compressed Sensing
• Guarantees of total variation minimization for signal recovery
• Bayesian inference for spatio-temporal spike-and-slab priors
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
• Cross validation in sparse linear regression with piecewise continuous nonconvex penalties and its acceleration
• Foveated compressive imaging for low power vehicle fingerprinting and tracking in aerial imagery
• Phase Transitions in Recovery of Structured Signals From Corrupted Measurements
• Perfect reconstruction of sparse signals with piecewise continuous nonconvex penalties and nonconvexity control
• Consistent parameter estimation for Lasso and approximate message passing
• Sharp global convergence guarantees for iterative nonconvex optimization with random data
• Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions
• The Lasso with general Gaussian designs with applications to hypothesis testing
• Phase transition and higher order analysis of L_q regularization under dependence
• Correlation adjusted debiased Lasso: debiasing the Lasso with inaccurate covariate model
• Equivalence of state equations from different methods in high-dimensional regression
• Precise asymptotics of bagging regularized M-estimators
• Differentially private learning beyond the classical dimensionality regime
• A CLuP algorithm to practically achieve 0.76 SK-model ground state free energy
• Regularity of almost-surely injective projections in Euclidean spaces
• From compression to compressed sensing

This page was built for publication: The Noise-Sensitivity Phase Transition in Compressed Sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5272314)