Guarantees of Riemannian optimization for low rank matrix completion. (English) Zbl 1439.65059

Summary: We establish the exact recovery guarantees for a class of Riemannian optimization methods based on the embedded manifold of low rank matrices for matrix completion. Assume \( m\) entries of an \( n\times n\) rank \( r\) matrix are sampled independently and uniformly with replacement. We first show that with high probability the Riemannian gradient descent and conjugate gradient descent algorithms initialized by one step hard thresholding are guaranteed to converge linearly to the measured matrix provided \[m\geq C_\kappa n^{1.5}r\log^{1.5}(n),\] where \( C_\kappa\) is a numerical constant depending on the condition number of the measured matrix. Then the sampling complexity is further improved to \[m\geq C_\kappa nr^2\log^2(n)\] via the resampled Riemannian gradient descent initialization. The analysis of the new initialization procedure relies on an asymmetric restricted isometry property of the sampling operator and the curvature of the low rank matrix manifold. Numerical simulation shows that the algorithms are able to recover a low rank matrix from nearly the minimum number of measurements.


65F55 Numerical methods for low-rank matrix approximation; matrix compression
15A83 Matrix completion problems
65K10 Numerical optimization and variational techniques
Full Text: DOI arXiv


[1] Y. Amit, M. Fink, N. Srebro and S. Ullman, Uncovering shared structures in multiclass classification, in: Proceedings of the 24th International Conference on Machine Learning, 2007, 17-24.
[2] A. Argyriou, T. Evgeniou and M. Pontil, Multi-task feature learning, Advances in Neural Information Processing Systems, 2007. · Zbl 1470.68073
[3] A. Ahmed; B. Recht; J. Romberg, Blind deconvolution using convex programming, IEEE Transactions on Information Theory, 60, 1711-1732 (2014) · Zbl 1360.94057
[4] A. Ahmed; B. Recht; J. Romberg, Blind deconvolution using convex programming, IEEE Transactions on Information Theory, 60, 1711-1732 (2014) · Zbl 1071.94530
[5] R. Ahlswede; A. Winter, Strong converse for identification via quantum channels, IEEE Transactions on Information Theory, 48, 569-579 (2002)
[6] S. Bhojanapalli; A. Kyrillidis; S. Sanghavi, Dropping convexity for faster semi-definite optimization, JMLR: Workshop and Conference Proceedings, 49, 1-53 (2016) · Zbl 1380.94045
[7] J. Blanchard; J. Tanner; K. Wei, CGIHT: Conjugate gradient iterative hard thresholding for compressed sensing and matrix completion, Information and Inference, 4, 289-327 (2015)
[8] N. Boumal and P.-A. Absil, RTRMC: A Riemannian trust-region method for low-rank matrix completion, in: Advances in Neural Information Processing Systems, 2011. · Zbl 1219.90124
[9] E. J. Candès; B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9, 717-772 (2009) · Zbl 1366.90160
[10] E. J. Candès; Y. Plan, Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements, IEEE Transactions on Information Theory, 57, 2342-2359 (2011)
[11] Y. Chen and M. J. Wainwright, Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees, arXiv: 1509.03025, 2015. · Zbl 1366.15021
[12] E. J. Candès; T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Transactions on Information Theory, 56, 2053-2080 (2009) · Zbl 1359.15022
[13] Y. Chen, Incoherence-optimal matrix completion, IEEE Transactions on Information Theory, 61, 2909-2923 (2015) · Zbl 1201.90155
[14] J.-F. Cai; E. J. Candès; Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20, 1956-1982 (2010) · Zbl 1280.49052
[15] E. J. Candès; Y. Eldar; T. Strohmer; V. Voroninski, Phase retrieval via matrix completion, SIAM J. on Imaging Sciences, 6, 199-225 (2013) · Zbl 1359.94069
[16] E. J. Candès; X. Li; M. Soltanolkotabi, Phase retrieval via Wirtinger flow: Theory and algorithms, IEEE Transactions on Information Theory, 61, 1985-2007 (2015) · Zbl 1379.90024
[17] Y. Chen; E. Candès, Solving random quadratic systems of equations is nearly as easy as solving linear systems, Communications on Pure and Applied Mathematics, 70, 822-883 (2017) · Zbl 1120.68092
[18] L. Eldén, Matrix Methods in Data Mining and Pattern Recogonization, SIAM, 2007.
[19] M. Fazel, Matrix rank minimization with applications, ph. D. dissertation, Stanford University, 2002. · Zbl 1366.94103
[20] D. Gross, Recovering low-rank matrices from few coefficients in any basis, IEEE Transactions on Information Theory, 57, 1548-1566 (2011) · Zbl 1219.90195
[21] D. Goldfarb; S. Ma, Convergence of fixed-point continuation algorithms for matrix rank minimization, Foundations of Computational Mathematics, 11, 183-210 (2011)
[22] R. W. Gerchberg; W. O. Saxton, A practical algorithm for the determination of the phase from image and diffraction plane pictures, Optik, 35, 237-246 (1972) · Zbl 1192.68322
[23] N. J. A. Harvey, D. R. Karger and S. Yekhanin, The complexity of matrix completion, in: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, 1103-1111.
[24] J. P. Haldar; D. Hernando, Rank-constrained solutions to linear matrix equations using PowerFactorization, IEEE Signal Processing Letters, 16, 584-587 (2009)
[25] P. Jain, R. Meka and I. Dhillon, Guaranteed rank minimization via singular value projection, in: NIPS, 2010. · Zbl 1293.65073
[26] P. Jain, P. Netrapalli and S. Sanghavi, Low-rank matrix completion using alternating minimization, in: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 2013,665-674.
[27] P. Jain; P. Netrapalli, Fast exact matrix completion with finite samples, JMLR: Workshop and Conference Proceedings, 40, 1-28 (2015) · Zbl 1311.90141
[28] A. Kyrillidis; V. Cevher, Matrix recipes for hard thresholding methods, Journal of Mathematical Imaging and Vision, 48, 235-265 (2014)
[29] R. H. Keshavan, Efficient algorithms for collaborative filtering, ph. D. dissertation, Stanford University, 2012. · Zbl 1366.62111
[30] R. H. Keshavan; A. Montanari; S. Oh, Matrix completion from a few entries, IEEE Transactions on Information Theory, 56, 2980-2998 (2010) · Zbl 1201.90151
[31] Z. Liu; L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM Journal on Matrix Analysis and Applications, 31, 1235-1256 (2009) · Zbl 1366.94112
[32] K. Lee; Y. Bresler, ADMiRA: Atomic decomposition for minimum rank approximation, IEEE Transactions on Information Theory, 128, 4402-4416 (2010) · Zbl 1370.94583
[33] S. Ling; T. Strohmer, Blind deconvolution meets blind demixing: Algorithms and performance bounds, IEEE Transactions on Information Theory, 63, 4497-4520 (2017)
[34] B. Mishra, K. A. Apuroop and R. Sepulchre, A Riemannian geometry for low-rank matrix completion, arXiv 1306.2672, 2013. · Zbl 1306.65107
[35] B. Mishra; G. Meyer; S. Bonnabel; R. Sepulchre, Fixed-rank matrix factorizations and Riemannian low-rank optimization, Computational Statistics, 29, 591-621 (2014)
[36] T. Ngo and Y. Saad, Scaled Gradients on Grassmann Manifolds for Matrix Completion, in: Advances in Neural Information Processing Systems, 2012. · Zbl 1104.65059
[37] J. Nocedal and S. J. Wright, Numerical Optimization, Springer, 2006. · Zbl 1198.90321
[38] B. Recht; M. Fazel; P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52, 471-501 (2010) · Zbl 1280.68141
[39] B. Recht, A simpler approach to matrix completion, The Journal of Machine Learning Research, 12, 3413-3430 (2011)
[40] C. D. Sa, K. Olukotun, C. Ré, Global convergence of stochastic gradient descent for some nonconvex matrix problems, in: ICML, 2015.
[41] R. Sun and Z. Luo, Guaranteed matrix completion via non-convex factorization, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science-FOCS 2015, IEEE Computer Soc., Los Alamitos, CA, 2015,270-289. · Zbl 1401.94049
[42] J. Sun; Q. Qu; J. Wright, A geometric analysis of phase retrieval, Foundations of Computational Mathematics, 18, 1131-1198 (2018) · Zbl 1282.65043
[43] J. Tanner and K. Wei, Normalized iterative hard thresholding for matrix completion, SIAM Journal on Scientific Computing, 35 (2013), S104-S125.
[44] S. Tu, R. Boczar, M. Simchowitz, M. Soltanolkotabi and B. Recht, Low-rank solutions of linear matrix equations via Procrustes flow, in: ICML, 2016. · Zbl 1336.65047
[45] J. Tanner; K. Wei, Low rank matrix completion by alternating steepest descent methods, Applied and Computational Harmonic Analysis, 40, 417-429 (2016) · Zbl 0845.65023
[46] L. Vandenberghe; S. Boyd, Semidefinite programming, SIAM Review, 38, 49-95 (1996) · Zbl 1277.15021
[47] B. Vandereycken, Low rank matrix completion by Riemannian optimization, SIAM Journal on Optimization, 23, 1214-1236 (2013) · Zbl 1271.65083
[48] Z. Wen; W. Yin; Y. Zhang, Solving a low-rank factorization model for matrix completion by a non-linear successive over-relaxation algorithm, Mathematical Programming Computation, 4, 333-361 (2012) · Zbl 1383.65064
[49] C. D. White; S. Sanghavi; R. Ward, The local convexity of solving systems of quadratic equations, Results in Mathematics, 71, 569-608 (2017) · Zbl 1347.65109
[50] K. Wei; J.-F. Cai; T. F. Chan; S. Leung, Guarantees of Riemannian optimization for low rank matrix recovery, SIAM Journal on Matrix Analysis nad Applications, 37, 1198-1222 (2016) · Zbl 1332.65045
[51] K. Wei, Solving systems of phaseless equations via Kaczmarz methods: A proof of concept study, Inverse Problems, 31 (2015), 125008, 23pp.
[52] Q. Zheng and J. Lafferty, A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements, NIPS, 2015.
[53] T. Zhao, Z. Wang and H. Liu, Nonconvex low rank matrix factorization via inexact first order oracle, NIPS, 2015.
[54] Q. Zheng and J. Lafferty, Convergence analysis for rectangular matrix completion using Burer-Monteiro factorization and gradient descent, 2016, arXiv: 1605.0705.
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.