# Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 97 references that are in the map.
- First posted on arXiv 31 Jul 2025.

## Builds on (most cited first, 19 of 19)

- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [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)
- [Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints](https://mlsanity.com/paper/2009.10395/) (2020)
- [Low-Rank Covariance Function Estimation for Multidimensional Functional Data](https://mlsanity.com/paper/2008.12919/) (2020)
- [Solving Partial Differential Equations on Manifolds From Incomplete Inter-Point Distance](https://mlsanity.com/paper/1701.02843/) (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)
- [A Riemannian Dimension-reduced Second Order Method with Application in Sensor Network Localization](https://mlsanity.com/paper/2304.10092/) (2023)
- [Sensor network localization has a benign landscape after low-dimensional relaxation](https://mlsanity.com/paper/2507.15662/) (2025)
- [A novel low-rank matrix completion approach to estimate missing entries in Euclidean distance matrices](https://mlsanity.com/paper/1711.06182/) (2017)
- [Blessing of High-Order Dimensionality: from Non-Convex to Convex Optimization for Sensor Network Localization](https://mlsanity.com/paper/2308.02278/) (2023)
- [Structured Sampling for Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2412.10664/) (2024)
- [Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent](https://mlsanity.com/paper/2504.19530/) (2025)
- [A Dual Basis Approach for Structured Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2505.18414/) (2025)
- [Robust Node Localization for Rough and Extreme Deployment Environments](https://mlsanity.com/paper/2507.03856/) (2025)

## Abstract (arXiv)

The problem of recovering the configuration of points from their partial pairwise distances, referred to as the Euclidean Distance Matrix Completion (EDMC) problem, arises in a broad range of applications, including sensor network localization, molecular conformation, and manifold learning. In this paper, we propose a Riemannian optimization framework for solving the EDMC problem by formulating it as a low-rank matrix completion task over the space of positive semi-definite Gram matrices. The available distance measurements are encoded as expansion coefficients in a non-orthogonal basis, and optimization over the Gram matrix implicitly enforces geometric consistency through nonnegativity and the triangle inequality, a structure inherited from classical multidimensional scaling. Under a Bernoulli sampling model for observed distances, we prove that Riemannian gradient descent on the manifold of rank-r matrices locally converges linearly with high probability when the sampling probability satisfies p≥ O(nu2 r2log(n)/n), where nu is an EDMC-specific incoherence parameter. Furthermore, we provide an initialization candidate using a one-step hard thresholding procedure that yields convergence, provided the sampling probability satisfies p ≥ O(nu r3/2log3/4(n)/n1/4). A key technical contribution of this work is the analysis of a symmetric linear operator arising from a dual basis expansion in the non-orthogonal basis, which requires analysis of a second order degenerate U-statistic to establish an optimal restricted isometry property in the presence of coupled terms. Empirical evaluations on synthetic data demonstrate that our algorithm achieves competitive performance relative to state-of-the-art methods. Moreover, we provide a geometric interpretation of matrix incoherence tailored to the EDMC setting and provide robustness guarantees for our method.