Fast matrix completion without the condition number

Moritz Hardt, Mary Wootters
Proceedings of The 27th Conference on Learning Theory, PMLR 35:638-678, 2014.

Abstract

We give the first algorithm for Matrix Completion that achieves running time and sample complexity that is polynomial in the rank of the unknown target matrix, \emphlinear in the dimension of the matrix, and \emphlogarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-hardt14a, title = {Fast matrix completion without the condition number}, author = {Hardt, Moritz and Wootters, Mary}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {638--678}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/hardt14a.pdf}, url = {https://proceedings.mlr.press/v35/hardt14a.html}, abstract = {We give the first algorithm for Matrix Completion that achieves running time and sample complexity that is polynomial in the rank of the unknown target matrix, \emphlinear in the dimension of the matrix, and \emphlogarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise. } }
Endnote
%0 Conference Paper %T Fast matrix completion without the condition number %A Moritz Hardt %A Mary Wootters %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-hardt14a %I PMLR %P 638--678 %U https://proceedings.mlr.press/v35/hardt14a.html %V 35 %X We give the first algorithm for Matrix Completion that achieves running time and sample complexity that is polynomial in the rank of the unknown target matrix, \emphlinear in the dimension of the matrix, and \emphlogarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise.
RIS
TY - CPAPER TI - Fast matrix completion without the condition number AU - Moritz Hardt AU - Mary Wootters BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-hardt14a PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 638 EP - 678 L1 - http://proceedings.mlr.press/v35/hardt14a.pdf UR - https://proceedings.mlr.press/v35/hardt14a.html AB - We give the first algorithm for Matrix Completion that achieves running time and sample complexity that is polynomial in the rank of the unknown target matrix, \emphlinear in the dimension of the matrix, and \emphlogarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise. ER -
APA
Hardt, M. & Wootters, M.. (2014). Fast matrix completion without the condition number. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:638-678 Available from https://proceedings.mlr.press/v35/hardt14a.html.

Related Material