Abstract
An elementary proof of a basic uncertainty principle concerning pairs of representations of R/sup N/ vectors in different orthonormal bases is provided. The result, slightly stronger than stated before, has a direct impact on the uniqueness property of the sparse representation of such vectors using pairs of orthonormal bases as overcomplete dictionaries. The main contribution in this paper is the improvement of an important result due to Donoho and Huo (2001) concerning the replacement of the l/sub 0/ optimization problem by a linear programming (LP) minimization when searching for the unique sparse representation.
Keywords
Orthonormal basisSparse approximationMathematicsUniquenessRepresentation (politics)Linear programmingProperty (philosophy)MinificationMathematical optimizationCombinatoricsAlgebra over a fieldDiscrete mathematicsApplied mathematicsAlgorithmPure mathematicsMathematical analysis
Affiliated Institutions
Related Publications
Atomic Decomposition by Basis Pursuit
The time-frequency and time-scale communities have recently developed a large number of overcomplete waveform dictionaries --- stationary wavelets, wavelet packets, cosine packe...
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 ...
Image Super-Resolution Via Sparse Representation
This paper presents a new approach to single-image super-resolution, based on sparse signal representation. Research on image statistics suggests that image patches can be well-...
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...
Beta Process Joint Dictionary Learning for Coupled Feature Spaces with Application to Single Image Super-Resolution
This paper addresses the problem of learning over-complete dictionaries for the coupled feature spaces, where the learned dictionaries also reflect the relationship between the ...
Publication Info
- Year
- 2002
- Type
- article
- Volume
- 48
- Issue
- 9
- Pages
- 2558-2567
- Citations
- 667
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
667
OpenAlex
Cite This
Michael Elad,
Alfred M. Bruckstein⋆
(2002).
A generalized uncertainty principle and sparse representation in pairs of bases.
IEEE Transactions on Information Theory
, 48
(9)
, 2558-2567.
https://doi.org/10.1109/tit.2002.801410
Identifiers
- DOI
- 10.1109/tit.2002.801410