Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling
This work addresses efficient recommendation or matrix completion under budget constraints, offering a novel active sampling approach with theoretical guarantees, though it is incremental in improving sampling methods for low-rank recovery.
The paper tackles the problem of recovering the column space of a partially observed, approximately low-rank matrix with a fixed observation budget per column, proving that alternating minimization succeeds with high probability if the budget exceeds the rank. It also introduces an active sampling strategy that outperforms random sampling in theory and experiments on synthetic and real data.
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.