A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed $\ell ^{0}$ Norm
Top Cited Papers
- 31 October 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 57 (1), 289-301
- https://doi.org/10.1109/tsp.2008.2007606
Abstract
In this paper, a fast algorithm for overcomplete sparse decomposition, called SL0, is proposed. The algorithm is essentially a method for obtaining sparse solutions of underdetermined systems of linear equations, and its applications include underdetermined sparse component analysis (SCA), atomic decomposition on overcomplete dictionaries, compressed sensing, and decoding real field codes. Contrary to previous methods, which usually solve this problem by minimizing the l 1 norm using linear programming (LP) techniques, our algorithm tries to directly minimize the l 1 norm. It is experimentally shown that the proposed algorithm is about two to three orders of magnitude faster than the state-of-the-art interior-point LP solvers, while providing the same (or better) accuracy.Keywords
Other Versions
This publication has 25 references indexed in Scilit:
- Estimating the mixing matrix in Sparse Component Analysis (SCA) based on partial k-dimensional subspace clusteringNeurocomputing, 2008
- Fast Sparse Representation Based on Smoothed ℓ0 NormPublished by Springer Science and Business Media LLC ,2007
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraintCommunications on Pure and Applied Mathematics, 2004
- Analysis of Sparse Representation and Blind Source SeparationNeural Computation, 2004
- An EM algorithm for wavelet-based image restorationIEEE Transactions on Image Processing, 2003
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimizationProceedings of the National Academy of Sciences, 2003
- Underdetermined blind source separation using sparse representationsSignal Processing, 2001
- Atomic Decomposition by Basis PursuitSIAM Journal on Scientific Computing, 1998
- Matching pursuits with time-frequency dictionariesIEEE Transactions on Signal Processing, 1993