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. 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.
