Nonconvex Matrix Factorization from Rank-One Measurements
  We consider the problem of recovering low-rank matrices from random rank-one
measurements, which spans numerous applications including covariance sketching,
phase retrieval, quantum state tomography, and learning shallow polynomial
neural networks, among others. Our approach is to directly estimate the
low-rank factor by minimizing a nonconvex quadratic 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 complexity and computational
complexity. To the best of our knowledge, this is the first 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.
