February, 2005; Revised June 2005 | Emmanuel Candes, Justin Romberg, and Terence Tao
This paper presents a method for stable signal recovery from incomplete and inaccurate measurements using $\ell_1$-regularization. The goal is to recover a sparse signal $x_0 \in \mathbb{R}^m$ from noisy observations $y = Ax_0 + e$, where $A$ is an $n \times m$ matrix with $n \ll m$ and $e$ is an error term. The method involves solving the $\ell_1$-regularization problem:
$$
\min \|x\|_{\ell_1} \quad \text{subject to} \quad \|Ax - y\|_{\ell_2} \leq \epsilon.
$$
The paper shows that if the matrix $A$ satisfies the uniform uncertainty principle and the signal $x_0$ is sufficiently sparse, then the solution $x^\sharp$ to this problem is within the noise level:
$$
\|x^\sharp - x_0\|_{\ell_2} \leq C \cdot \epsilon.
$$
The uniform uncertainty principle requires that the matrix $A$ approximately preserves the Euclidean norm of sparse vectors. The paper provides conditions under which this principle holds, and shows that the $\ell_1$-regularization method can recover sparse signals accurately even in the presence of noise.
The paper also discusses the recovery of approximately sparse signals and provides numerical examples demonstrating the effectiveness of the method. The results are applicable to a wide range of measurement ensembles, including Gaussian, Fourier, and general orthogonal matrices. The method is shown to be robust to noise and can be used for both sparse and compressible signals. The paper concludes with a discussion of the computational tractability of the method and its potential applications in signal processing and imaging.This paper presents a method for stable signal recovery from incomplete and inaccurate measurements using $\ell_1$-regularization. The goal is to recover a sparse signal $x_0 \in \mathbb{R}^m$ from noisy observations $y = Ax_0 + e$, where $A$ is an $n \times m$ matrix with $n \ll m$ and $e$ is an error term. The method involves solving the $\ell_1$-regularization problem:
$$
\min \|x\|_{\ell_1} \quad \text{subject to} \quad \|Ax - y\|_{\ell_2} \leq \epsilon.
$$
The paper shows that if the matrix $A$ satisfies the uniform uncertainty principle and the signal $x_0$ is sufficiently sparse, then the solution $x^\sharp$ to this problem is within the noise level:
$$
\|x^\sharp - x_0\|_{\ell_2} \leq C \cdot \epsilon.
$$
The uniform uncertainty principle requires that the matrix $A$ approximately preserves the Euclidean norm of sparse vectors. The paper provides conditions under which this principle holds, and shows that the $\ell_1$-regularization method can recover sparse signals accurately even in the presence of noise.
The paper also discusses the recovery of approximately sparse signals and provides numerical examples demonstrating the effectiveness of the method. The results are applicable to a wide range of measurement ensembles, including Gaussian, Fourier, and general orthogonal matrices. The method is shown to be robust to noise and can be used for both sparse and compressible signals. The paper concludes with a discussion of the computational tractability of the method and its potential applications in signal processing and imaging.