GNMR: A Provable One-Line Algorithm for Low Rank Matrix Recovery

DOI10.1137/21M1433812zbMath1492.65115arXiv2106.12933OpenAlexW3173745758MaRDI QIDQ5089733

Boaz Nadler, Pini Zilber

Publication date: 15 July 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

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

zbMATH Keywords

matrix completionGauss-Newtonmatrix recoverylow rank matricesmatrix sensing

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Matrix completion problems (15A83) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Related Items (2)

Stochastic Gauss-Newton algorithms for online PCA ⋮ Re-thinking high-dimensional mathematical statistics. Abstracts from the workshop held May 15--21, 2022

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed point and Bregman iterative methods for matrix rank minimization
• Low rank matrix completion by alternating steepest descent methods
• The restricted isometry property and its implications for compressed sensing
• Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Matrix recipes for hard thresholding methods
• Fixed-rank matrix factorizations and Riemannian low-rank optimization
• Low-rank matrix completion via preconditioned optimization on the Grassmann manifold
• Trust-region methods on Riemannian manifolds
• Exact matrix completion via convex optimization
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• Low-Rank Matrix Completion by Riemannian Optimization
• Normalized Iterative Hard Thresholding for Matrix Completion
• Guaranteed Matrix Completion via Non-Convex Factorization
• Uniqueness of Low-Rank Matrix Completion by Rigidity Theory
• A Singular Value Thresholding Algorithm for Matrix Completion
• Low-rank Matrix Recovery via Iteratively Reweighted Least Squares Minimization
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• On $l_q$ Optimization and Matrix Completion
• CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
• Global Optimality in Low-Rank Matrix Optimization
• On the Quadratic Convergence of the Cubic Regularization Method under a Local Error Bound Condition
• Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries
• Non-convex low-rank matrix recovery with arbitrary outliers via median-truncated gradient descent
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Low-Rank Matrix Recovery With Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Nonconvex Rectangular Matrix Completion via Gradient Descent Without ℓ₂,_∞ Regularization
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Leave-One-Out Approach for Matrix Completion: Primal and Dual Analysis
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Finding Low-Rank Solutions via Nonconvex Matrix Factorization, Efficiently and Provably
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Matrix Completion From a Few Entries
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• A Simpler Approach to Matrix Completion
• Low-Rank Optimization with Trace Norm Penalty
• Low-rank matrix completion using alternating minimization

This page was built for publication: GNMR: A Provable One-Line Algorithm for Low Rank Matrix Recovery