Optspace: A Gradient Descent Algorithm on the Grassmann Manifold for Matrix Completion. We consider the problem of reconstructing a low-rank matrix from a small subset of its entries. In this paper, we describe the implementation of an efficient algorithm called OptSpace, based on singular value decomposition followed by local manifold optimization, for solving the low-rank matrix completion problem. It has been shown that if the number of revealed entries is large enough, the output of singular value decomposition gives a good estimate for the original matrix, so that local optimization reconstructs the correct matrix with high probability. We present numerical results which show that this algorithm can reconstruct the low rank matrix exactly from a very small subset of its entries. We further study the robustness of the algorithm with respect to noise, and its performance on actual collaborative filtering datasets.
Keywords for this software
References in zbMATH (referenced in 7 articles , 1 standard article )
Showing results 1 to 7 of 7.
- Wang, Zheng; Lai, Ming-Jun; Lu, Zhaosong; Fan, Wei; Davulcu, Hasan; Ye, Jieping: Orthogonal rank-one matrix pursuit for low rank matrix completion (2015)
- Lin, Junhong; Li, Song: Convergence of projected Landweber iteration for matrix rank minimization (2014)
- Liu, Yuanyuan; Jiao, L. C.; Shang, Fanhua: An efficient matrix factorization based low-rank representation for subspace clustering (2013)
- Mishra, B.; Meyer, G.; Bach, F.; Sepulchre, R.: Low-rank optimization with trace norm penalty (2013)
- Tanner, Jared; Wei, Ke: Normalized iterative hard thresholding for matrix completion (2013)
- Wen, Zaiwen; Yin, Wotao; Zhang, Yin: Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm (2012)
- Keshavan, Raghunandan H.; Montanari, Andrea; Oh, Sewoong: Matrix completion from noisy entries (2010)