Abstract
In 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
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
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
then \((\alpha_1, \alpha_2)\) is the unique sparsest possible decomposition (all other decompositions have more nonzero terms). In addition, if
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
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.\)
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
An erratum to this article is available at http://dx.doi.org/10.1007/s10208-007-7162-6.
Rights and permissions
About this article
Cite this article
Candes, E., Romberg, J. Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions. Found Comput Math 6, 227–254 (2006). https://doi.org/10.1007/s10208-004-0162-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10208-004-0162-x