×

\(\ell _p\) regularized low-rank approximation via iterative reweighted singular value minimization. (English) Zbl 1388.90096

Summary: In this paper we study the \(\ell _p\) (or Schatten-\(p\) quasi-norm) regularized low-rank approximation problems. In particular, we introduce a class of first-order stationary points for them and show that any local minimizer of these problems must be a first-order stationary point. In addition, we derive lower bounds for the nonzero singular values of the first-order stationary points and hence also of the local minimizers of these problems. The iterative reweighted singular value minimization (IRSVM) methods are then proposed to solve these problems, whose subproblems are shown to have a closed-form solution. Compared to the analogous methods for the \(\ell _p\) regularized vector minimization problems, the convergence analysis of these methods is significantly more challenging. We develop a novel approach to establishing the convergence of the IRSVM methods, which makes use of the expression of a specific solution of their subproblems and avoids the intricate issue of finding the explicit expression for the Clarke subdifferential of the objective of their subproblems. In particular, we show that any accumulation point of the sequence generated by the IRSVM methods is a first-order stationary point of the problems. Our computational results demonstrate that the IRSVM methods generally outperform the recently developed iterative reweighted least squares methods in terms of solution quality and/or speed.

MSC:

90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
15A18 Eigenvalues, singular values, and eigenvectors
15A83 Matrix completion problems
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Barzilai, J., Borwein, J.M.: Two point step size gradient methods. IMA J. Numer. Anal. 8, 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[2] Bertalmío, M., Sapiro, G., Caselles, V., Ballester C.: Image inpainting. In: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH) (2000)
[3] Bian, W., Chen, X.: Worst-case complexity of smoothing quadratic regularization methods for non-Lipschitzian optimization, SIAM J. Optim. 23, 1718-1741 (2013) · Zbl 1282.90175
[4] Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 4, 1196-1211 (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[5] Cai, J.-F., Candés, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 1956-1982 (2010) · Zbl 1201.90155 · doi:10.1137/080738970
[6] Candés, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9, 717-772 (2009) · Zbl 1219.90124
[7] Candés, E.J., Wakin, M.B., Boyd, S.P.: Enhancing sparsity by reweighted \[\ell_1\] ℓ1 minimization. J. Fourier Anal. Appl. 14(5-6), 877-905 (2008) · Zbl 1176.94014 · doi:10.1007/s00041-008-9045-x
[8] Chartrand, R.: Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Process. Lett. 14, 707-710 (2007) · doi:10.1109/LSP.2007.898300
[9] Chartrand, R., Staneva, V.: Restricted isometry properties and nonconvex compressive sensing. Inverse Probl. 24, 1-14 (2008) · Zbl 1143.94004 · doi:10.1088/0266-5611/24/3/035020
[10] Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: 33rd International Conference on Acoustics, Speech, and Signal Processing (ICASSP) (2008)
[11] Chen, X., Ge, D., Wang, Z., Ye, Y.: Complexity of unconstrained \[L_2\] L \[2-L_p\] Lp minimization. Math. Program. 143(1), 371-383 (2014) · Zbl 1285.90039 · doi:10.1007/s10107-012-0613-0
[12] Chen, X., Niu, L., Yuan, Y.: Optimality conditions and a smoothing trust region Newton method for non-Lipschitz optimization. SIAM J. Optim. 23(3), 1528-1552 (2013) · Zbl 1291.90238 · doi:10.1137/120871390
[13] Chen, X., Xu, F., Ye, Y.: Lower bound theory of nonzero entries in solutions of \[l_2\] l \[2-l_p\] lp minimization. SIAM J. Sci. Comput. 32, 2832-2852 (2010) · Zbl 1242.90174 · doi:10.1137/090761471
[14] Chen, X., Zhou, W.: Convergence of reweighted \[l_1\] l1 minimization algorithm for \[l_2\] l \[2-l_p\] lp minimization. Comput. Optim. Appl. 59, 47-61 (2014) · Zbl 1326.90062 · doi:10.1007/s10589-013-9553-8
[15] Daubechies, I., DeVore, R., Fornasier, M., Gunturk, C.S.: Iteratively reweighted least squares minimization for sparse recovery. Commun. Pure. Appl. Math. 63, 1-38 (2010) · Zbl 1202.65046 · doi:10.1002/cpa.20303
[16] Fazel, M., Hindi, H., Boyd, S.P.: A rank minimization heuristic with application to minimum order system approximation. P. Am. Contr. Conf. 6, 4734-4739 (2001) · doi:10.1109/ACC.2001.945730
[17] Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348-1360 (2001) · Zbl 1073.62547 · doi:10.1198/016214501753382273
[18] Foucart, S., Lai, M.: Sparsest solutions of underdetermined linear systems via \[l_q\] lq-minimization for \[0 < q \le 10\]<q≤1. Appl. Comput. Harmon. Anal. 26, 395-407 (2009) · Zbl 1171.90014 · doi:10.1016/j.acha.2008.09.001
[19] Fornasier, M., Rauhut, H., Ward, R.: Low-rank matrix recovery via iteratively reweighted least squares minimization. SIAM J. Optim. 21, 1614-1640 (2011) · Zbl 1236.65044 · doi:10.1137/100811404
[20] Ge, D., Jiang, X., Ye, Y.: A note on the complexity of \[L_p\] Lp minimization. Math. Program. 21, 1721-1739 (2011)
[21] Gong, P., Zhang, C., Lu, Z., Huang, J., Ye, J.: A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems. In: The 30th International Conference on Machine Learning (ICML) (2013)
[22] Ji, S., Sze, K.-F., Zhou, Z., So, A., Ye, Y.: Beyond convex relaxation: a polynomialtime nonconvex optimization approach to network localization. In: INFOCOM (2013)
[23] Kong, L., Xiu, N.: Exact low-rank matrix recovery via nonconvex Schatten \[p\] p-minimization. Asia Pac. J. Oper. Res. 30(3), 1340010 (2013) · Zbl 1273.90257 · doi:10.1142/S0217595913400101
[24] Lai, M., Li, S., Liu, L.Y., Wang, H.: Two results on the schatten \[p\] p-quasi-norm minimization for low-rank matrix recovery. Preprint (2012)
[25] Lai, M., Wang, J.: An unconstrained \[l_q\] lq minimization with \[0 < q \le 10\]<q≤1 for sparse solution of underdetermined linear systems. SIAM J. Optim. 21, 82-101 (2010) · Zbl 1220.65051 · doi:10.1137/090775397
[26] Lai, M., Xu, Y., Yin, W.: Improved iteratively reweighted least squares for unconstrained smoothed \[l_q\] lq minimization. SIAM J. Numer. Anal. 5(2), 927-957 (2013) · Zbl 1268.49038 · doi:10.1137/110840364
[27] Lewis, A.S., Sendov, H.S.: Nonsmooth analysis of singular values. Part I: theory. Set Valued Anal. 13, 213-241 (2005) · Zbl 1129.49025 · doi:10.1007/s11228-004-7197-7
[28] Lewis, A.S., Sendov, H.S.: Nonsmooth analysis of singular values. Part II: applications. Set Valued Anal. 13, 243-264 (2005) · Zbl 1129.49026 · doi:10.1007/s11228-004-7198-6
[29] Lu, Z.: Iterative reweighted minimization methods for \[l_p\] lp regularized unconstrained nonlinear programming. Math. Program. 147(1-2), 277-307 (2014) · Zbl 1308.90170 · doi:10.1007/s10107-013-0722-4
[30] Lu, Z., Zhang, Y., Li, X.: Penalty decomposition methods for rank minimization. Optim. Method Softw. 30(3), 531-558 (2015) · Zbl 1323.65070 · doi:10.1080/10556788.2014.936438
[31] Ma, S., Goldfarb, D., Chen, L.: Fixed point and Bregman iterative methods for matrix rank minimization. Math. Program. 128(1), 321-353 (2011) · Zbl 1221.65146 · doi:10.1007/s10107-009-0306-5
[32] Malek-Mohammadi, M., Babaie-Zadeh, M., Skoglund, M.: Performance guarantees for Schatten-\[p\] p quasi-norm minimization in recovery of low-rank matrices. Sig. Process. 114, 225-230 (2015) · doi:10.1016/j.sigpro.2015.02.025
[33] Mohan, K., Fazel, M.: Iterative reweighted least squares for matrix rank minimization. In: 48th Annual Allerton Conference on Communication, Control, and Computing, pp. 653-661 (2010)
[34] Mrita, T., Kanade, T.: A sequential factorization method for recovering shape and motion from image streams. IEEE T. Pattern Anal. 19, 858-867 (1997) · doi:10.1109/34.608289
[35] Mourad, N., Reilly, J.P.: Minimizing nonconvex functions for sparse vector reconstruction. IEEE Trans. Signal Process. 58, 3485-3496 (2010) · Zbl 1391.90492 · doi:10.1109/TSP.2010.2046900
[36] Rao, B.D., Kreutz-Delgado, K.: An affine scaling methodology for best basis selection. IEEE Trans. Signal Process. 47, 187-200 (1999) · Zbl 0984.94010 · doi:10.1109/78.738251
[37] Recht, B., Fazel, M., Parrilo, P.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471-501 (2010) · Zbl 1198.90321 · doi:10.1137/070697835
[38] Sun, Q.: Recovery of sparsest signals via \[l_q\] lq minimization. Appl. Comput. Harmon. Anal. 32, 329-341 (2012) · Zbl 1266.94017 · doi:10.1016/j.acha.2011.07.001
[39] Toh, K., Yun, S.: An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pac. J. Optim. 6, 615-640 (2010) · Zbl 1205.90218
[40] Tpmasi, C., Kanade, T.: Shape and motion from image streams under orthography: a factorization method. Int. J. Comput. Vis. 9, 137-154 (1992) · doi:10.1007/BF00129684
[41] Wang, Z., Lai, M.-J., Lu, Z., Fan, W., Davulcu, H., Ye, J.: Orthogonal rank-one matrix pursuit for low rank matrix completion. SIAM J. Sci. Comput. 37, A488-A514 (2015) · Zbl 1315.65044 · doi:10.1137/130934271
[42] Wen, Z., Yin, W., Zhang, Y.: Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Prog. Comput. 4, 333-361 (2012) · Zbl 1271.65083 · doi:10.1007/s12532-012-0044-1
[43] Wright, S.J., Nowak, R., Figueiredo, M.: Sparse reconstruction by separable approximation. IEEE T. Image Process. 57, 2479-2493 (2009) · Zbl 1391.94442 · doi:10.1109/TSP.2009.2016892
[44] Xu, Z., Zhang, H., Wang, Y., Chang, X.: \[L_{1/2}\] L1/2 regularizer. Sci. China 52, 1-9 (2009)
[45] Yue, M., So, A.M.: A perturbation inequality for the schatten-\[p\] p quasi-norm and its applications to low-rank matrix recovery. Appl. Comput. Harmon. Anal. 40, 396-416 (2016) · Zbl 1335.15031
[46] Zhang, C.H.: Nearly unbiased variable selection under minimax concave penalty. Ann. Stat. 38(2), 894-942 (2010) · Zbl 1183.62120 · doi:10.1214/09-AOS729
[47] Zhang, T.: Analysis of multi-stage convex relaxation for sparse regularization. J. Mach. Learn. Res. 11, 1081-1107 (2010) · Zbl 1242.68262
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.