×

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
PDF BibTeX Cite
Full Text: DOI
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<q \le 1\), Appl. Comput. Harmon. Anal., 26, 3, 395-407 (2009) · Zbl 1171.90014
[20] Hale, ET; Yin, WT; Zhang, Y., Fixed-point continuation for \(l_1\)-minimization: methodology and convergence, SIAM J. Optim., 19, 3, 1107-1130 (2008) · Zbl 1180.65076
[21] Hale, ET; Yin, WT; Zhang, Y., Fixed-point continuation applied to compressed sensing: implementation and numerical experiments, J. Comput. Math., 28, 2, 170-194 (2010) · Zbl 1224.65153
[22] Huang, J.; Horowitz, JL; Ma, SG, Asymptotic properties of bridge estimators in sparse high-dimensional regression models, Ann. Stat., 36, 2, 587-613 (2008) · Zbl 1133.62048
[23] Johnstone, PR; Moulin, P., Local and global convergence of a general inertial proximal splitting scheme for minimizing composite functions, Comput. Optim. Appl, 67, 2, 259-292 (2017) · Zbl 1376.90046
[24] Lan, GH; Monteiro, RDC, Iteration-complexity of first-order penalty methods for convex programming, Math. Program., 138, 1-2, 115-139 (2013) · Zbl 1282.90129
[25] Le Thi, HA; Dinh, TP; Le, HM; Vo, XT, DC approximation approaches for sparse optimization, Eur. J. Oper. Res., 244, 1, 26-46 (2015) · Zbl 1346.90819
[26] Liao, JG; Chin, KV, Logistic regression for disease classification using microarray data: model selection in a large \(p\) and small \(n\) case, Bioinformatics, 23, 15, 1945-1951 (2007)
[27] Lu, ZS, Iterative hard thresholding methods for \(l_0\) regularized convex cone programming, Math. Program., 147, 1-2, 125-154 (2014) · Zbl 1308.65094
[28] Lu, ZS; Zhang, Y., Sparse approximation via penalty decomposition methods, SIAM J. Optim., 23, 4, 2448-2478 (2013) · Zbl 1295.90056
[29] Luo, ZQ; Tseng, P., Error bounds and convergence analysis of feasible descent methods: a general approach, Ann. Oper. Res., 46, 1, 157-178 (1993) · Zbl 0793.90076
[30] Luo, ZQ; Tseng, P., On the convergence rate of dual ascent methods for linearly constrained convex minimization, Math. Oper. Res., 18, 4, 846-867 (1993) · Zbl 0804.90103
[31] Mallat, SG; Zhang, ZF, Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process., 41, 12, 3397-3415 (1993) · Zbl 0842.94004
[32] Nesterov, Y., Gradient methods for minimizing composite functions, Math. Program., 140, 1, 125-161 (2013) · Zbl 1287.90067
[33] Nikolova, M., Local strong homogeneity of a regularized estimator, SIAM J. Appl. Math., 61, 2, 633-658 (2000) · Zbl 0991.94015
[34] Nikolova, M., Description of the minimizers of least squares regularized with \(l_0\) norm. Uniqueness of the global minimizer, SIAM J. Imaging Sci., 6, 2, 904-937 (2013) · Zbl 1281.65092
[35] Pati, Y.C., Rezaiifar, R., Krishnaprasad, P.S.: Orthogonal matching pursuit-recursive function approximation with applications to wavelet decomposition. In: Conference Record of the 27th Asilomar Conference on Signal, Systems and Computers vol. 1-2, pp. 40-44 (1993)
[36] Peleg, D.; Meir, R., A bilinear formulation for vector sparsity optimization, Signal Process., 88, 2, 375-389 (2008) · Zbl 1186.94273
[37] Philiastides, MG; Sajda, P., Temporal characterization of the neural correlates of perceptual decision making in the human brain, Cereb. Cortex, 16, 4, 509-518 (2006)
[38] Pilanci, M.; Wainwright, MJ; El Ghaoui, L., Sparse learning via boolean relaxations, Math. Program., 151, 1, 63-87 (2015) · Zbl 1328.90106
[39] Rockafellar, RT; Wets, RJB, Variational Analysis (1998), Berlin: Springer, Berlin
[40] Soubies, E.; Blanc-Feraud, L.; Aubert, G., A continuous exact \(l_0\) penalty (CEL0) for least squares regularized problem, SIAM J. Imaging Sci., 9, 1, 490-494 (2016) · Zbl 1346.65028
[41] Tropp, JA, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inf. Theory, 50, 10, 2231-2242 (2004) · Zbl 1288.94019
[42] Tropp, JA, Just relax: convex programming methods for identifying sparse signals in noise, IEEE Trans. Inf. Theory, 52, 3, 1030-1051 (2006) · Zbl 1288.94025
[43] Tseng, P.; Yun, SW, A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training, Comput. Optim. Appl., 47, 2, 179-206 (2010) · Zbl 1226.90062
[44] Tsuruoka, Y.; McNaught, J.; Tsujii, J.; Ananiadou, S., Learning string similarity measures for gene/protein name dictionary look-up using logistic regression, Bioinformatics, 23, 20, 2768-2774 (2007)
[45] Wen, B.; Chen, XJ; Pong, TK, Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems, SIAM J. Optim., 27, 1, 124-145 (2017) · Zbl 1359.90138
[46] Wright, SJ; Nocedal, J., Numerical Optimization (2006), New York: Springer, New York
[47] Xu, ZB; Chang, XY; Xu, FM; Zhang, H., \({L}_{1/2}\) regularization: a thresholding representation theory and a fast solver, IEEE Trans. Neural Netw. Learn. Syst., 23, 7, 1013-1027 (2012)
[48] Yang, F.; Shen, Y.; Liu, ZS, The proximal alternating iterative hard thresholding method for \(l_0\) minimization, with complexity \({O}(1/\sqrt{k})\), J. Comput. Appl. Math., 311, 115-129 (2017) · Zbl 1354.49071
[49] Yap, PT; Zhang, Y.; Shen, DG, Multi-tissue decomposition of diffusion MRI signals via \(l_0\) sparse-group estimation, IEEE Trans. Image Process., 25, 9, 4340-4353 (2016) · Zbl 1408.94770
[50] Zhang, H.; Yin, WT; Cheng, LZ, Necessary and sufficient conditions of solution uniqueness in \(1\)-norm minimization, J. Optim. Theory Appl., 164, 1, 109-122 (2015) · Zbl 1308.65102
[51] Zheng, ZM; Fan, YY; Lv, JC, High dimensional thresholded regression and shrinkage effect, J. R. Stat. Soc. Ser. B Stat. Methodol., 76, 3, 627-649 (2014) · Zbl 1411.62049
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.