Matrix Completion from Noisy Entries
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 by Keshavan, Montanari, and Oh (2010), 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.
Cite
Text
Keshavan et al. "Matrix Completion from Noisy Entries." Journal of Machine Learning Research, 2010.Markdown
[Keshavan et al. "Matrix Completion from Noisy Entries." Journal of Machine Learning Research, 2010.](https://mlanthology.org/jmlr/2010/keshavan2010jmlr-matrix/)BibTeX
@article{keshavan2010jmlr-matrix,
title = {{Matrix Completion from Noisy Entries}},
author = {Keshavan, Raghunandan H. and Montanari, Andrea and Oh, Sewoong},
journal = {Journal of Machine Learning Research},
year = {2010},
pages = {2057-2078},
volume = {11},
url = {https://mlanthology.org/jmlr/2010/keshavan2010jmlr-matrix/}
}