A fast approach for overcomplete sparse decomposition based on smoothed L0 norm

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 L1 norm using Linear Programming (LP) techniques, our algorithm tries to directly minimize the L0 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.

Accepted in IEEE Transactions on Signal Processing. For MATLAB codes, see (http://ee.sharif.ir/~SLzero). File replaced, because Fig. 5 was missing erroneously

Cited by in corpus (58)

• Expectation-Maximization Gaussian-Mixture Approximate Message Passing
• Sparse Regularization via Convex Analysis
• Compressed Sensing for Energy-Efficient Wireless Telemonitoring of Noninvasive Fetal ECG via Block Sparse Bayesian Learning
• Sparse Signal Estimation by Maximally Sparse Convex Optimization
• Performance Analysis of l_0 Norm Constraint Least Mean Square Algorithm
• A Majorize-Minimize subspace approach for l2-l0 image regularization
• Total Variation Denoising via the Moreau Envelope
• ${\ell }_0$-Motivated Low-Rank Sparse Subspace Clustering
• Backhaul Limited Asymmetric Cooperation for MIMO Cellular Networks via Semidefinite Relaxation
• Rakeness in the design of Analog-to-Information Conversion of Sparse and Localized Signals
• Block-Sparsity-Induced Adaptive Filter for Multi-Clustering System Identification
• Enhanced Sparsity by Non-Separable Regularization
• Homotopy based algorithms for ${\ell }_0$-regularized least-squares
• On the Achievability of Cramér-Rao Bound In Noisy Compressed Sensing
• Recovery of Low-Rank Matrices under Affine Constraints via a Smoothed Rank Function
• Successive Concave Sparsity Approximation for Compressed Sensing
• On the stable recovery of the sparsest overcomplete representations in presence of noise
• Optimized projections for compressed sensing via rank-constrained nearest correlation matrix
• ICR: Iterative Convex Refinement for Sparse Signal Recovery Using Spike and Slab Priors
• Iterative Concave Rank Approximation for Recovering Low-Rank Matrices
• Sparse Bayesian Estimation of Parameters in Linear-Gaussian State-Space Models
• Improving A*OMP: Theoretical and Empirical Analyses With a Novel Dynamic Cost Model
• Model-Based Photoacoustic Image Reconstruction using Compressed Sensing and Smoothed L0 Norm
• Sparse Vector Distributions and Recovery from Compressed Sensing
• Compressed sensing reconstruction using Expectation Propagation
• Robustness of Sparse Recovery via $F$-minimization: A Topological Viewpoint
• Iterative Null-space Projection Method with Adaptive Thresholding in Sparse Signal Recovery and Matrix Completion
• Oracle-order Recovery Performance of Greedy Pursuits with Replacement against General Perturbations
• Improving Smoothed l0 Norm in Compressive Sensing Using Adaptive Parameter Selection
• Convolution based smooth approximations to the absolute value function with application to non-smooth regularization
• A Unified Framework for Constructing Nonconvex Regularizations
• Bayesian Cramér-Rao Bound for Noisy Non-Blind and Blind Compressed Sensing
• On the error of estimating the sparsest solution of underdetermined linear systems
• Transduction with Matrix Completion Using Smoothed Rank Function
• Dynamic Sensor Selection for Reliable Spectrum Sensing via E-Optimal Criterion
• Thermal Source Localization Through Infinite-Dimensional Compressed Sensing
• Measurement-Adaptive Sparse Image Sampling and Recovery
• A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning
• Affine matrix rank minimization problem via non-convex fraction function penalty
• Compression via Compressive Sensing : A Low-Power Framework for the Telemonitoring of Multi-Channel Physiological Signals
• Nonconvex Regularization Based Sparse Recovery and Demixing with Application to Color Image Inpainting
• Bayesian Hypothesis Testing for Sparse Representation
• Binary Compressive Sensing via Smoothed ${\ell }_0$ Gradient Descent
• A New Nonconvex Strategy to Affine Matrix Rank Minimization Problem
• Fast Greedy Approaches for Compressive Sensing of Large-Scale Signals
• The Convergence Guarantees of a Non-convex Approach for Sparse Recovery
• Ideological Sublations: Resolution of Dialectic in Population-based Optimization
• Adaptive matching pursuit for sparse signal recovery
• Iterative Methods for Sparse Signal Reconstruction from Level Crossings
• Efficient and Robust Recovery of Sparse Signal and Image Using Generalized Nonconvex Regularization
• Compressive sensing based Bayesian sparse channel estimation for OFDM communication systems: high performance and low complexity
• Matrix Coherency Graph: A Tool for Improving Sparse Coding Performance
• Gradually Atom Pruning for Sparse Reconstruction and Extension to Correlated Sparsity
• Projection Neural Network for a Class of Sparse Regression Problems with Cardinality Penalty
• Robust Dictionary based Data Representation
• Sparse Diffusion Steepest-Descent for One Bit Compressed Sensing in Wireless Sensor Networks
• Scan-based Compressed Terahertz Imaging and Real-Time Reconstruction via the Complex-valued Fast Block Sparse Bayesian Learning Algorithm
• A New Trend in Optimization on Multi Overcomplete Dictionary toward Inpainting