Source-linked AI summary
Noise Folding in Compressed Sensing
Ery Arias-Castro, Yonina C. Eldar
TL;DR
Compressed sensing has mostly analyzed noiseless signals with noise entering during measurement, although practical signals may already contain noise. This paper analyzes pre-measurement noise, showing that for common measurement schemes it can be reduced to an equivalent measurement-noise model with increased variance proportional to p/n. The analysis establishes this equivalence and bounds the resulting measurement matrix under stated assumptions.
Problem
Compressed sensing has largely overlooked recovery when random noise is added to the signal before measurement rather than only to the measurements.
Method
The paper analyzes pre-measurement noise by whitening the model and comparing the resulting measurement matrix's coherence and RIP constants with those of the original matrix.
Results
For common compressed-sensing measurement schemes, pre-measurement noise is equivalent after whitening to measurement noise with variance increased by a factor proportional to p/n, while the relevant matrix constants remain essentially unchanged in the stated asymptotic regime.
Takeaways & Limitations
When n ≪ p, signal noise is folded into the compressed measurements, producing a large noise increase that can substantially affect SNR.
Takeaways & Limitations
The analysis assumes random signal and measurement noises with covariance σ2I and uses a small-η condition for the whitening analysis.
Abstract
from arXiv · showhide
The literature on compressed sensing has focused almost entirely on settings where the signal is noiseless and the measurements are contaminated by noise. In practice, however, the signal itself is often subject to random noise prior to measurement. We briefly study this setting and show that, for the vast majority of measurement schemes employed in compressed sensing, the two models are equivalent with the important difference that the signal-to-noise ratio is divided by a factor proportional to p/n, where p is the dimension of the signal and n is the number of observations. Since p/n is often large, this leads to noise folding which can have a severe impact on the SNR.
1 Introduction
Compressed sensing studies recovery of sparse signals from few noisy measurements, typically modeling noise as measurement error. This literature has largely overlooked noise added to the signal before measurement, despite its practical importance and potential effect on recovery.
- 1 Introduction: Compressed sensing recovers s-sparse signals from n measurements using a measurement matrix with n ≪ p.The signal has at most s nonzero elements, and recovery methods include greedy algorithms and relaxation methods.
- 1 Introduction: Noise analysis commonly models measurement noise as either deterministic and bounded or random, typically Gaussian.The paper focuses on the random-noise setting because it permits better performance bounds than worst-case analysis.
- 1 Introduction: Recovery guarantees for standard methods depend on measurement-matrix properties such as coherence and the restricted isometry property.When these quantities are sufficiently small, squared error is proportional to sparsity and noise variance, up to a factor logarithmic in p.
- 1 Introduction: Practical systems can add noise to the signal before measurement, a setting that the compressed-sensing literature has treated only sparsely.The paper highlights sub-Nyquist A/D conversion as an example in which the analog signal is contaminated before measurement.
2 Noise Folding
Pre-measurement signal noise can be reformulated as an equivalent measurement-noise model, but with substantially increased effective noise. For common compressed-sensing matrices, whitening preserves the relevant measurement properties closely enough that standard recovery analyses apply, while the increase scales with p/n.
- Problem formulation: Pre-measurement noise changes the model to y = A(x + z) + w, where z is signal noise and w is measurement noise.The paper assumes both are independent random vectors with isotropic covariance.
- Equivalent formulation: The effective model uses a transformed matrix B with coherence and RIP constants very close to those of A, and white noise variance σ0^2 + (p/n)σ^2.This makes the pre-measurement-noise model comparable to the standard measurement-noise setting.
- Equivalent formulation: When the effective noise is not white, whitening converts it to white noise but changes the measurement matrix from A to B.This transformation enables standard analysis while requiring control of the resulting matrix changes.
- Special case: If AA^T is proportional to the identity, the effective noise remains white and the two models are identical except for increased noise variance.This includes matrices formed by concatenating orthonormal bases.
- Noise folding: For the special case, assuming σ0^2 ≈ σ^2, the noise increase is proportional to p/n, producing noise folding.More generally, the paper states that the equivalent-model result persists even when AA^T is not proportional to the identity.
3 RIP and Coherence with Whitening
The analysis whitens pre-measurement noise, changing A to B while preserving its CS geometry when η is small. For standard random measurement matrices, η is small with high probability, so RIP and coherence remain close under whitening.
- Whitening: Whitening converts the noise into white noise and changes the measurement matrix from A to B, with generally small changes for standard CS matrices.The transformed noise has covariance γI, while the matrix change is quantified through RIP constants and coherence.
- Whitening: Approximating AAT by (p/n)I with small η underpins the claim that B and A have similar coherence and RIP constants.The approximation quality is measured by η, and the derivation assumes η is small.
- Whitening: η is small with high probability for common sub-Gaussian and spherical-column measurement ensembles, including Gaussian, uniform, and Bernoulli matrices.The cited results also cover other distributions when A's independent columns have covariance I/n.
- Restricted Isometry Analysis: If A has RIP constants α_s and β_s and η < 1/2, then B has constants α_s(1 −η1) and β_s(1 + η1), with η1 = η/(1 −η).The smaller RIP constant remains positive under the stated η < 1/2 restriction.
4 Conclusion
The paper argues that pre-measurement noise is effectively measurement noise after whitening for common CS schemes, but with noise variance increased by p/n. The resulting measurement matrix retains essentially the same RIP and coherence in the stated asymptotic regime.
- Conclusion: Pre-measurement noise is equivalent after whitening to standard measurement noise, modulo a changed measurement matrix and a noise-variance increase by p/n.This is the paper's stated noise-folding effect.
- Conclusion: As n, p →∞ with p/n →0, the new measurement matrix has essentially unchanged RIP constants and coherence.The paper connects these bounds to standard recovery methods whose performance is formulated using those quantities.
- Conclusion: Standard recovery methods therefore operate as usual in this regime, except that noise folding multiplies the noise variance by p/n.The conclusion states the qualification in terms of the usual RIP- and coherence-based performance analysis.