The Noise-Sensitivity Phase Transition in Compressed Sensing

By David L. Donoho, Arian Maleki, Andrea Montanari. IEEE Transactions on Information Theory, 2010

389 citations recorded by the source corpus.

Consider the noisy underdetermined system of linear equations: y = Ax₀ + z, with A an n × N measurement matrix, n <; N, and z ~ N(0, σ²I) a Gaussian white noise. Both y and A are known, both x₀ and z are unknown, and we seek an approximation to x₀. When x₀ has few nonzeros, useful approximations are often obtained by ℓ₁-penalized ℓ₂ minimization, in which the reconstruction x̂^1,λ solves min{||y - Ax||₂²/2 + λ||x||₁}. Consider the reconstruction mean-squared error MSE = E|| x̂^1,λ - x₀||₂²/N, and define the ratio MSE/σ² as the noise sensitivity. Consider matrices A with i.i.d. Gaussian entries and a large-system limit in which n, N → ∞ with n/N → δ and k/n → ρ. We develop exact expressions for the asymptotic MSE of x̂^1,λ , and evaluate its worst-case noise sensitivity over all types of k-sparse signals. The phase space 0 ≤ 8, ρ ≤ 1 is partitioned by the curve ρ = ρ_MSE(δ) into two regions. Formal noise sensitivity is bounded throughout the region ρ = ρ_MSE(δ) and is unbounded throughout the region ρ = ρ_MSE(δ). The phase boundary ρ = ρ_MSE(δ) is identical to the previously known phase transition curve for equivalence of ℓ₁ - ℓ₀ minimization in the k-sparse noiseless case. Hence, a single phase boundary describes the fundamental phase transitions both for the noise less and noisy cases. Extensive computational experiments validate these predictions, including the existence of game-theoretical structures underlying it (saddlepoints in the payoff, least-favorable signals and maximin penalization). Underlying our formalism is an approximate message passing soft thresholding algorithm (AMP) introduced earlier by the authors. Other papers by the authors detail expressions for the formal MSE of AMP and its close connection to ℓ₁-penalized reconstruction. The focus of the present paper is on computing the minimax formal MSE within the class of sparse signals x⁰.

Subfields: Computational Mechanics, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/6e4a477ec52d60db64621c0839fad1bc6da018fc

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

1. Philip Schniter
2. Andrea Montanari
3. E.J. Candes
4. Yaniv Plan
5. Li Ping
6. Junjie Ma
7. Wei Yu
8. Liang Liu

In Computer Networks and Communications

1. Philip Schniter
2. Liang Liu
3. Wei Yu
4. Li Ping
5. Junjie Ma
6. Andrea Montanari
7. E.J. Candes
8. Jeremy P. Vila

In Signal Processing

1. E.J. Candes
2. Philip Schniter
3. Li Ping
4. Junjie Ma
5. Andrea Montanari
6. Wei Yu
7. Liang Liu
8. Jeremy P. Vila

Citations in the corpus

• A Probabilistic and RIPless Theory of Compressed Sensing (2010, background): “In the asymptotic case, stable signal recovery has been demonstrated for the Gaussian measurement ensemble in a regime in which the RIP does not necessarily hold [22], [4].”
• Sparse Signal Processing for Grant-Free Massive Connectivity: A Future Paradigm for Random Access Protocols in the Internet of Things (2018, background): “Note that AMP with soft thresholding implicitly solves the LASSO problem [19], i.”
• The dynamics of message passing on dense graphs, with applications to compressed sensing (2010, neutral): “A prominent example is the noise sensitivity of LASSO, which is investigated in [DMM10c].”
• The LASSO Risk for Gaussian Matrices (2010, methodology): “Further, they seem to enjoy a remarkable universality property and to hold for a fairly broad family of matrices [13].”
• Expectation-Maximization Gaussian-Mixture Approximate Message Passing (2012, background): “, the ratio of estimat onerror power to measurement-noise power under the worst-cas e signal distribution) is either finite or infinite [4].”
• Hypothesis Testing in High-Dimensional Regression Under the Gaussian Random Design Model: Asymptotic Theory (2013, neutral): “We then specialize this bound to the case of standard Gaussian design matrices, showing formally that no test can detect θ 0 ,i (cid:54) = 0 unless | θ 0 ,i | ≥ µ UB = cσ/ √ n .”
• From Denoising to Compressed Sensing (2014, neutral): “Unfortunately, sparsity-based methods are less appropriate for many imaging applications.”
• Orthogonal AMP (2016, methodology): “, LASSO [11]) with IID Gaussian sensing matrices [12]–[14] and SE provides a tool to predict the related performance [13].”