On Recovering the Best Rank-r Approximation from Few Entries
arXiv:2111.06302
Abstract
In this note, we investigate how well we can reconstruct the best rank- approximation of a large matrix from a small number of its entries. We show that even if a data matrix is of full rank and cannot be approximated well by a low-rank matrix, its best low-rank approximations may still be reliably computed or estimated from a small number of its entries. This is especially relevant from a statistical viewpoint: the best low-rank approximations to a data matrix are often of more interest than itself because they capture the more stable and oftentimes more reproducible properties of an otherwise complicated data-generating model. In particular, we investigate two agnostic approaches: the first is based on spectral truncation; and the second is a projected gradient descent based optimization procedure. We argue that, while the first approach is intuitive and reasonably effective, the latter has far superior performance in general. We show that the error depends on how close the matrix is to being of low rank. Both theoretical and numerical evidence is presented to demonstrate the effectiveness of the proposed approaches.
References in corpus (7)
- Finding community structure in very large networks
- A Simpler Approach to Matrix Completion
- An overview of low-rank matrix recovery from incomplete observations
- Guaranteed Matrix Completion via Non-convex Factorization
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- A Note on Element-wise Matrix Sparsification via a Matrix-valued Bernstein Inequality