Iterative Soft/Hard Thresholding with Homotopy Continuation for Sparse Recovery
It provides a theoretical guarantee for a practical algorithm to recover sparse signals from noisy data, but the result is incremental as it combines existing techniques.
The paper proposes an iterative soft/hard thresholding algorithm with homotopy continuation for sparse recovery, achieving a sharp reconstruction error of O(ε) with iteration complexity O(ln ε / ln γ * np).
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 $ε$. Under suitable regularity and sparsity conditions, we design a path along which the algorithm can find a solution $x^*$ which admits a sharp reconstruction error $\|x^* - x^†\|_{\ell^\infty} = O(ε)$ with an iteration complexity $O(\frac{\ln ε}{\ln γ} np)$, where $n$ and $p$ are problem dimensionality and $γ\in (0,1)$ controls the length of the path. Numerical examples are given to illustrate its performance.