Iterative Soft/Hard Thresholding With Homotopy Continuation for Sparse Recovery.

In this note, we analyze an iterative soft/hard thresholding algorithm with homotopy continuation for recovering a sparse signal x^\dagger 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^*, which admits a sharp reconstruction error \Vert x^* - x^\dagger \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. [ABSTRACT FROM PUBLISHER]