mlsanityData to 14 Oct 2026

Guarantees of Riemannian Optimization for Low Rank Matrix Completion

arXiv 1603.06610 ↗First posted 21 Mar 2016math.NA cs.NA math.OCcited by 19

Not on the map. Why?

Abstract (arXiv)

We study the Riemannian optimization methods on the embedded manifold of low rank matrices for the problem of matrix completion, which is about recovering a low rank matrix from its partial entries. Assume m entries of an n× n rank r matrix are sampled independently and uniformly with replacement. We first prove that with high probability the Riemannian gradient descent and conjugate gradient descent algorithms initialized by one step hard thresholding are guaranteed to converge linearly to the measured matrix provided beginalign* m≥ C_kappa n1.5rlog1.5(n), endalign* where C_kappa is a numerical constant depending on the condition number of the underlying matrix. The sampling complexity has been further improved to beginalign* m≥ C_kappa nr2log2(n) endalign* via the resampled Riemannian gradient descent initialization. The analysis of the new initialization procedure relies on an asymmetric restricted isometry property of the sampling operator and the curvature of the low rank matrix manifold. Numerical simulation shows that the algorithms are able to recover a low rank matrix from nearly the minimum number of measurements.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). First posted on arXiv 21 Mar 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 4; 2023: 2; 2024: 4; 2025: 3; 2026: 2.

19 papers.

Sort:

  1. 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
  2. 2021A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samplescited by 13
  3. 2022Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Samplingcited by 12
  4. 2022Riemannian CUR Decompositions for Robust Principal Component Analysiscited by 7
  5. 2021Tensor train completion: local recovery guarantees via Riemannian optimizationcited by 6
  6. 2021Fully-Connected Tensor Network Decomposition for Robust Tensor Completion Problemcited by 5
  7. 2022Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penaltiescited by 4
  8. 2023Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regretcited by 4
  9. 2023Localization from structured distance matrices via low-rank matrix recoverycited by 4
  10. 2024Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guaranteescited by 4
  11. 2024Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descentcited by 3
  12. 2024Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimizationcited by 3
7 more
  1. 2022Learning Transition Operators From Sparse Space-Time Samplescited by 1
  2. 2024Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functionscited by 1
  3. 2025Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descentcited by 1
  4. 2025Fast and Provable Tensor-Train Format Tensor Completion via Precondtioned Riemannian Gradient Descentcited by 0
  5. 2025Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustnesscited by 0
  6. 2026Subspace-Constrained Federated Learning with Low-Rank Adaptationcited by 0
  7. 2026Tensor Completion using Subspace Informationcited by 0