Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions

Abstract

In this paper we develop a robust uncertainty principle for finite signals in C^N which states that, for nearly all choices T,Ω⊂{0,…,N−1} such that |T|+|Ω|≍(logN)−^(1/2)⋅N, there is no signal f supported on T whose discrete Fourier transform f is supported on Ω. 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 is concentrated on Ω. 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) = ∑t∈Tα1(t)δ(s−t)+∑ω∈Ωα2(ω)e^(i2πωs/N)/√N. We show that if a generic signal f has a decomposition (α_1,α_2) using spike and frequency locations in T and Ω, respectively, and obeying |T|+|Ω|≤Const⋅(logN)^(−1/2)⋅N, then (α_1,α_2) is the unique sparsest possible decomposition (all other decompositions have more nonzero terms). In addition, if |T|+|Ω|≤Const⋅(logN)^(−1)⋅N, then the sparsest (α_1,α_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,Ω) for which the above properties do not hold can be upper bounded by quantities like N^(-α) for large values of α.α. The QRUP (and the application to finding sparse representations) can be extended to general pairs of orthogonal bases Φ_1,Φ_2ofC^N. For nearly all choices Γ_1,Γ_2⊂{0,…,N−1} obeying |Γ_1|+|Γ_2|≍μ(Φ_1,Φ_2)^(−2)⋅(logN)^(−m), where m≤6 , there is no signal f such that Φ_1f is supported on Γ_1 and Φ2_f is supported on Γ_2 where μ(Φ_1,Φ_2) is the mutual coherence between Φ_1 and Φ_2.

Files

Additional details