Matrix Completion from Noisy Entries

2009/06/11 by Keshavan, Raghunandan H., Montanari, Andrea, Oh, Sewoong · 2 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.0906.2027

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 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.

Cited by

• New perturbation bounds for low rank approximation of matrices: Beyond Eckart-Young-Mirsky
• Integrated Analysis for Electronic Health Records with Structured and Sporadic Missingness

Related

• Low-rank Matrix Completion with Noisy Observations: a Quantitative Comparison
• Regularization for Matrix Completion
• Obtaining error-minimizing estimates and universal entry-wise error\n bounds for low-rank matrix completion
• Matrix Completion With Noise
• Matrix Completion with Sparse Noisy Rows