Abstract
Given a dictionary D = { d k } of vectors d k , we seek to represent a signal S as a linear combination S = ∑ k γ( k ) d k , with scalar coefficients γ ( k ). In particular, we aim for the sparsest representation possible. In general, this requires a combinatorial optimization process. Previous work considered the special case where D is an overcomplete system consisting of exactly two orthobases and has shown that, under a condition of mutual incoherence of the two bases, and assuming that S has a sufficiently sparse representation, this representation is unique and can be found by solving a convex optimization problem: specifically, minimizing the ℓ 1 norm of the coefficients γ̱. In this article, we obtain parallel results in a more general setting, where the dictionary D can arise from two or several bases, frames, or even less structured systems. We sketch three applications: separating linear features from planar ones in 3D data, noncooperative multiuser encoding, and identification of over-complete independent component models.
Keywords
Sparse approximationMinificationMathematicsOperator (biology)Convex optimizationScalar (mathematics)Representation (politics)CombinatoricsNorm (philosophy)Optimization problemAlgorithmRegular polygonComputer scienceMathematical optimization
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 ...
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...
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-...
Regularization Paths for Generalized Linear Models via Coordinate Descent
We develop fast algorithms for estimation of generalized linear models with convex penalties. The models include linear regression, two-class logistic regression, and multi- nom...
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...
Publication Info
- Year
- 2003
- Type
- article
- Volume
- 100
- Issue
- 5
- Pages
- 2197-2202
- Citations
- 2887
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
2887
OpenAlex
Cite This
David L. Donoho,
Michael Elad
(2003).
Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ <sup>1</sup> minimization.
Proceedings of the National Academy of Sciences
, 100
(5)
, 2197-2202.
https://doi.org/10.1073/pnas.0437847100
Identifiers
- DOI
- 10.1073/pnas.0437847100