# zbMATH — the first resource for mathematics

Accelerated iterative hard thresholding algorithm for $$l_0$$ regularized regression problem. (English) Zbl 1441.90121
Summary: In this paper, we propose an accelerated iterative hard thresholding algorithm for solving the $$l_0$$ regularized box constrained regression problem. We substantiate that there exists a threshold, if the extrapolation coefficients are chosen below this threshold, the proposed algorithm is equivalent to the accelerated proximal gradient algorithm for solving a corresponding constrained convex problem after finite iterations. Under some proper conditions, we get that the sequence generated by the proposed algorithm is convergent to a local minimizer of the $$l_0$$ regularized problem, which satisfies a desired lower bound. Moreover, when the data fitting function satisfies the error bound condition, we prove that both the iterate sequence and the corresponding sequence of objective function values are R-linearly convergent. Finally, we use several numerical experiments to verify our theoretical results.
##### MSC:
 90C25 Convex programming
Full Text:
##### References:
 [1] Aubin, JP; Cellina, A., Differential Inclusions: Set-Valued Maps and Viability Theory (1984), Berlin: Springer, Berlin · Zbl 0538.34007 [2] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009 [3] Bian, W.; Chen, XJ, Optimality and complexity for constrained optimization problems with nonconvex regularization, Math. Oper. Res., 42, 4, 1063-1084 (2017) · Zbl 1386.90167 [4] Blumensath, T.; Davies, ME, Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14, 5-6, 629-654 (2008) · Zbl 1175.94060 [5] Blumensath, T.; Davies, ME, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27, 3, 265-274 (2009) · Zbl 1174.94008 [6] Blumensath, T.; Davies, ME, Normalized iterative hard thresholding: guaranteed stability and performance, IEEE J. Sel. Top. Signal Process., 4, 2, 298-309 (2010) [7] Candes, EJ; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017 [8] Candes, EJ; Tao, T., Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121 [9] Candes, EJ; Wakin, MB; Boyd, SP, Enhancing sparsity by reweighted $$l_1$$ minimization, J. Fourier Anal. Appl., 14, 5-6, 877-905 (2008) · Zbl 1176.94014 [10] Chambolle, A., An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20, 1-2, 89-97 (2004) · Zbl 1366.94048 [11] Chambolle, A.; DeVore, RA; Lee, NY; Lucier, BJ, Nonlinear wavelet image processing: variational problems, compression, and noise removal through wavelet shrinkage, IEEE Trans. Image Process., 7, 3, 319-335 (1998) · Zbl 0993.94507 [12] Chartrand, R., Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14, 10, 707-710 (2007) [13] Chartrand, R.; Staneva, V., Restricted isometry properties and nonconvex compressive sensing, Inverse Probl., 24, 3, 1-14 (2008) · Zbl 1143.94004 [14] Chen, S.; Cowan, CFN; Grant, PM, Orthogonal least-squares learning algorithm for radial basis function networks, IEEE Trans. Neural Netw., 2, 2, 302-309 (1991) [15] Chen, XJ; Ng, MK; Zhang, C., Non-Lipschitz $$l_p$$-regularization and box constrained model for image restoration, IEEE Trans. Image Process., 21, 12, 4709-4721 (2012) · Zbl 1373.94080 [16] Donoho, DL, Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 [17] Fan, JQ; Li, RZ, Variable selection via nonconcave penalized likelihood and its oracle properties, J. Am. Stat. Assoc., 96, 456, 1348-1360 (2001) · Zbl 1073.62547 [18] Figueiredo, MAT; Nowak, RD, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 12, 8, 906-916 (2003) · Zbl 1279.94015 [19] Foucart, S.; Lai, MJ, Sparsest solutions of underdetermined linear systems via $$l_q$$-minimization for \(0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.