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 in [1], 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." Neural Information Processing Systems, 2009.Markdown
[Keshavan et al. "Matrix Completion from Noisy Entries." Neural Information Processing Systems, 2009.](https://mlanthology.org/neurips/2009/keshavan2009neurips-matrix/)BibTeX
@inproceedings{keshavan2009neurips-matrix,
title = {{Matrix Completion from Noisy Entries}},
author = {Keshavan, Raghunandan and Montanari, Andrea and Oh, Sewoong},
booktitle = {Neural Information Processing Systems},
year = {2009},
pages = {952-960},
url = {https://mlanthology.org/neurips/2009/keshavan2009neurips-matrix/}
}