Nonconvex Matrix Factorization From Rank-One Measurements

DOI10.1109/TIT.2021.3050427MaRDI QIDQ5001494zbMATH OpenOpenAlexFDO

Authors Yuan-Xin Li, Cong Ma, Yuxin Chen, Yuejie Chi

Publication date 22 July 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.06286

zbMATH Keywords

minimization of nonconvex least-squares loss functionnear-optimal computational complexitynear-optimal sample complexityrandom rank-one measurementsrecovering low-rank matricesvanilla gradient descent

Mathematics Subject Classification ID

Numerical methods for matrix equations (65F45) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: 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.

Recommendations

• Nonsmooth rank-one matrix factorization landscape
• Low-rank factorization for rank minimization with nonconvex regularizers
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
• Nonnegative matrix factorization with rank regularization and hard constraint
• Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
• Rank-constrained nonnegative matrix factorization for data representation
• A Non-Euclidean Gradient Descent Framework for Non-Convex Matrix Factorization
• Nonconvex Robust Low-Rank Matrix Recovery
• Matrix Completion Based on Non-Convex Low-Rank Approximation

Cited in

(6)

• Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
• Improved performance guarantees for orthogonal group synchronization via generalized power method
• Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent
• The power of preconditioning in overparameterized low-rank matrix sensing

This page was built for publication: Nonconvex Matrix Factorization From Rank-One Measurements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5001494)