nips nips2009 nips2009-147 nips2009-147-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Raghunandan Keshavan, Andrea Montanari, Sewoong Oh
Abstract: Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the ‘Netflix problem’) to structure-from-motion and positioning. We study a low complexity algorithm introduced in [1], based on a combination of spectral techniques and manifold optimization, that we call here O PT S PACE. We prove performance guarantees that are order-optimal in a number of circumstances. 1
[1] R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from a few entries. arXiv:0901.3150, January 2009.
[2] A. Frieze, R. Kannan, and S. Vempala. Fast monte-carlo algorithms for finding low-rank approximations. J. ACM, 51(6):1025–1041, 2004.
[3] E. J. Cand` s and B. Recht. e Exact matrix completion via convex optimization. arxiv:0805.4471, 2008.
[4] M. Fazel. Matrix Rank Minimization with Applications. PhD thesis, Stanford University, 2002.
[5] E. J. Cand` s and T. Tao. The power of convex relaxation: Near-optimal matrix completion. e arXiv:0903.1476, 2009.
[6] J-F Cai, E. J. Cand` s, and Z. Shen. A singular value thresholding algorithm for matrix come pletion. arXiv:0810.3286, 2008.
[7] S. Ma, D. Goldfarb, and L. Chen. Fixed point and Bregman iterative methods for matrix rank minimization. arXiv:0905.1643, 2009.
[8] K. Toh and S. Yun. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. http://www.math.nus.edu.sg/∼matys, 2009.
[9] J. Wright, A. Ganesh, S. Rao, and Y. Ma. Robust principal component analysis: Exact recovery of corrupted low-rank matrices. arXiv:0905.0233, 2009.
[10] K. Lee and Y. Bresler. Admira: Atomic decomposition for minimum rank approximation. arXiv:0905.0044, 2009.
[11] E. J. Cand` s and Y. Plan. Matrix completion with noise. arXiv:0903.3131, 2009. e
[12] A. Edelman, T. A. Arias, and S. T. Smith. The geometry of algorithms with orthogonality constraints. SIAM J. Matr. Anal. Appl., 20:303–353, 1999.
[13] P.-A. Absil, R. Mahony, and R. Sepulchrer. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2008.
[14] D. Achlioptas and F. McSherry. Fast computation of low-rank matrix approximations. J. ACM, 54(2):9, 2007. 9