# Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 80 references that are in the map.
- First posted on arXiv 28 Apr 2025.

## Builds on (most cited first, 30 of 34)

- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent](https://mlsanity.com/paper/1605.07051/) (2016)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [The Global Optimization Geometry of Low-Rank Matrix Optimization](https://mlsanity.com/paper/1703.01256/) (2017)
- [Recovery guarantee of weighted low-rank approximation via alternating minimization](https://mlsanity.com/paper/1602.02262/) (2016)
- [Guarantees of Riemannian Optimization for Low Rank Matrix Completion](https://mlsanity.com/paper/1603.06610/) (2016)
- [Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion](https://mlsanity.com/paper/1804.04310/) (2018)
- [Robust Spectral Compressed Sensing via Structured Matrix Completion](https://mlsanity.com/paper/1304.8126/) (2013)
- [Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA](https://mlsanity.com/paper/1711.01742/) (2017)
- [Universal Matrix Completion](https://mlsanity.com/paper/1402.2324/) (2014)
- [Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion](https://mlsanity.com/paper/2204.03316/) (2022)
- [A State-of-the-Art Survey on Multidimensional Scaling Based Localization Techniques](https://mlsanity.com/paper/1906.03585/) (2019)
- [Matrix completion with deterministic pattern - a geometric perspective](https://mlsanity.com/paper/1802.00047/) (2018)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion](https://mlsanity.com/paper/2402.06756/) (2024)
- [Spectral Compressed Sensing via Projected Gradient Descent](https://mlsanity.com/paper/1707.09726/) (2017)
- [A dual basis approach to multidimensional scaling](https://mlsanity.com/paper/2303.05682/) (2023)
- [Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version](https://mlsanity.com/paper/2403.08442/) (2024)
- [Low-rank Matrix Completion in a General Non-orthogonal Basis](https://mlsanity.com/paper/1812.05786/) (2018)
- [Riemannian Optimization for Distance-Geometric Inverse Kinematics](https://mlsanity.com/paper/2108.13720/) (2021)
- [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)
- [Distance Geometry and Data Science](https://mlsanity.com/paper/1909.08544/) (2019)

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

- [Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness](https://mlsanity.com/paper/2508.00091/) (2025)

## Abstract (arXiv)

This paper proposes and analyzes a gradient-type algorithm based on Burer-Monteiro factorization, called the Asymmetric Projected Gradient Descent (APGD), for reconstructing the point set configuration from partial Euclidean distance measurements, known as the Euclidean Distance Matrix Completion (EDMC) problem. By paralleling the incoherence matrix completion framework, we show for the first time that global convergence guarantee with exact recovery of this routine can be established given O(μ2 r3 kappa2 n log n) Bernoulli random observations without any sample splitting. Unlike leveraging the tangent space Restricted Isometry Property (RIP) and local curvature of the low-rank embedding manifold in some very recent works, our proof provides extra upper bounds that act as analogies of the random graph lemma under EDMC setting. The APGD works surprisingly well and numerical experiments demonstrate exact linear convergence behavior in rich-sample regions yet deteriorates rapidly when compared with the performance obtained by optimizing the s-stress function, i.e., the standard but unexplained non-convex approach for EDMC, if the sample size is limited. While virtually matching our theoretical prediction, this unusual phenomenon might indicate that: (i) the power of implicit regularization is weakened when specified in the APGD case; (ii) the stabilization of such new gradient direction requires substantially more samples than the information-theoretic limit would suggest.