A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery. (English) Zbl 1452.90258

Summary: This paper concerns with a noisy structured low-rank matrix recovery problem which can be modeled as a structured rank minimization problem. We reformulate this problem as a mathematical program with a generalized complementarity constraint (MPGCC), and show that its penalty version, yielded by moving the generalized complementarity constraint to the objective, has the same global optimal solution set as the MPGCC does whenever the penalty parameter is over a certain threshold. Then, by solving the exact penalty problem in an alternating way, we obtain a multi-stage convex relaxation approach. We provide theoretical guarantees for our approach under a mild restricted eigenvalue condition, by quantifying the reduction of the error and approximate rank bounds of the first stage convex relaxation in the subsequent stages and establishing the geometric convergence of the error sequence in a statistical sense. Numerical experiments are conducted for some structured low-rank matrix recovery examples to confirm our theoretical findings. Our code can be achieved from https://doi.org/10.5281/zenodo.3600639.


90C27 Combinatorial optimization
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49M20 Numerical methods of relaxation type


Full Text: DOI arXiv


[1] Bai, MR; Zhang, XJ; Ni, GY; Cui, CF, An adaptive correction approach for tensor completion, SIAM J. Imaging Sci., 9, 3, 1298-1323 (2016) · Zbl 1456.90104
[2] Bi, SJ; Liu, XL; Pan, SH, Exact penalty decomposition method for zero-norm minimization based on MPEC formulation, SIAM J. Sci. Comput., 36, 4, A1451-A1477 (2014) · Zbl 1306.65211
[3] Bi, SJ; Pan, SH, Error bounds for rank constrained optimization problems and applications, Oper. Res. Lett., 44, 3, 336-341 (2016) · Zbl 1408.90279
[4] Candès, EJ; Plain, Y., Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements, IEEE Trans. Inf. Theory, 57, 4, 2342-2359 (2011) · Zbl 1366.90160
[5] Candès, EJ; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 6, 717-772 (2009) · Zbl 1219.90124
[6] Chandrasekaran, V.; Parrilo, PA; Willsky, AS, Latent variable graphical model selection via convex optimization, Ann. Stat., 40, 4, 1935-1967 (2012) · Zbl 1257.62061
[7] Chen, YX; Chi, YJ, Robust spectral compressed sensing via structured matrix completion, IEEE Trans. Inf. Theory, 60, 10, 6576-6601 (2014) · Zbl 1360.94064
[8] Ding, C.; Qi, HD, Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction, Math. Progr., 164, 341-381 (2017) · Zbl 1391.90472
[9] Ding, C.; Sun, DF; Ye, JJ, First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints, Math. Progr., 147, 1-2, 539-579 (2014) · Zbl 1301.49036
[10] Dvijotham, K., Fazel, M.: A nullspace analysis of the nuclear norm heuristic for rank minimization. In: 2010 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), pp. 3586-3589 (2010)
[11] Fazel, M.: Matrix rank minimization with applications. Ph.D. thesis, Stanford University (2002)
[12] Fazel, M., Hindi, H., Boyd, S.: Log-det heuirstic for matrix rank minimization with applications to Hankel and Euclidean distance matrices. In: Proceedings of the 2003 American Control Conference, vol. 3, pp. 2156-2162 (2003)
[13] Fazel, M.; Pong, TK; Sun, DF; Tseng, P., Hankel matrix rank minimization with applications to system identification and realization, SIAM J. Matrix Anal. A., 34, 3, 946-977 (2013) · Zbl 1302.90127
[14] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2, 1, 17-40 (1976) · Zbl 0352.65034
[15] Gao, Y.; Sun, DF, Calibrating least squares semidefinite programming with equality and inequality constraints, SIAM J. Matrix Anal. Appl., 31, 3, 1432-1457 (2010) · Zbl 1201.49031
[16] Gross, D., Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inf. Theory, 57, 3, 1548-1566 (2011) · Zbl 1366.94103
[17] Haeffele, B.D., Yang, E., Vidal, R.: Structured low-rank matrix factorization: optimality, algorithm and applications to image processing. In: Proceedings of the 31st International Conference on Machine Learning (ICML), pp. 2007-2015(2014)
[18] Horn, RA; Johnson, CR, Topics in Matrix Analysis (1991), Cambridge: Cambridge University Presss, Cambridge
[19] Jain, P., Netrapalli, P., Sanghavi, S.: Low-rank matrix completion using alternating minimization. In: Proceedings of the 45th annual ACM Symposium on Theory of Computing (STOC), pp. 665-674 (2013) · Zbl 1293.65073
[20] Keshavan, RH; Montanari, A.; Oh, S., Matrix completion from a few entries, IEEE Trans. Inf. Theory, 56, 2980-2998 (2010) · Zbl 1366.62111
[21] Koltchinskii, V.; Lounici, K.; Tsybakov, AB, Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion, Ann. Stat., 39, 5, 2302-2329 (2011) · Zbl 1231.62097
[22] Lai, MJ; Xu, YY; Yin, WT, Improved iteratively reweighted least squares for unconstrained smoothed \(\ell_q\) minimization, SIAM J. Numer. Anal., 51, 2, 927-957 (2013) · Zbl 1268.49038
[23] Li, XD; Sun, DF; Toh, KC, A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Math. Progr., 155, 333-373 (2016) · Zbl 1342.90134
[24] Miao, WM; Pan, SH; Sun, DF, A rank-corrected procedure for matrix completion with fixed basis coefficients, Math. Progr., 159, 1-2, 289-338 (2016) · Zbl 1356.90178
[25] Mohan, K., Fazel, M.: New restricted isometry results for noisy low-rank recovery. In: IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 1573-1577 (2010)
[26] Mohan, K.; Fazel, M., Iterative reweighted algorithm for matrix rank minimization, J. Mach. Learn. Res., 13, 1, 3441-3473 (2012) · Zbl 1436.65055
[27] Natsoulis, G.; Pearson, CI; Gollub, J.; Eynon, BP; Ferng, J.; Nair, R.; Idury, R.; Lee, MD; Fielden, MR; Brennan, RJ; Roter, AH; Jarnagin, K., The liver pharmacological and xenobiotic gene response repertoire, Mol. Syst. Biol., 4, 175 (2008)
[28] Negahban, S.; Wainwright, MJ, Estimation of (near) low-rank matrices with noise and high-dimensional scaling, Ann. Stat., 39, 2, 1069-1097 (2011) · Zbl 1216.62090
[29] Negahban, S.; Wainwright, MJ, Restricted strong convexity and weighted matrix completion: optimal bounds with noise, J. Mach. Learn. Res., 13, 1, 1665-1697 (2012) · Zbl 1436.62204
[30] Pietersz, R.; Groenen, PJF, Rank reduction of correlation matrices by majorization, Quant. Finance, 4, 6, 649-662 (2004) · Zbl 1405.91647
[31] Qi, HD; Yuan, XM, Computing the nearest Euclidean distance matrix with low embedding dimensions, Math. Progr., 147, 351-389 (2014) · Zbl 1304.49051
[32] Raskutti, G.; Wainwright, MJ; Yu, B., Minimax rates of estimation for high-dimensional linear regression over \(l_q\)-balls, IEEE Trans. Inf. Theory, 57, 6976-6994 (2011) · Zbl 1365.62276
[33] Recht, B.; Fazel, M.; Parrilo, PA, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[34] Recht, B.; Xu, W.; Hassibi, B., Null space conditions and thresholds for rank minimization, Math. Progr., 127, 175-202 (2011) · Zbl 1211.90172
[35] Rennie, J., Srebro, N.: Fast maximum margin matrix factorization for collaborative prediction. In: Proceedings of the 22nd International Conference on Machine Learning (ICML), pp. 713-719 (2005)
[36] Richard, E., Savalle, P., Vayatis, N.: Estimation simultaneously sparse and low rank matrices. In: Proceedings of the 29th International Conference on Machine Learning (ICML), pp 1351-1358 (2012)
[37] Rockafellar, RT, Convex Analysis (1970), Princeton: Princeton University Press, Princeton
[38] Toh, KC; Yun, SW, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pac. J. Optim., 6, 3, 615-640 (2010) · Zbl 1205.90218
[39] Vershynin, R.; Eldar, YC; Kutyniok, G., Introduction to the non-asymptotic analysis of random matrices, Compressed Sensing: Theory and Applications (2012), Cambridge: Cambridge University Press, Cambridge
[40] Watson, GA, Characterization of the subdifferential of some matrix norms, Linear Algebra Appl., 170, 33-45 (1992) · Zbl 0751.15011
[41] Wu, J.; Zhang, LW; Zhang, Y., Mathematical programs with semidefinite cone complementarity constraints: constraint qualifications and optimality conditions, Set-Valued and Var. Anal., 22, 1, 155-187 (2014) · Zbl 1296.90118
[42] Zhang, T., Some sharp performance bounds for least squares regression with \(L_1\) regularization, Ann. Stat., 37, 5, 2109-2144 (2009) · Zbl 1173.62029
[43] 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. 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.