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^{d} a g

from noisy data of a noise level

e p s i l o n

. 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^{d} a g |_{e l l^{i} n f t y} = O (e p s i l o n)

with an iteration complexity

O (f r a c l n e p s i l o n l n g a m m a n p)

, where

n

and

p

are problem dimensionality and

g a m m a i n (0, 1)

controls the length of the path. Numerical examples are given to illustrate its performance.

This page was built for publication: Iterative Soft/Hard Thresholding with Homotopy Continuation for Sparse Recovery