A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed $\ell ^{0}$ Norm

By Hossein Mohimani, Massoud Babaie-Zadeh, Christian Jutten. IEEE Transactions on Signal Processing, 2008

1,125 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/385211eacf0c355f3b4753205f60bace1901b459

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Expectation-Maximization Gaussian-Mixture Approximate Message Passing (2012, methodology): “For comparison, we show the performance of the proposed EM-GM-GAMP (in “sparse” mode), EM-BG-GAMP [12], Bayesian Compressive Sensing (BCS) [11], Sparse Bayesian Learning [10] (via T-MSBL [15]), debiased genie-aided8 Lasso (via SPGL1 [16]), and Smoothed-l0 (SL0) [17].”
Compressed Sensing for Energy-Efficient Wireless Telemonitoring of Noninvasive Fetal ECG Via Block Sparse Bayesian Learning (2012, neutral): “The bottom two panels in Figure 9 (b) show the recovered segment and the recovered wavelet coefﬁcients by SL0, respectively.”
Sparse Regularization via Convex Analysis (2017, background): “9]. 2 1.1 Related work Many prior works have proposed non-convex penalties that strongly promote sparsity or describe algorithms for solving the sparse-regularized linear least squares problem, e.g., [11,13,15,16,19,25, 30,31,38,39,43,47,58,64,66]. However, most of these papers (i) use separable (ad”
Direction-of-Arrival Estimation Using a Mixed $\ell _{2,0}$ Norm Approximation (2010, methodology): “The key feature of the algorithm is that it represents the snapshots as some jointly sparse linear combinations of the columns of a manifold matrix.”