Sparse approximation property and stable recovery of sparse signals from noisy measurements

Abstract

In this paper, we introduce a sparse approximation property of order $s$ for a measurement matrix $\mathbf{A}$: $$\Vert {\mathbf{x}}_s{\Vert }_2\le D\Vert \mathbf{A}\mathbf{x}{\Vert }_2+\beta \frac{{\sigma }_s(\mathbf{x})}{\sqrt{s}}\mathrm{for}\mathrm{all}\mathbf{x},$$ where ${\mathbf{x}}_s$ is the best $s$-sparse approximation of the vector $\mathbf{x}$ in ${\ell }^2$, ${\sigma }_s(\mathbf{x})$ is the $s$-sparse approximation error of the vector $\mathbf{x}$ in ${\ell }^1$, and $D$ and $\beta$ are positive constants. The sparse approximation property for a measurement matrix can be thought of as a weaker version of its restricted isometry property and a stronger version of its null space property. In this paper, we show that the sparse approximation property is an appropriate condition on a measurement matrix to consider stable recovery of any compressible signal from its noisy measurements. In particular, we show that any compressible signalcan be stably recovered from its noisy measurements via solving an ${\ell }^1$-minimization problem if the measurement matrix has the sparse approximation property with $\beta \in (0,1)$, and conversely the measurement matrix has the sparse approximation property with $\beta \in (0,\infty )$ if any compressible signal can be stably recovered from its noisy measurements via solving an ${\ell }^1$-minimization problem.

To appear in IEEE Trans. Signal Processing, 2011

References in corpus (3)

• Near-ideal model selection by ${\ell }_1$ minimization
• The statistical restricted isometry property and the Wigner semicircle distribution of incoherent dictionaries
• Recovery of sparsest signals via ${\ell }^q$-minimization

Cited by in corpus (10)

• Compressed Sensing Recovery via Nonconvex Shrinkage Penalties
• Signal Recovery under Cumulative Coherence
• Lower Bound for RIP Constants and Concentration of Sum of Top Order Statistics
• A null space property approach to compressed sensing with frames
• A null space analysis of the L1 synthesis method in dictionary-based compressed sensing
• Nonlinear frames and sparse reconstructions in Banach spaces
• The gap between the null space property and the restricted isometry property
• Truncated Sparse Approximation Property and Truncated $q$-Norm Minimization
• Restricted $q$-Isometry Properties Adapted to Frames for Nonconvex $l_q$-Analysis
• Matrix Recovery from Rank-One Projection Measurements via Nonconvex Minimization