The iterative hard thresholding(IHT)algorithm is a powerful and efficient algorithm for solving l_(0)-regularized problems and inspired many applications in sparse-approximation and image-processing fields.Recently,so...The iterative hard thresholding(IHT)algorithm is a powerful and efficient algorithm for solving l_(0)-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_(0)-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_(0)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.展开更多
基金supported by the National Natural Science Foundation of China(No.91330102)973 program(No.2015CB856000).
文摘The iterative hard thresholding(IHT)algorithm is a powerful and efficient algorithm for solving l_(0)-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_(0)-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_(0)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.
