Candès, Emmanuel J.; Romberg, Justin Quantitative robust uncertainty principles and optimally sparse decompositions. (English) Zbl 1102.94020 Found. Comput. Math. 6, No. 2, 227-254 (2006). Summary: We develop a robust uncertainty principle for finite signals in \({\mathbb C}^N\) which states that, for nearly all choices \(T, \Omega\subset\{0,\dots,N-1\}\) such that \[ |T| + |\Omega| \asymp (\log N)^{-1/2}\cdot N, \] is no signal \(f\) supported on \(T\) whose discrete Fourier transform \(\widehat{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 \(\widehat{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 \text{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 \text{Const} \cdot (\log N)^{-1}\cdot N, \] 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 [D. L. Donoho and P. B. Stark, SIAM J. Appl. Math. 49, No. 3, 906–931 (1989; Zbl 0689.42001), D. L. Donoho and X. Huo, IEEE Trans. Inf. Theory 47, No. 7, 2845–2862 (2001; Zbl 1019.94503)]. 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\) of \({\mathbb C}^N\). For nearly all choices \(\Gamma_1,\;\Gamma_2\subset\{0,\dots,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\). Cited in 1 ReviewCited in 55 Documents MSC: 94A12 Signal theory (characterization, reconstruction, filtering, etc.) 94A20 Sampling theory in information and communication theory 42A38 Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type 46A35 Summability and bases in topological vector spaces 65C35 Stochastic particle methods 42A61 Probabilistic methods for one variable harmonic analysis Keywords:unique sparsest possible decomposition Citations:Zbl 0689.42001; Zbl 1019.94503 Software:QRUP PDFBibTeX XMLCite \textit{E. J. Candès} and \textit{J. Romberg}, Found. Comput. Math. 6, No. 2, 227--254 (2006; Zbl 1102.94020) Full Text: DOI arXiv Link