×

zbMATH — the first resource for mathematics

Iterative hard thresholding methods for \(l_0\) regularized convex cone programming. (English) Zbl 1308.65094
The author presents an iterative hard thresholding (IHT) method and its variant for solving a special \(l_0\) regularized box constrained convex programming. The iteration complexity of the IHT method for finding an \(\epsilon\)-local-optimal solution of the problem is obtained. Furthermore, the author develops a method for solving \(l_0\) regularized convex cone programming by applying the IHT method to its quadratic penalty relation and establishes its iteration complexity for finding an \(\epsilon\)-approximate local minimizer of the problem.

MSC:
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C25 Convex programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bahmani, S; Raj, B; Boufounos, P, Greedy sparsity-constrained optimization, J. Mach. Learn Res., 14, 807-841, (2013) · Zbl 1320.90046
[2] Barzilai, J; Borwein, JM, Two point step size gradient methods, IMA J. Numer. Anal., 8, 141-148, (1988) · Zbl 0638.65055
[3] Blumensath, T, Accelerated iterative hard thresholding, Signal Process., 92, 752-756, (2012)
[4] Blumensath, T, Compressed sensing with nonlinear observations and related nonlinear optimization problems, IEEE Trans. Inf. Theory, 59, 3466-3474, (2013) · Zbl 1364.94111
[5] Blumensath, T; Davies, ME, Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14, 629-654, (2008) · Zbl 1175.94060
[6] Blumensath, T; Davies, ME, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27, 265-274, (2009) · Zbl 1174.94008
[7] Blumensath, T; Davies, ME, Normalized iterative hard thresholding: guaranteed stability and performance, IEEE J. Sel. Top. Signal Process., 4, 298-309, (2010)
[8] Candès, E; Romberg, J; Tao, T, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 489-509, (2006) · Zbl 1231.94017
[9] Cevher, V.: On accelerated hard thresholding methods for sparse approximation. In: Proceedings of SPIE, Conference on Wavelets and Sparsity XIV. San Diego, CA (2011)
[10] Dempster, A, Covariance selection, Biometrics, 28, 157-175, (1978)
[11] Donoho, D, Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306, (2006) · Zbl 1288.94016
[12] Foucart, S, Hard thresholding pursuit: an algorithm for compressive sensing, SIAM J. Numer. Anal., 49, 2543-2563, (2011) · Zbl 1242.65060
[13] Herrity, K.K., Gilbert, A.C., Tropp, J.A.: Sparse approximation via iterative thresholding. In: IEEE International Conference on Acoustics, Speech and Signal Processing (2006) · Zbl 1288.94016
[14] Jain, P., Meka, R., Dhillon, I.: Guaranteed rank minimization via singular value projection. Neural Inf. Process. Syst., 937-945 (2010)
[15] Lan, G; Monteiro, RDC, Iteration-complexity of first-order penalty methods for convex programming, Math. Progam., 138, 115-139, (2013) · Zbl 1282.90129
[16] Lu, Z., Zhang, Y.: Sparse approximation via penalty decomposition methods. To appear in SIAM J. Optim. (2013) · Zbl 1295.90056
[17] Maleki, A.: Coherence analysis of iterative thresholding algorithms. In: Proceedings of 47th Annual Allerton Conference on Communication, Control, and Computing, pp. 236-243 (2009) · Zbl 0638.65055
[18] Mallat, S; Zhang, Z, Matching pursuits with time-frequency dictionaries, IEEE Trans. Image Process., 41, 3397-3415, (1993) · Zbl 0842.94004
[19] Nesterov, Y.: Introductory Lectures on Convex Programming: A Basic Course. Kluwer, Boston, MA (2004) · Zbl 1086.90045
[20] Ng, A.Y.: Feature selection, \(l_1\) vs. \(l_2\) regularization, and rotational invariance. In: Proceedings of the Twenty-First International Conference on Machine learning (ICML), pp. 72-85 (2004) · Zbl 1174.94008
[21] Nikolova, M.: Description of the minimizers of least squares regularized with \(l_0\) norm. Report HAL-00723812, CMLA-CNRS ENS Cachan, France (2011)
[22] Tanner, J., Wei, K.: Normalized iterative hard thresholding for matrix completion. Accepted by SIAM J. Sci. Comput. (2012) · Zbl 1282.65043
[23] Tropp, JA, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inf. Theory, 50, 2231-2242, (2004) · Zbl 1288.94019
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.