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

Carolyn Kim, Mohsen Bayati
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:445-455, 2020.

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

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-kim20a, title = {Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling}, author = {Kim, Carolyn and Bayati, Mohsen}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {445--455}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/kim20a/kim20a.pdf}, url = {https://proceedings.mlr.press/v108/kim20a.html}, 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. 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.} }
Endnote
%0 Conference Paper %T Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling %A Carolyn Kim %A Mohsen Bayati %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-kim20a %I PMLR %P 445--455 %U https://proceedings.mlr.press/v108/kim20a.html %V 108 %X 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 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.
APA
Kim, C. & Bayati, M.. (2020). Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:445-455 Available from https://proceedings.mlr.press/v108/kim20a.html.

Related Material