Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling
arXiv:2002.11589
Abstract
We analyze alternating minimization for column space recovery of a partially observed, approximately low rank matrix with a growing number of columns and a fixed budget of observations per column. In this work, we prove that if the budget is greater than the rank of the matrix, column space recovery succeeds -- as the number of columns grows, the estimate from alternating minimization converges to the true column space with probability tending to one. From our proof techniques, we naturally formulate an active sampling strategy for choosing entries of a column that is theoretically and empirically (on synthetic and real data) better than the commonly studied uniformly random sampling strategy.
arXiv commentA shorter version is accepted to AISTATS
References in corpus (11)
- A Simpler Approach to Matrix Completion
- Matrix estimation by Universal Singular Value Thresholding
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
- Angles between subspaces and their tangents
- Probabilistic Matrix Factorization for Automated Machine Learning
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- On the Power of Adaptivity in Matrix Completion and Approximation
- Noise-Tolerant Life-Long Matrix Completion via Adaptive Sampling
- Matrix Completion from Samples in Linear Time
- Active Matrix Factorization for Surveys