On Sparse Representations in Arbitrary Redundant Bases
- 1 June 2004
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 50 (6), 1341-1344
- https://doi.org/10.1109/tit.2004.828141
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
This publication has 9 references indexed in Scilit:
- Sparse representations in unions of basesIEEE Transactions on Information Theory, 2003
- Detection and estimation of superimposed signalsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A generalized uncertainty principle and sparse representation in pairs of basesIEEE Transactions on Information Theory, 2002
- Uncertainty principles and ideal atomic decompositionIEEE Transactions on Information Theory, 2001
- On the application of the global matched filter to DOA estimation with uniform circular arraysIEEE Transactions on Signal Processing, 2001
- Minimal L/sub 1/-norm reconstruction function for oversampled signals: applications to time-delay estimationIEEE Transactions on Information Theory, 2000
- Multipath time-delay detection and estimationIEEE Transactions on Signal Processing, 1999
- Atomic Decomposition by Basis PursuitSIAM Journal on Scientific Computing, 1998
- Extension of the Pisarenko method to sparse linear arraysIEEE Transactions on Signal Processing, 1997