mlsanityData to 7 Oct 2026

Global Optimality in Low-rank Matrix Optimization

arXiv 1702.07945 ↗First posted 25 Feb 2017cs.IT math.IT math.OCcited by 35

Not on the map. Why?

Abstract (arXiv)

This paper considers the minimization of a general objective function f(X) over the set of rectangular n× m matrices that have rank at most r. To reduce the computational burden, we factorize the variable X into a product of two smaller matrices and optimize over these two matrices instead of X. Despite the resulting nonconvexity, recent studies in matrix completion and sensing have shown that the factored problem has no spurious local minima and obeys the so-called strict saddle property (the function has a directional negative curvature at all critical points but local minima). We analyze the global geometry for a general and yet well-conditioned objective function f(X) whose restricted strong convexity and restricted strong smoothness constants are comparable. In particular, we show that the reformulated objective function has no spurious local minima and obeys the strict saddle property. These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) can provably solve the factored problem with global convergence.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Feb 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 7; 2023: 6; 2024: 6; 2025: 7; 2026: 2.

35 papers.

Sort:

By area:

  1. 2021A Geometric Analysis of Neural Collapse with Unconstrained Featurescited by 226
  2. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 40
  3. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
  4. 2024The Utility and Complexity of in- and out-of-Distribution Machine Unlearningcited by 20
  5. 2025LoRA Training Provably Converges to a Low-Rank Global Minimum or It Fails Loudly (But it Probably Won't Fail)cited by 19
  6. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  7. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  8. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  9. 2022A Validation Approach to Over-parameterized Matrix and Image Recoverycited by 8
  10. 2024Guaranteed Nonconvex Factorization Approach for Tensor Train Recoverycited by 8
  11. 2021Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurementscited by 7
  12. 2022Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Ratecited by 7
23 more
  1. 2026A Bitter Lesson for Data Filteringcited by 7
  2. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  3. 2022Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensingcited by 5
  4. 2022Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithmcited by 4
  5. 2024Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decompositioncited by 4
  6. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  7. 2025A Scalable Factorization Approach for High-Order Structured Tensor Recoverycited by 4
  8. 2021Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regimecited by 3
  9. 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 3
  10. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 3
  11. 2024Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimizationcited by 3
  12. 2021Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensingcited by 2
  13. 2023Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?cited by 2
  14. 2023Gradient descent in matrix factorization: Understanding large initializationcited by 2
  15. 2022Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularizationcited by 1
  16. 2024Absence of spurious solutions far from ground truth: A low-rank analysis with high-order lossescited by 1
  17. 2025Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minimacited by 1
  18. 2025A Complete Loss Landscape Analysis of Regularized Deep Matrix Factorizationcited by 1
  19. 2023Robust matrix completion via Novel M-estimator Functionscited by 0
  20. 2024Multi-Head Encoding for Extreme Label Classificationcited by 0
  21. 2025RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guaranteescited by 0
  22. 2025A Saddle Point Remedy: Power of Variable Elimination in Non-convex Optimizationcited by 0
  23. 2026A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexitycited by 0