Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions

By E.J. Candes, Justin K. Romberg. Foundations of Computational Mathematics, 2004

572 citations recorded by the source corpus.

AbstractIn this paper we develop a robust uncertainty principle for finite signals in ${\Bbb C}^N$ which states that, for nearly all choices $T, \Omega\subset\{0,\ldots,N-1\}$ such that $|T| + |\Omega| \asymp (\log N)^{-1/2} \cdot N,$ there is no signal $f$ supported on $T$ whose discrete Fourier transform $\hat{f}$ is supported on $\Omega.$ In fact, we can make the above uncertainty principle quantitative in the sense that if $f$ is supported on $T,$ then only a small percentage of the energy (less than half, say) of $\hat{f}$ is concentrated on $\Omega.$ As an application of this robust uncertainty principle (QRUP), we consider the problem of decomposing a signal into a sparse superposition of spikes and complex sinusoids $f(s) = \sum_{t\in T}\alpha_1(t)\delta(s-t) + \sum_{\omega\in\Omega}\alpha_2(\omega)e^{i2\pi \omega s/N}/\sqrt{N}.$ We show that if a generic signal $f$ has a decomposition $(\alpha_1,\alpha_2)$ using spike and frequency locations in $T$ and $\Omega,$ respectively, and obeying $|T| + |\Omega| \leq {\rm Const}\cdot (\log N)^{-1/2}\cdot N,$ then $(\alpha_1, \alpha_2)$ is the unique sparsest possible decomposition (all other decompositions have more nonzero terms). In addition, if $|T| + |\Omega| \leq {\rm Const}\cdot (\log N)^{-1}\cdot N,$ then the sparsest $(\alpha_1,\alpha_2)$ can be found by solving a convex optimization problem. Underlying our results is a new probabilistic approach which insists on finding the correct uncertainty relation, or the optimally sparse solution for nearly all subsets but not necessarily all of them, and allows us to considerably sharpen previously known results [9], [10]. In fact, we show that the fraction of sets $(T, \Omega)$ for which the above properties do not hold can be upper bounded by quantities like $N^{-\alpha}$ for large values of $\alpha.$ The QRUP (and the application to finding sparse representations) can be extended to general pairs of orthogonal bases $\Phi_1,\Phi_2 \mbox{of} {\Bbb C}^N.$ For nearly all choices ${\Gamma_1},{\Gamma_2}\subset\{0,\ldots,N-1\}$ obeying $|{\Gamma_1}| + |{\Gamma_2}| \asymp \mu(\Phi_1,\Phi_2)^{-2} \cdot (\log N)^{-m},$ where $m\leq 6,$ there is no signal $f$ such that $\Phi_1 f$ is supported on ${\Gamma_1}$ and $\Phi_2 f$ is supported on ${\Gamma_2}$ where $\mu(\Phi_1,\Phi_2)$ is the mutual coherence between $\Phi_1$ and $\Phi_2.$

Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/927de77d0002851c150be9fb0ea2204880135f3f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Simply denoise: Wavefield reconstruction via jittered undersampling (2008, background): “Jittered undersampling differentiates itself from random undersampling according to a discrete uniform distribution, which also creates favorable recovery conditions (Xu et al., 2005; Abma and Kabir, 2006; Zwartjes and Sacchi, 2007), by controlling the maximum gap in the acquired data.”
Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization (2014, methodology): “As is now well known, 1-norm minimization has been used to recover sparse signals in compressive sensing [5,6,9,14], and nuclear-norm minimization has been used to recover a low-rank matrix from a subset of its entries in matrix completion [3,43].”
Linearized Bregman iterations for compressed sensing (2009, background): “The interested reader should consult, for example, [2, 8, 9, 10, 11, 12, 19, 21, 22, 23, 24, 29, 30, 31, 33, 34] for details.”
A non-adapted sparse approximation of PDEs with stochastic inputs (2010, background): “Compressive sampling is an emerging theory in the field of signal and image processing [20,21,17,30,15,18,16,22,14].”
A compressed sensing approach for partial differential equations with random input data (2012, unknown): “Email addresses: mathelin@limsi.fr (L. Mathelin), gallivan@math.fsu.edu (K. A. Gallivan) http://www.global-sci.com/ 919 c©2012 Global-Science Press”
Sparsity and incoherence in compressive sampling (2006, methodology): “2 with the methods used in [3], we can establish that if |supp x| const · n μ2( ∗ 1 2) · log n ,”
A Generalized Iterated Shrinkage Algorithm for Non-convex Sparse Coding (2013, background): “Sparse coding [7, 18, 31] is an effective tool in a myriad of applications such as compressed sensing [11], image restoration [24, 25], face recognition [38], etc.”
Decoding by linear programming (2005, methodology): “4 is inspired by our previous work [5], see also [4, 6], but unlike those earlier results, our results here are deterministic, and thus do not have a non-zero probability of failure, provided of course one can ensure that the system (vj)j∈J verifies the condition (1.”
On sparse reconstruction from Fourier and Gaussian measurements (2008, unknown): “and in practice, based on the convex relaxation [9, 16, 18, 19, 15, 21, 29, 30, 31, 12, 10, 11, 14, 3, 2 , 5, 6, 27, 4, 7, 23].”
Theory and Implementation of an Analog-to-Information Converter using Random Demodulation (2007, background): “The CS framework [2], [3], demonstrates that a signal that is compressible in one basis Ψ can be recovered to a quality similar to that of a K-term approximation from M = O(K log N K ) nonadaptive linear projections onto a second basis Φ that is incoherent with the first.”
11-magic : Recovery of sparse signals via convex programming (2005, background): “A recent series of papers [3] [4] [5] [6] [7] [8] develops a theory of signal recovery from highly incomplete information.”
An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems (2009, background): “The problem (4) has attracted much interest in compressed sensing [8, 9, 10, 14, 15] and is also known as the basis pursuit problem.”