Carolyn Kim

Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling

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. We prove that if the budget is greater than the rank of the matrix, column space recovery succeeds – as…