Iterative Sparsification-Projection: Fast and Robust Sparse Signal Approximation

摘要

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.