A Note on the Complexity of Proximal Iterative Hard Thresholding Algorithm  

作　　者：Xue Zhang Xiao-Qun Zhang 

机构地区：[1]Department of Mathematics,Shanghai Jiao Tong University,Shanghai 200240,China [2]Institute of Natural Sciences,Shanghai Jiao Tong University,Shanghai 200240,China

出　　处：《Journal of the Operations Research Society of China》2015年第4期459-473,共15页中国运筹学会会刊（英文）

基　　金：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.

关 键 词：l_(0)Regularization Iterative hard thresholding Proximal algorithm Convergence rate R-linear 

分 类 号：O17[理学—数学]