Fetching the paper…

Reading the bibliography…

2009

Matrix Completion from Noisy Entries

Keshavan, Raghunandan H., Montanari, Andrea, Oh, Sewoong

Original
PDF
Post on X

Understand

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 by Keshavan et al.(2009), based on a combination of spectral techniques and manifold optimization, that we call here OptSpace.
We prove performance guarantees that are order-optimal in a number of circumstances.

Matrix Completion from Noisy Entries · Around

Built on

A new look at independence
M. Talagrand · 1996
Earlier work this paper cites.
The geometry of algorithms with orthogonality constraints
A. Edelman, T. A. Arias, and S. T. Smith · 1999
Earlier work this paper cites.
The expected norm of random matrices
Y. Seginer · 2000
Earlier work this paper cites.
Matrix Rank Minimization with Applications
M. Fazel · 2002
Earlier work this paper cites.
Weighted low-rank approximations
N. Srebro and T. S. Jaakkola · 2003
Earlier work this paper cites.
Fast monte-carlo algorithms for finding low-rank approximations
A. Frieze, R. Kannan, and S. Vempala · 2004
Earlier work this paper cites.
Maximum-margin matrix factorization
N. Srebro, J. D. M. Rennie, and T. S. Jaakola · 2005
Earlier work this paper cites.
Fast computation of low-rank matrix approximations
D. Achlioptas and F. McSherry · 2007
Earlier work this paper cites.

Similar

Guaranteed minimum rank solutions of matrix equations via nuclear norm minimization
Original
B. Recht, M. Fazel, and P. Parrilo · 2007
Cited alongside, same era.
Restricted Boltzmann machines for collaborative filtering
R. Salakhutdinov, A. Mnih, and G. Hinton · 2007
Cited alongside, same era.
Optimization Algorithms on Matrix Manifolds
P.-A. Absil, R. Mahony, and R. Sepulchrer · 2008
Cited alongside, same era.
A singular value thresholding algorithm for matrix completion
Original
J-F Cai, E. J. Candès, and Z. Shen · 2008
Cited alongside, same era.
Exact matrix completion via convex optimization
Original
E. J. Candès and B. Recht · 2008
Cited alongside, same era.

Then

The power of convex relaxation: Near-optimal matrix completion
Original
E. J. Candès and T. Tao · 2009
Closest in time.
Optspace: A gradient descent algorithm on the grassman manifold for matrix completion
Original
R. H. Keshavan and S. Oh · 2009
Closest in time.
Admira: Atomic decomposition for minimum rank approximation
Original
K. Lee and Y. Bresler · 2009
Closest in time.
Fixed point and Bregman iterative methods for matrix rank minimization
Original
S. Ma, D. Goldfarb, and L. Chen · 2009
Closest in time.
An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems
Original

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Probabilistic matrix factorization

R. Salakhutdinov and A. Mnih · 2008

Cited alongside, same era.

Matrix completion with noise

E. J. Candès and Y. Plan · 2009

Cited alongside, same era.

K. Toh and S. Yun · 2009

Closest in time.

Matrix completion from a few entries

R. H. Keshavan, A. Montanari, and S. Oh · 2010

Closest in time.

Collaborative filtering in a non-uniform world: Learning with the weighted trace norm

R. Salakhutdinov and N. Srebro · 2010

Closest in time.