Research ArticleOpen AccessGoogle Scholar indexed
On Accelerated Singular Value Thresholding Algorithm for Matrix Completion
School of Mathematics and Statistics, Hainan Normal University, Haikou, China
School of Mathematics and Statistics, Hainan Normal University, Haikou, China
School of Mathematics and Statistics, Hainan Normal University, Haikou, China
- 1 School of Mathematics and Statistics, Hainan Normal University, Haikou, China
- 2 School of Mathematics and Statistics, Hainan Normal University, Haikou, China
- 3 School of Mathematics and Statistics, Hainan Normal University, Haikou, China
Applied Mathematics·Volume 05 (2014)·Pages 3445–3451·Published 1 December 2014·DOI10.4236/am.2014.521322
Copy link · social · email
Abstract
An accelerated singular value thresholding (SVT) algorithm was introduced for matrix completion in a recent paper [1], which applies an adaptive line search scheme and improves the convergence rate from O (1/ N ) for SVT to O (1/ N 2 ), where N is the number of iterations. In this paper, we show that it is the same as the Nemirovski’s approach, and then modify it to obtain an accelerate Nemirovski’s technique and prove the convergence. Our preliminary computational results are very favorable.
KeywordsMatrix CompletionSingular Value ThresholdingNemirovski’s Line Search SchemeAdaptive Line Search
- Hu, Y., Zhang, D. and Liu, J. (2012) Accelerated Singular Value Thresholding for Matrix Completion. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, 12-16 August 2012, 298-306. http://dx.doi.org/10.1145/2339530.2339581
- Koren, Y. (2008) Factorization Meets the Neighborhood: A Multifaceted Collaborative Filtering Model. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, 24-27 August 2008, 426-434. http://dx.doi.org/10.1145/1401890.1401944
- Koren, Y. (2010) Collaborative Filtering with Temporal Dynamics. Communications of the ACM, 53, 89-97. http://dx.doi.org/10.1145/1721654.1721677
- Steck, H. (2010) Training and Testing of Recommender Systems on Data Missing Not at Random. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington DC, 25-28 July 2010, 713-722.
- Candès, E.J. and Recht, B. (2009) Exact Matrix Completion via Convex Optimization. Foundations of Computational Mathematics, 9, 717-772. http://dx.doi.org/10.1007/s10208-009-9045-5
- Cai, J.F., Candès, E.J. and Shen, Z. (2010) A Singular Value Thresholding Algorithm for Matrix Completion. SIAM Journal on Optimization, 20, 1956-1982. http://dx.doi.org/10.1137/080738970
- Toh, K.C. and Yun, S. (2010) An Accelerated Proximal Gradient Algorithm for Nuclear Norm Regularized Least Squares Problems. Pacific Journal of Optimization, 6, 615-640.
- Nemirovski, A. (1994) Lecture Notes on Efficient Methods in Convex Programming. http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf
- Liu, J., Chen, J. and Ye, J. (2009) Large-Scale Sparse Logistic Regression. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, 28 June-1 July 2009, 547-556. http://dx.doi.org/10.1145/1557019.1557082
- Nesterov, Y. (2003) Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Norwell.