A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
作者： Quanquan Gu , Lingxiao Wang , Xiao Zhang
DOI:
关键词:
摘要: We propose a unified framework for estimating low-rank matrices through nonconvex optimization based on gradient descent algorithm. Our framework is quite general and can be applied to both noisy and noiseless observations. In the general case with noisy observations, we show that our algorithm is guaranteed to linearly converge to the unknown low-rank matrix up to a minimax optimal statistical error, provided an appropriate initial estimator. While in the generic noiseless setting, our algorithm converges to the unknown …
arxiv.org参考文章(33)
Inderjit S. Dhillon, Prateek Jain, Raghu Meka, Guaranteed Rank Minimization via Singular Value Projection neural information processing systems. ,vol. 23, pp. 937- 945 ,(2010)
Srinadh Bhojanapalli, Sujay Sanghavi, Rachel Ward, Yudong Chen, Completing Any Low-rank Matrix, Provably arXiv: Machine Learning. ,(2013)
Martin J Wainwright, Alekh Agarwal, Sahand Negahban, Fast global convergence rates of gradient methods for high-dimensional statistical recovery neural information processing systems. ,vol. 23, pp. 37- 45 ,(2010)
Ross Boczar, Mahdi Soltanolkotabi, Benjamin Recht, Max Simchowitz, Stephen Tu, Low-rank Solutions of Linear Matrix Equations via Procrustes Flow arXiv: Optimization and Control. ,(2015)
Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi, Low-rank matrix completion using alternating minimization Proceedings of the 45th annual ACM symposium on Symposium on theory of computing - STOC '13. pp. 665- 674 ,(2013) , 10.1145/2488608.2488693
Martin J. Wainwright, Sahand Negahban, Restricted strong convexity and weighted matrix completion: optimal bounds with noise Journal of Machine Learning Research. ,vol. 13, pp. 1665- 1697 ,(2012)
Suriya Gunasekar, Joydeep Ghosh, Pradeep Ravikumar, Exponential Family Matrix Completion under Structural Constraints international conference on machine learning. pp. 1917- 1925 ,(2014)
Martin J. Wainwright, Yudong Chen, Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees arXiv: Statistics Theory. ,(2015)
Benjamin Recht, Maryam Fazel, Pablo A. Parrilo, Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization Siam Review. ,vol. 52, pp. 471- 501 ,(2010) , 10.1137/070697835
Benjamin Recht, A Simpler Approach to Matrix Completion Journal of Machine Learning Research. ,vol. 12, pp. 3413- 3430 ,(2011)