Matrix completion : fundamental limits and efficient algorithms
Abstract/Contents
- Abstract
- Low-rank models provide low-dimensional representations capturing the important aspects of data naturally described in matrix form. Examples range from users' preferences on movies to similarities between pairs of items. Naturally, the low-rank representations serve as a tool for data compression and efficient computation. But more importantly, they are used in data analysis to learn hidden structures of the data, which is at the heart of machine learning and data mining. Applications include latent semantic analysis, factor analysis, and clustering high-dimensional data. While singular value decomposition provides an efficient way to construct a low-rank model of a fully observed data matrix, finding a low-rank model becomes challenging when we only have a partial knowledge about the matrix. When we observe a subset of the entries, we show that the singular value decomposition is sub-optimal and can be significantly improved upon. In this work, we investigate the possibility of learning a low-rank model from a partial observation of a data matrix. We develop a novel and efficient algorithm that finds a near-optimal solution. Further, we prove that the proposed algorithm achieves performance close to the fundamental limit under a number of noise scenarios. This provides a solution to many practical problems including collaborative filtering and positioning.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Copyright date | 2011 |
| Publication date | 2010, c2011; 2010 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Oh, Sewoong |
|---|---|
| Associated with | Stanford University, Department of Electrical Engineering |
| Primary advisor | Cover, T. M, 1938-2012 |
| Primary advisor | Montanari, Andrea |
| Thesis advisor | Cover, T. M, 1938-2012 |
| Thesis advisor | Montanari, Andrea |
| Thesis advisor | Prabhakar, Balaji, 1967- |
| Advisor | Prabhakar, Balaji, 1967- |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Sewoong Oh. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2011. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Sewoong Oh
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...