×

Adaptive projected gradient thresholding methods for constrained \(l_0\) problems. (English) Zbl 1327.90393

Summary: In this paper, we propose and analyze adaptive projected gradient thresholding (APGT) methods for finding sparse solutions of the underdetermined linear systems with equality and box constraints. The general convergence will be demonstrated, and in addition, the bound of the number of iterations is established in some special cases. Under suitable assumptions, it is proved that any accumulation point of the sequence generated by the APGT methods is a local minimizer of the underdetermined linear system. Moreover, the APGT methods, under certain conditions, can find all \(s\)-sparse solutions for accurate measurement cases and guarantee the stability and robustness for flawed measurement cases. Numerical examples are presented to show the accordance with theoretical results in compressed sensing and verify high out-of-sample performance in index tracking.

MSC:

90C52 Methods of reduced gradient type
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beasley J E. OR-Library: Distributing test problems by electronic mail. J Oper Res Soc, 1990, 41: 1069-1072 · doi:10.1057/jors.1990.166
[2] Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J Imaging Sci, 2009, 2: 183-202 · Zbl 1175.94009 · doi:10.1137/080716542
[3] Blumensath T, Davies M E. Iterative hard thresholding for compressed sensing. Appl Comput Harmon Anal, 2009, 27: 265-274 · Zbl 1174.94008 · doi:10.1016/j.acha.2009.04.002
[4] Blumensath T, Davies M E. Normalized iterative hard thresholding: Guaranteed stability and performance. IEEE J Sel Topics Signal Process, 2010, 4: 298-309 · doi:10.1109/JSTSP.2010.2042411
[5] Candes E J, Romberg J, Tao T. Stable signal recovery from incomplete and inaccurate measurements. Comm Pure Appl Math, 2006, 59: 1207-1223 · Zbl 1098.94009 · doi:10.1002/cpa.20124
[6] Candes E J, Romberg J, Tao T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans Inform Theory, 2006, 52: 489-509 · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[7] Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit. SIAM J Sci Comput, 1998, 20: 33-61 · Zbl 0919.94002 · doi:10.1137/S1064827596304010
[8] Chen X J, Ng M K, Zhang C. Non-Lipschitz lp-regularization and box constrained model for image restoration. IEEE Trans Image Process, 2012, 21: 4709-4721 · Zbl 1373.94080 · doi:10.1109/TIP.2012.2214051
[9] Chen X J, Niu L F, Yuan Y X. Optimality conditions and a smoothing trust region Newton method for non Lipschitz optimization. SIAM J Optim, 2013, 23: 1528-1552 · Zbl 1291.90238 · doi:10.1137/120871390
[10] Chen X J, Xu F M, Ye Y Y. Lower bound theory of nonzero entries in solutions of l2-lp minimization. SIAM J Sci Comput, 2010, 32: 2832-2852 · Zbl 1242.90174 · doi:10.1137/090761471
[11] Daubechies I, Defrise M, de Mol C. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Comm Pure Appl Math, 2004, 57: 1413-1457 · Zbl 1077.65055 · doi:10.1002/cpa.20042
[12] Donoho D L. Compressed sensing. IEEE Trans Inform Theory, 2006, 52: 1289-1306 · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[13] Donoho D L, Tsaig Y, Drori I, et al. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit. IEEE Trans Inform Theory, 2012, 58: 1094-1121 · Zbl 1365.94069 · doi:10.1109/TIT.2011.2173241
[14] Efron B, Hastie T, Johnstone I, et al. Least angle regression. Ann Statist, 2004, 32: 407-499 · Zbl 1091.62054 · doi:10.1214/009053604000000067
[15] Fan J Q, Zhang J J, Yu K. Asset allocation and risk assessment with gross exposure constraints for vast portfolios. ArXiv:0812.2604, 2008 · Zbl 1077.65055
[16] Fastrich B, Paterlini S, Winker P. Cardinality versus q-norm constraints for index tracking. Quant Finance, 2014, 14: 2019-2032 · Zbl 1402.91689 · doi:10.1080/14697688.2012.691986
[17] Foucart S. Hard thresholding pursuit: An algorithm for compressive sensing. SIAM J Numer Anal, 2011, 49: 2543-2563 · Zbl 1242.65060 · doi:10.1137/100806278
[18] Friedman J, Hastie T, Hofling H, et al. Pathwise coordinate optimization. Ann Appl Stat, 2007, 1: 302-332 · Zbl 1378.90064 · doi:10.1214/07-AOAS131
[19] Kim S, Koh K, Lustig M, et al. An interior-point method for large-scale l1-regularized least squares. IEEE J Sel Topics Signal Process, 2007, 1: 606-617 · doi:10.1109/JSTSP.2007.910971
[20] Kyrillidis A, Becker S, Cevher V, et al. Sparse projections onto the simplex. ArXiv:1206.1529, 2013
[21] Lu Z S, Zhang Y. Sparse approximation via penalty decomposition methods. SIAM J Optim, 2013, 23: 2448-2478 · Zbl 1295.90056 · doi:10.1137/100808071
[22] Needell D, Tropp J. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Appl Comput Harmon Anal, 2009, 26: 301-321 · Zbl 1163.94003 · doi:10.1016/j.acha.2008.07.002
[23] Ruiz-Torrubiano R, Suarez A. A hybrid optimization approach to index tracking. Ann Oper Res, 2009, 166: 57-71 · Zbl 1163.91421 · doi:10.1007/s10479-008-0404-4
[24] Tibshirani R. Regression shrinkage and selection via the Lasso. J Roy Statist Soc Ser B, 1996, 58: 267-288 · Zbl 0850.62538
[25] Tropp J A, Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans Inform Theory, 2007, 53: 4655-4666 · Zbl 1288.94022 · doi:10.1109/TIT.2007.909108
[26] Wen Z W, Yin W T, Goldfarb D, et al. A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation. SIAM J Sci Comput, 2010, 32: 1832-1857 · Zbl 1215.49039 · doi:10.1137/090747695
[27] Wen Z W, Yin W T, Zhang H C, et al. On the convergence of an active-set method for l1 minimization. Optim Methods Softw, 2012, 27: 1127-1146 · Zbl 1244.49055 · doi:10.1080/10556788.2011.591398
[28] Xu F M, Lu Z S, Xu Z B. An efficient optimization approach for a cardinality-constrained index tracking problem. ArXiv: 1506.05866, 2015 · Zbl 1382.90117
[29] Xu F M, Xu Z B, Xue H G. Sparse index tracking based on L1/2 model and algorithm. ArXiv: 1506.05867, 2015
[30] Xu Z B, Chang X Y, Xu F M, et al. L1/2 regularization: A thresholding representation theory and a fast solver. IEEE Trans Neural Netw Learn Syst, 2012, 23: 1013-1027 · doi:10.1109/TNNLS.2012.2197412
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.