A Note on the Complexity of Proximal Iterative Hard Thresholding Algorithm

作     者：Xue Zhang Xiao-Qun Zhang 

作者机构：Department of MathematicsShanghai Jiao Tong UniversityShanghai 200240China Institute of Natural SciencesShanghai Jiao Tong UniversityShanghai 200240China 

出 版 物：《Journal of the Operations Research Society of China》 (中国运筹学会会刊（英文）)

年 卷 期：2015年第3卷第4期

页      面：459-473页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：supported by the National Natural Science Foundation of China(No.91330102) 973 program(No.2015CB856000) 

主　　题：l_(0)Regularization Iterative hard thresholding Proximal algorithm Convergence rate R-linear 

摘      要：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 ***,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 ***,the complexity analysis for the PIHT algorithm is not well *** this paper,we aim to provide some complexity estimations for the PIHT *** 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 ***,we illustrate some applications of this algorithm for compressive sensing reconstruction and sparse learning and validate the estimated error bounds.