# Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 82 references that are in the map.
- First posted on arXiv 8 Oct 2024.

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

- [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)
- [Accelerated Alternating Projections for Robust Principal Component Analysis](https://mlsanity.com/paper/1711.05519/) (2017)
- [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)
- [Riemannian CUR Decompositions for Robust Principal Component Analysis](https://mlsanity.com/paper/2206.09042/) (2022)
- [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)
- [Localization from structured distance matrices via low-rank matrix recovery](https://mlsanity.com/paper/2311.18076/) (2023)
- [A Riemannian Dimension-reduced Second Order Method with Application in Sensor Network Localization](https://mlsanity.com/paper/2304.10092/) (2023)
- [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)

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

- [Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery](https://mlsanity.com/paper/2410.16826/) (2024)
- [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)

## Abstract (arXiv)

The problem of determining the configuration of points from partial distance information, known as the Euclidean Distance Geometry (EDG) problem, is fundamental to many tasks in the applied sciences. In this paper, we propose two algorithms grounded in the Riemannian optimization framework to address the EDG problem. Our approach formulates the problem as a low-rank matrix completion task over the Gram matrix, using partial measurements represented as expansion coefficients of the Gram matrix in a non-orthogonal basis. For the first algorithm, under a uniform sampling with replacement model for the observed distance entries, we demonstrate that, with high probability, a Riemannian gradient-like algorithm on the manifold of rank-r matrices converges linearly to the true solution, given initialization via a one-step hard thresholding. This holds provided the number of samples, m, satisfies m ≥ O(n7/4r2 log(n)). With a more refined initialization, achieved through resampled Riemannian gradient-like descent, we further improve this bound to m ≥ O(nr2 log(n)). Our analysis for the first algorithm leverages a non-self-adjoint operator and depends on deriving eigenvalue bounds for an inner product matrix of restricted basis matrices, leveraging sparsity properties for tighter guarantees than previously established. The second algorithm introduces a self-adjoint surrogate for the sampling operator. This algorithm demonstrates strong numerical performance on both synthetic and real data. Furthermore, we show that optimizing over manifolds of higher-than-rank-r matrices yields superior numerical results, consistent with recent literature on overparameterization in the EDG problem.