Iterative Soft/Hard Thresholding with Homotopy Continuation for Sparse Recovery

Abstract

In this note, we analyze an iterative soft / hard thresholding algorithm with homotopy continuation for recovering a sparse signal $x^{†}$ from noisy data of a noise level $\epsilon$. Under suitable regularity and sparsity conditions, we design a path along which the algorithm can find a solution $x^{\ast }$ which admits a sharp reconstruction error $\Vert x^{\ast }-x^{†}{\Vert }_{{\ell }^{\infty }}=O(\epsilon )$ with an iteration complexity $O(\frac{\ln \epsilon }{\ln \gamma }np)$, where $n$ and $p$ are problem dimensionality and $\gamma \in (0,1)$ controls the length of the path. Numerical examples are given to illustrate its performance.

5 pages, 4 figures

References in corpus (4)

• Nearly unbiased variable selection under minimax concave penalty
• Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• A Primal Dual Active Set Algorithm with Continuation for Compressed Sensing

Cited by in corpus (3)

• The springback penalty for robust signal recovery
• Deep Network Classification by Scattering and Homotopy Dictionary Learning
• SNAP: A semismooth Newton algorithm for pathwise optimization with optimal local convergence rate and oracle properties