Concentration-Based Guarantees for Low-Rank Matrix Reconstruction

Rina Foygel, Nathan Srebro
Proceedings of the 24th Annual Conference on Learning Theory, PMLR 19:315-340, 2011.

Abstract

We consider the problem of approximately reconstructing a partially-observed, approximately low-rank matrix. This problem has received much attention lately, mostly using the trace-norm as a surrogate to the rank. Here we study low-rank matrix reconstruction using both the trace-norm, as well as the less-studied max-norm, and present reconstruction guarantees based on existing analysis on the Rademacher complexity of the unit balls of these norms. We show how these are superior in several ways to recently published guarantees based on specialized analysis.

Cite this Paper

BibTeX
@InProceedings{pmlr-v19-foygel11a, title = {Concentration-Based Guarantees for Low-Rank Matrix Reconstruction}, author = {Foygel, Rina and Srebro, Nathan}, booktitle = {Proceedings of the 24th Annual Conference on Learning Theory}, pages = {315--340}, year = {2011}, editor = {Kakade, Sham M. and von Luxburg, Ulrike}, volume = {19}, series = {Proceedings of Machine Learning Research}, address = {Budapest, Hungary}, month = {09--11 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v19/foygel11a/foygel11a.pdf}, url = {https://proceedings.mlr.press/v19/foygel11a.html}, abstract = {We consider the problem of approximately reconstructing a partially-observed, approximately low-rank matrix. This problem has received much attention lately, mostly using the trace-norm as a surrogate to the rank. Here we study low-rank matrix reconstruction using both the trace-norm, as well as the less-studied max-norm, and present reconstruction guarantees based on existing analysis on the Rademacher complexity of the unit balls of these norms. We show how these are superior in several ways to recently published guarantees based on specialized analysis.} }
Endnote
%0 Conference Paper %T Concentration-Based Guarantees for Low-Rank Matrix Reconstruction %A Rina Foygel %A Nathan Srebro %B Proceedings of the 24th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2011 %E Sham M. Kakade %E Ulrike von Luxburg %F pmlr-v19-foygel11a %I PMLR %P 315--340 %U https://proceedings.mlr.press/v19/foygel11a.html %V 19 %X We consider the problem of approximately reconstructing a partially-observed, approximately low-rank matrix. This problem has received much attention lately, mostly using the trace-norm as a surrogate to the rank. Here we study low-rank matrix reconstruction using both the trace-norm, as well as the less-studied max-norm, and present reconstruction guarantees based on existing analysis on the Rademacher complexity of the unit balls of these norms. We show how these are superior in several ways to recently published guarantees based on specialized analysis.
RIS
TY - CPAPER TI - Concentration-Based Guarantees for Low-Rank Matrix Reconstruction AU - Rina Foygel AU - Nathan Srebro BT - Proceedings of the 24th Annual Conference on Learning Theory DA - 2011/12/21 ED - Sham M. Kakade ED - Ulrike von Luxburg ID - pmlr-v19-foygel11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 19 SP - 315 EP - 340 L1 - http://proceedings.mlr.press/v19/foygel11a/foygel11a.pdf UR - https://proceedings.mlr.press/v19/foygel11a.html AB - We consider the problem of approximately reconstructing a partially-observed, approximately low-rank matrix. This problem has received much attention lately, mostly using the trace-norm as a surrogate to the rank. Here we study low-rank matrix reconstruction using both the trace-norm, as well as the less-studied max-norm, and present reconstruction guarantees based on existing analysis on the Rademacher complexity of the unit balls of these norms. We show how these are superior in several ways to recently published guarantees based on specialized analysis. ER -
APA
Foygel, R. & Srebro, N.. (2011). Concentration-Based Guarantees for Low-Rank Matrix Reconstruction. Proceedings of the 24th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 19:315-340 Available from https://proceedings.mlr.press/v19/foygel11a.html.

Related Material