Nonconvex matrix factorization from rank-one measurements

Yuanxin Li, Cong Ma, Yuxin Chen, Yuejie Chi

Research output: Contribution to conferencePaperpeer-review

12 Scopus citations


We consider the problem of recovering low-rank matrices from random rank-one measurements, which spans numerous applications including phase retrieval, quantum state tomography, and learning shallow neural networks with quadratic activations, among others. Our approach is to directly estimate the low-rank factor by minimizing a nonconvex least-squares loss function via vanilla gradient descent, following a tailored spectral initialization. When the true rank is small, this algorithm is guaranteed to converge to the ground truth (up to global ambiguity) with near-optimal sample and computational complexities with respect to the problem size. To the best of our knowledge, this is the first theoretical guarantee that achieves near optimality in both metrics. In particular, the key enabler of near-optimal computational guarantees is an implicit regularization phenomenon: without explicit regularization, both spectral initialization and the gradient descent iterates automatically stay within a region incoherent with the measurement vectors. This feature allows one to employ much more aggressive step sizes compared with the ones suggested in prior literature, without the need of sample splitting.

Original languageEnglish (US)
StatePublished - 2020
Event22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019 - Naha, Japan
Duration: Apr 16 2019Apr 18 2019


Conference22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Statistics and Probability


Dive into the research topics of 'Nonconvex matrix factorization from rank-one measurements'. Together they form a unique fingerprint.

Cite this