Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions

Emmanuel Candes, Justin Romberg

We develop a robust uncertainty principle for finite signals in C^N 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 si…