Abstract
This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f ∈ C N and a randomly chosen set of frequencies Ω of mean size τN. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set Ω? A typical result of this paper is as follows: for each M> 0, suppose that f obeys #{t, f(t) = 0} ≤ α(M) · (log N) −1 · #Ω, then with probability at least 1 − O(N −M), f can be reconstructed exactly as the solution to the ℓ1 minimization problem |g(t)|, s.t. ˆg(ω) = ˆ f(ω) for all ω ∈ Ω.
Keywords
OmegaCombinatoricsMathematicsSignal reconstructionSuperposition principleConvex optimizationDiscrete mathematicsRegular polygonAlgorithmSignal processingMathematical analysisPhysicsComputer scienceQuantum mechanicsGeometry
Affiliated Institutions
Related Publications
Uncertainty principles and ideal atomic decomposition
Suppose a discrete-time signal S(t), 0/spl les/t<N, is a superposition of atoms taken from a combined time-frequency dictionary made of spike sequences 1/sub {t=/spl tau/}/ and ...
Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
Suppose we are given a vector f in a class F ⊂ ℝN, e.g., a class of digital signals or digital images. How many linear measurements do we need to make about f to be able to reco...
Decoding by Linear Programming
This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e....
Sparsity and incoherence in compressive sampling
We consider the problem of reconstructing a sparse signal x^0\\in{\\bb R}^n from a limited number of linear measurements. Given m randomly selected samples of Ux0, where U is an...
The Variation with Frequency of the Power Loss in Dielectrics
Variation of the power loss in dielectrics with frequency, 500 to 1,000,000 cycles.---(1) A new bridge method of measurement is described. This bridge has two resistance ratio a...
Publication Info
- Year
- 2006
- Type
- article
- Volume
- 52
- Issue
- 2
- Pages
- 489-509
- Citations
- 15472
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
15472
OpenAlex
Cite This
Emmanuel J. Candès,
Justin Romberg,
Terence Tao
(2006).
Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information.
IEEE Transactions on Information Theory
, 52
(2)
, 489-509.
https://doi.org/10.1109/tit.2005.862083
Identifiers
- DOI
- 10.1109/tit.2005.862083