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 (32)

• Structured Compressed Sensing: From Theory to Applications
• Compressed Sensing in Astronomy
• Compressive sensing as a new paradigm for model building
• A Singular Value Thresholding Algorithm for Matrix Completion
• Compressive Direct Measurement of the Quantum Wave Function
• Spread spectrum magnetic resonance imaging
• 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
• Compressed Sensing with Prior Information: Optimal Strategies, Geometry, and Bounds
• Search for localized Wannier functions of topological band structures via compressed sensing
• A Unified Approach to Sparse Signal Processing
• Matrix Coherence and the Nystrom Method
• Fast and Near-Optimal Matrix Completion via Randomized Basis Pursuit
• Informative Sensing
• Low-Rank Matrix Recovery from Row-and-Column Affine Measurements
• Compressed Sensing for Network Reconstruction
• Compressive sensing: a paradigm shift in signal processing
• A Fast Non-Gaussian Bayesian Matching Pursuit Method for Sparse Reconstruction
• Principal Component Pursuit with Reduced Linear Measurements
• Sums of random Hermitian matrices and an inequality by Rudelson
• Compressive sensing by white random convolution
• Blind Compressive Sensing Framework for Collaborative Filtering
• Random Subdictionaries and Coherence Conditions for Sparse Signal Recovery
• Theoretical Analysis of Compressive Sensing via Random Filter
• On Finite Alphabet Compressive Sensing
• Oblique Pursuits for Compressed Sensing
• Probabilistic Recovery Guarantees for Sparsely Corrupted Signals
• Compression and Encryption of Search Survey Gamma Spectra using Compressive Sensing
• Compressive Imaging and Characterization of Sparse Light Deflection Maps
• Compressive Schlieren Deflectometry
• The Design of Compressive Sensing Filter