Quantitative robust uncertainty principles and optimally sparse decompositions

In this paper we develop a robust uncertainty principle for finite signals in C-N which states that, for nearly all choices T, Omega subset of {0,,,,, N - 1} such that vertical bar T vertical bar + vertical bar Omega vertical bar asymptotic to (log N)(-1/2) . N, there is no signal f supported on T whose discrete Fourier transform (f) over cap 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 (f) over cap 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 [GRAPHICS] We show that if a generic signal f has a decomposition (eel, C12) using spike and frequency locations in T and Omega, respectively, and obeying vertical bar T vertical bar +vertical bar Omega vertical bar <= Const . (log N)(-1/2) . N, then (alpha(1), alpha(2)) is the unique sparsest possible decomposition (all other decompositions have more nonzero terms). In addition, if vertical bar T vertical bar + vertical bar Omega vertical bar <= Const . (log N)(-1) . 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) of C-N. For nearly all choices Gamma(1), Gamma(2) subset of {0,..., N - 1} obeying vertical bar Gamma(1)vertical bar + vertical bar Gamma(2)vertical bar asymptotic to mu(Phi(1), Phi(2))(-2) . (log N)(-m) where m <= 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).