2004/11/12 by Emmanuel J. Candès, Emmanuel Candes, Justin Romberg +2 · 1 citation
Decision Sciences · Engineering · Mathematics · #41A45 #42A10 #94A12 #Classical Analysis and ODEs (math.CA) #Control Systems and Identification #FOS: Mathematics #Fault Detection and Control Systems #Probabilistic and Robust Engineering Design #math.CA #msc:41A45 #msc:42A10 #msc:94A12
paper · pdf · doi:10.48550/arxiv.math/0411273
25 pages, 9 figures
arxiv created 2004/11/12 · openalex publication_date 2004/11/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We develop a robust uncertainty principle for finite signals in CN which states that for almost all subsets T,W of 0,...,N-1 such that |T|+|W| ~ (log N)^(-1/2) N, there is no sigal f supported on T whose discrete Fourier transform is supported on W. 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 its Fourier transform is concentrated on W. 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 using spike and frequency locations in T and W respectively, and obeying |T| + |W| <= C (log N)-1/2 N, then this is the unique sparsest possible decomposition (all other decompositions have more non-zero terms). In addition, if |T| + |W| <= C (log N)-1 N, then this sparsest decomposition can be found by solving a convex optimization problem.