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.
Code (0)
등록된 구현이 없습니다.
Tasks
Polynomial Neural NetworksQuantum State TomographyRetrievalSimilar Papers 제목 키워드 기반
Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
In practical instances of nonconvex matrix factorization, the rank of the true solution $r^{\star}$ is often unknown, so the rank $r$ of the model can be overspecified as $r>r^{\star}$. This over-parameterized regime of …
Guaranteed Matrix Completion via Non-convex Factorization
Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization can be solved very efficiently by standard algorithms in practice. However, due to …
Matrix CompletionNonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Substantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. While conventional wisdom often takes a dim view of nonco…
Matrix CompletionRetrievalColumn $\ell_{2,0}$-norm regularized factorization model of low-rank matrix recovery and its computation
This paper is concerned with the column $\ell_{2,0}$-regularized factorization model of low-rank matrix recovery problems and its computation. The column $\ell_{2,0}$-norm of factor matrices is introduced to promote colu…
Matrix Completion1-Bit Matrix Completion under Exact Low-Rank Constraint
We consider the problem of noisy 1-bit matrix completion under an exact rank constraint on the true underlying matrix $M^*$. Instead of observing a subset of the noisy continuous-valued entries of a matrix $M^*$, we obse…
Matrix Completion