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.
Original language | English (US) |
---|---|
Pages (from-to) | 2057-2078 |
Number of pages | 22 |
Journal | Journal of Machine Learning Research |
Volume | 11 |
State | Published - Jul 2010 |
Externally published | Yes |
Keywords
- Low-rank matrices
- Manifold optimization
- Matrix completion
- Spectral methods
ASJC Scopus subject areas
- Software
- Artificial Intelligence
- Control and Systems Engineering
- Statistics and Probability