×

Quantitative robust uncertainty principles and optimally sparse decompositions. (English) Zbl 1102.94020

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\).

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

Software:

QRUP
PDFBibTeX XMLCite
Full Text: DOI arXiv Link