Sparsity and Incoherence in Compressive Sampling

Abstract

We consider the problem of reconstructing a sparse signal $x^0\in {\mathbb{R}}^n$ from a limited number of linear measurements. Given $m$ randomly selected samples of $U{x}^0$, where $U$ is an orthonormal matrix, we show that ${\ell }_1$ minimization recovers $x^0$ exactly when the number of measurements exceeds \[ m\geq \mathrm{Const}\cdotμ^2(U)\cdot S\cdot\log n, \] where $S$ is the number of nonzero components in $x^0$, and $\mu$ is the largest entry in $U$ properly normalized: $\mu (U)=\sqrt{n}\cdot {\max }_{k,j}|U_{k,j}|$. The smaller $\mu$, the fewer samples needed. The result holds for ``most'' sparse signals $x^0$ supported on a fixed (but arbitrary) set $T$. Given $T$, if the sign of $x^0$ for each nonzero entry on $T$ and the observed values of $U{x}^0$ are drawn at random, the signal is recovered with overwhelming probability. Moreover, there is a sense in which this is nearly optimal since any method succeeding with the same probability would require just about this many samples.

References in corpus (1)

• Concentration around the mean for maxima of empirical processes

Cited by in corpus (12)

• Compressed Sensing in Astronomy
• A Singular Value Thresholding Algorithm for Matrix Completion
• Rejoinder: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
• Guaranteed Rank Minimization via Singular Value Projection
• Exact Matrix Completion via Convex Optimization
• A Unified Approach to Sparse Signal Processing
• Fast and Near-Optimal Matrix Completion via Randomized Basis Pursuit
• Informative Sensing
• Compressive sensing: a paradigm shift in signal processing
• Compressive sensing by white random convolution
• Theoretical Analysis of Compressive Sensing via Random Filter
• The Design of Compressive Sensing Filter