Low-rank Solutions of Linear Matrix Equations via Procrustes Flow

Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, Ben Recht
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:964-973, 2016.

Abstract

In this paper we study the problem of recovering a low-rank matrix from linear measurements. Our algorithm, which we call Procrustes Flow, starts from an initial estimate obtained by a thresholding scheme followed by gradient descent on a non-convex objective. We show that as long as the measurements obey a standard restricted isometry property, our algorithm converges to the unknown matrix at a geometric rate. In the case of Gaussian measurements, such convergence occurs for a n1 \times n2 matrix of rank r when the number of measurements exceeds a constant times (n1 + n2)r.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-tu16, title = {Low-rank Solutions of Linear Matrix Equations via Procrustes Flow}, author = {Tu, Stephen and Boczar, Ross and Simchowitz, Max and Soltanolkotabi, Mahdi and Recht, Ben}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {964--973}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/tu16.pdf}, url = {https://proceedings.mlr.press/v48/tu16.html}, abstract = {In this paper we study the problem of recovering a low-rank matrix from linear measurements. Our algorithm, which we call Procrustes Flow, starts from an initial estimate obtained by a thresholding scheme followed by gradient descent on a non-convex objective. We show that as long as the measurements obey a standard restricted isometry property, our algorithm converges to the unknown matrix at a geometric rate. In the case of Gaussian measurements, such convergence occurs for a n1 \times n2 matrix of rank r when the number of measurements exceeds a constant times (n1 + n2)r.} }
Endnote
%0 Conference Paper %T Low-rank Solutions of Linear Matrix Equations via Procrustes Flow %A Stephen Tu %A Ross Boczar %A Max Simchowitz %A Mahdi Soltanolkotabi %A Ben Recht %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-tu16 %I PMLR %P 964--973 %U https://proceedings.mlr.press/v48/tu16.html %V 48 %X In this paper we study the problem of recovering a low-rank matrix from linear measurements. Our algorithm, which we call Procrustes Flow, starts from an initial estimate obtained by a thresholding scheme followed by gradient descent on a non-convex objective. We show that as long as the measurements obey a standard restricted isometry property, our algorithm converges to the unknown matrix at a geometric rate. In the case of Gaussian measurements, such convergence occurs for a n1 \times n2 matrix of rank r when the number of measurements exceeds a constant times (n1 + n2)r.
RIS
TY - CPAPER TI - Low-rank Solutions of Linear Matrix Equations via Procrustes Flow AU - Stephen Tu AU - Ross Boczar AU - Max Simchowitz AU - Mahdi Soltanolkotabi AU - Ben Recht BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-tu16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 964 EP - 973 L1 - http://proceedings.mlr.press/v48/tu16.pdf UR - https://proceedings.mlr.press/v48/tu16.html AB - In this paper we study the problem of recovering a low-rank matrix from linear measurements. Our algorithm, which we call Procrustes Flow, starts from an initial estimate obtained by a thresholding scheme followed by gradient descent on a non-convex objective. We show that as long as the measurements obey a standard restricted isometry property, our algorithm converges to the unknown matrix at a geometric rate. In the case of Gaussian measurements, such convergence occurs for a n1 \times n2 matrix of rank r when the number of measurements exceeds a constant times (n1 + n2)r. ER -
APA
Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M. & Recht, B.. (2016). Low-rank Solutions of Linear Matrix Equations via Procrustes Flow. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:964-973 Available from https://proceedings.mlr.press/v48/tu16.html.

Related Material