Abstract
The purpose of this contribution is to generalize some recent results on sparse representations of signals in redundant bases. The question that is considered is the following: given a matrix A of dimension (n,m) with m>n and a vector b=Ax, find a sufficient condition for b to have a unique sparsest representation x as a linear combination of columns of A. Answers to this question are known when A is the concatenation of two unitary matrices and either an extensive combinatorial search is performed or a linear program is solved. We consider arbitrary A matrices and give a sufficient condition for the unique sparsest solution to be the unique solution to both a linear program or a parametrized quadratic program. The proof is elementary and the possibility of using a quadratic program opens perspectives to the case where b=Ax+e with e a vector of noise or modeling errors.
Keywords
Concatenation (mathematics)Dimension (graph theory)MathematicsQuadratic equationSparse approximationLinear systemMatrix (chemical analysis)Discrete mathematicsCombinatoricsAlgorithmAlgebra over a fieldPure mathematics
Affiliated Institutions
Related Publications
Fast Training of Support Vector Machines Using Sequential Minimal Optimization
This chapter describes a new algorithm for training Support Vector Machines: Sequential Minimal Optimization, or SMO. Training a Support Vector Machine (SVM) requires the soluti...
The Theory of Matrices
Volume 2: XI. Complex symmetric, skew-symmetric, and orthogonal matrices: 1. Some formulas for complex orthogonal and unitary matrices 2. Polar decomposition of a complex matrix...
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....
The algebraic eigenvalue problem
Theoretical background Perturbation theory Error analysis Solution of linear algebraic equations Hermitian matrices Reduction of a general matrix to condensed form Eigenvalues o...
The Approximation of One Matrix by Another of Lower Rank
The mathematical problem of approximating one matrix by another of lower rank is closely related to the fundamental postulate of factor-theory. When formulated as a least-square...
Publication Info
- Year
- 2004
- Type
- article
- Volume
- 50
- Issue
- 6
- Pages
- 1341-1344
- Citations
- 568
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
568
OpenAlex
Cite This
J.-J. Fuchs
(2004).
On Sparse Representations in Arbitrary Redundant Bases.
IEEE Transactions on Information Theory
, 50
(6)
, 1341-1344.
https://doi.org/10.1109/tit.2004.828141
Identifiers
- DOI
- 10.1109/tit.2004.828141