Mathematics – Classical Analysis and ODEs
Scientific paper
2004-11-12
Mathematics
Classical Analysis and ODEs
25 pages, 9 figures
Scientific paper
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 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.
Candes Emmanuel
Romberg Justin
No associations
LandOfFree
Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-87555