# Guarantees of Riemannian Optimization for Low Rank Matrix Completion

arXiv: https://arxiv.org/abs/1603.06610 · HTML: https://mlsanity.com/paper/1603.06610/

## Key facts

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

## Built on by (most cited first, 19 of 19)

- [Provable Tensor-Train Format Tensor Completion by Riemannian Optimization](https://mlsanity.com/paper/2108.12163/) (2021)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Riemannian CUR Decompositions for Robust Principal Component Analysis](https://mlsanity.com/paper/2206.09042/) (2022)
- [Tensor train completion: local recovery guarantees via Riemannian optimization](https://mlsanity.com/paper/2110.03975/) (2021)
- [Fully-Connected Tensor Network Decomposition for Robust Tensor Completion Problem](https://mlsanity.com/paper/2110.08754/) (2021)
- [Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties](https://mlsanity.com/paper/2211.14645/) (2022)
- [Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regret](https://mlsanity.com/paper/2306.03372/) (2023)
- [Localization from structured distance matrices via low-rank matrix recovery](https://mlsanity.com/paper/2311.18076/) (2023)
- [Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees](https://mlsanity.com/paper/2410.06376/) (2024)
- [Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent](https://mlsanity.com/paper/2406.07409/) (2024)
- [Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization](https://mlsanity.com/paper/2410.16982/) (2024)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)
- [Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions](https://mlsanity.com/paper/2407.19446/) (2024)
- [Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent](https://mlsanity.com/paper/2504.19530/) (2025)
- [Fast and Provable Tensor-Train Format Tensor Completion via Precondtioned Riemannian Gradient Descent](https://mlsanity.com/paper/2501.13385/) (2025)
- [Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness](https://mlsanity.com/paper/2508.00091/) (2025)
- [Subspace-Constrained Federated Learning with Low-Rank Adaptation](https://mlsanity.com/paper/2606.22724/) (2026)
- [Tensor Completion using Subspace Information](https://mlsanity.com/paper/2609.24501/) (2026)

## 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.