Exact minimum rank approximation via Schatten \(p\)-norm minimization. (English) Zbl 1293.65056

Summary: Minimizing the rank of a matrix with a given system of affine constraints is to recover the lowest-rank matrix with many important applications in engineering and science. A convex relaxation of the rank minimization problem by minimizing the nuclear norm instead of the rank of the matrix has recently been proposed. Recht and Fazel concluded that nuclear norm minimization subject to affine constraints is equivalent to rank minimization under a certain condition in terms of the rank-restricted isometry property. In this paper, we extend some recent results from nuclear norm minimization to Schatten \(p\)-norm minimization and present a theoretical guarantee for the Schatten \(p\)-norm minimization if a certain restricted isometry property holds for the linear affine transform. Our results improve on the previous works where recovery is used for nuclear norm minimization. An algorithm based on the Majorization Minimization algorithm has been proposed to solve Schatten \(p\)-norm minimization. By using an approximate singular value decomposition procedure, we obtain a fast and robust algorithm. The numerical results on the matrix completion problem with noisy measurements indicate that our algorithm gives a more accurate reconstruction and takes less time compared with some other existing algorithms.


65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory
15A23 Factorization of matrices
15A83 Matrix completion problems


ADMiRA; softImpute
Full Text: DOI


[1] Mesbahi, M.; Papavassilopoulos, G. P., On the rank minimization problem over a positive semidefinite linear matrix inequality, IEEE Trans. Automat. Control, 42, 2, 239-243 (1997) · Zbl 0872.93029
[2] Liu, Z.; Vandenberghe, L., Interior-point method for nuclear norm approximation with application to system identification, SIAM J. Matrix Anal. Appl., 31, 3, 1235-1256 (2009) · Zbl 1201.90151
[3] Shapiro, A., Weighted minimum trace factor analysis, Psychometrika, 47, 3, 243-264 (1982) · Zbl 0544.62058
[4] Evgeniou, A.; Pontil, M., Multi-task feature learning, (Advances in Neural Information Processing Systems: Proceedings of the 2006 Conference, Vol. 19 (2007), The MIT Press), 41
[5] Tomasi, C.; Kanade, T., Shape and motion from image streams under orthography: a factorization method, Int. J. Comput. Vis., 9, 2, 137-154 (1992)
[6] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[7] Candès, E. J.; Tao, T., The power of convex relaxation: near-optimal matrix completion, IEEE Trans. Inform. Theory, 56, 5, 2053-2080 (2010) · Zbl 1366.15021
[9] Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 6, 717-772 (2009) · Zbl 1219.90124
[11] Mazumder, R.; Hastie, T.; Tibshirani, R., Spectral regularization algorithms for learning large incomplete matrices, J. Mach. Learn. Res., 99, 2287-2322 (2010) · Zbl 1242.68237
[12] Lee, K.; Bresler, Y., Admira: atomic decomposition for minimum rank approximation, IEEE Trans. Inform. Theory, 56, 9, 4402-4416 (2010) · Zbl 1366.94112
[14] Beck, A.; Teboulle, M., A linearly convergent algorithm for solving a class of nonconvex/affine feasibility problems, (Fixed-Point Algorithms for Inverse Problems in Science and Engineering (2011), Springer), 33-48 · Zbl 1242.90225
[15] Rohde, A.; Tsybakov, A. B., Estimation of high-dimensional low-rank matrices, Ann. Statist., 39, 2, 887-930 (2011) · Zbl 1215.62056
[16] Candes, E. J.; Romberg, J. K.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59, 8, 1207-1223 (2006) · Zbl 1098.94009
[18] Ma, S.; Goldfarb, D.; Chen, L., Fixed point and bregman iterative methods for matrix rank minimization, Math. Program., 128, 1-2, 321-353 (2011) · Zbl 1221.65146
[19] Drineas, P.; Kannan, R.; Mahoney, M. W., Fast Monte Carlo algorithms for matrices II: computing a low-rank approximation to a matrix, SIAM J. Comput., 36, 1, 158-183 (2006) · Zbl 1111.68148
[20] Mohan, K.; Fazel, M., Iterative reweighted algorithms for matrix rank minimization, J. Mach. Learn. Res., 13, 3441-3473 (2012) · Zbl 1436.65055
[21] Lai, M.-J.; Xu, Y.; Yin, W., Improved iteratively reweighted least squares for unconstrained smoothed \(\ell_q\) minimization, SIAM J. Numer. Anal., 51, 2, 927-957 (2013) · Zbl 1268.49038
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.