Low-rank Solutions of Linear Matrix Equations via Procrustes Flow

被引：0

作者：

Tu, Stephen ^{[1
]}

Boczar, Ross ^{[1
]}

Simchowitz, Max ^{[1
]}

Soltanolkotabi, Mahdi ^{[2
]}

Recht, Benjamin ^{[1
]}

机构：

[1] Univ Calif Berkeley, EECS Dept, Berkeley, CA 94720 USA

[2] USC, Ming Hsieh Dept Elect Engn, Los Angeles, CA USA

来源：

INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 48 | 2016年 / 48卷

关键词：

SIGNAL RECOVERY;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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 n(1) x n(2) matrix of rank r when the number of measurements exceeds a constant times (n(1) + n(2))r.

引用

页数：10

共 38 条

[21] Recovering Low-Rank Matrices From Few Coefficients in Any Basis
Gross, David
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2011, 57 (03) : 1548 - 1566
[22] Understanding Alternating Minimization for Matrix Completion
Hardt, Moritz
[J]. 2014 55TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2014), 2014, : 651 - 660
[23] Jain P., 2013, STOC
[24] Matrix Completion From a Few Entries
Keshavan, Raghunandan H.
Montanari, Andrea
Oh, Sewoong
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 56 (06) : 2980 - 2998
[25] Meka R., 2009, ARXIV09095457
[26] CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
Needell, D.
Tropp, J. A.
[J]. APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, 2009, 26 (03) : 301 - 321
[27] Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit
Needell, Deanna
Vershynin, Roman
[J]. FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2009, 9 (03) : 317 - 334
[28] Recht B., J MACHINE LEARNING R, V12, P3413
[29] Parallel stochastic gradient algorithms for large-scale matrix completion
Recht B.
Ré C.
[J]. Mathematical Programming Computation, 2013, 5 (2) : 201 - 226
[30] Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
Recht, Benjamin
Fazel, Maryam
Parrilo, Pablo A.
[J]. SIAM REVIEW, 2010, 52 (03) : 471 - 501

← 1 2 3 4 →