Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing

Abstract

Low-rank matrix estimation plays a central role in various applications across science and engineering. Recently, nonconvex formulations based on matrix factorization are provably solved by simple gradient descent algorithms with strong computational and statistical guarantees. However, when the low-rank matrices are asymmetric, existing approaches rely on adding a regularization term to balance the scale of the two matrix factors which in practice can be removed safely without hurting the performance when initialized via the spectral method. In this paper, we provide a theoretical justification to this for the matrix sensing problem, which aims to recover a low-rank matrix from a small number of linear measurements. As long as the measurement ensemble satisfies the restricted isometry property, gradient descent -- in conjunction with spectral initialization -- converges linearly without the need of explicitly promoting balancedness of the factors; in fact, the factors stay balanced automatically throughout the execution of the algorithm. Our analysis is based on analyzing the evolution of a new distance metric that directly accounts for the ambiguity due to invertible transforms, and might be of independent interest.

arXiv commentTo appear on IEEE Trans. on Signal Processing

References in corpus (22)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion
• Recovering low-rank matrices from few coefficients in any basis
• An overview of low-rank matrix recovery from incomplete observations
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Robust Spectral Compressed Sensing via Structured Matrix Completion
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Fast Algorithms for Robust PCA via Gradient Descent
• Global Optimality in Low-rank Matrix Optimization
• Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• The Non-convex Geometry of Low-rank Matrix Optimization
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• Dropping Convexity for Faster Semi-definite Optimization
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent

Cited by in corpus (11)

• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy
• Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Projected Gradient Descent for Spectral Compressed Sensing via Symmetric Hankel Factorization
• Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect
• Implicit Regularization in Matrix Sensing via Mirror Descent
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization