Abstract:

The iterative hard thresholding (IHT) algorithm is a powerful and efficient algorithm for solving l₀-regularized problems and inspired many applications in sparse approximation and image-processing fields. Recently, some convergence results are established for the proximal scheme of IHT, namely proximal iterative hard thresholding (PIHT) algorithm (Blumensath and Davies, in J Fourier Anal Appl 14:629–654, 2008; Hu et al., Methods 67:294–303, 2015; Lu, Math Program 147:125– 154, 2014; Trzasko et al., IEEE/SP 14th Workshop on Statistical Signal Processing, 2007) on solving the related l₀-optimization problems. However, the complexity analysis for the PIHT algorithm is not well explored. In this paper, we aim to provide some complexity estimations for the PIHT sequences. In particular, we show that the complexity of the sequential iterate error is at o(1/k). Under the assumption that the objective function is composed of a quadratic convex function and l₀ regularization, we show that the PIHT algorithm has R-linear convergence rate. Finally, we illustrate some applications of this algorithm for compressive sensing reconstruction and sparse learning and validate the estimated error bounds.

Key words: l_0 Regularization ·, Iterative hard thresholding ·, Proximal algorithm ·Convergence rate ·, R-linear