Iterative Sparsification-Projection: Fast and Robust Sparse Signal Approximation
- 27 June 2016
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 64 (21) , 5536-5548
Abstract
In this paper, we address recovery of sparse signals from compressed measurements, and sparse signal approximation, which have received considerable attention over the last decade. First, we revisit smoothed L0 (SL0), a well-known sparse recovery algorithm, and give some insights into it that have not been noticed previously. Specifically, we re-derive the SL0 algorithm based on proximal methods, and using recent results in solving nonconvex problems by proximal algorithms, we provide a convergence guarantee for it. In addition, inspired by this derivation, we propose a general family of algorithms, which we call iterative sparsification-projection (ISP), having SL0 as a special member. Our algorithmic framework starts with an initial guess for the unknown sparse vector, and then iteratively sparsifies it (using a fixed threshold) followed by projecting the result onto the admissible solution set. The threshold is then decreased, and the same process is repeated. The algorithm terminates when the threshold becomes sufficiently small, or another stopping criterion is satisfied. We also propose a robust projection to handle the situations with observation noise or model uncertainties. Our extensive simulations confirm the promising performance of the ISP algorithms compared with some well-known algorithms.Keywords
Funding Information
- Center for International Scientific Studies and Collaboration
This publication has 41 references indexed in Scilit:
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methodsMathematical Programming, 2011
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersFoundations and Trends in Machine Learning, 2011
- Message-passing algorithms for compressed sensingProceedings of the National Academy of Sciences, 2009
- Iterative hard thresholding for compressed sensingApplied and Computational Harmonic Analysis, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed $\ell ^{0}$ NormIEEE Transactions on Signal Processing, 2008
- Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and ConvergenceSIAM Journal on Optimization, 2008
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraintCommunications on Pure and Applied Mathematics, 2004
- Deterministic annealing for clustering, compression, classification, regression, and related optimization problemsProceedings of the IEEE, 1998
- Updating the Inverse of a MatrixSIAM Review, 1989