# Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion

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

## Key facts

- Cited by 18 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 12 Apr 2018.

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

- [Practical Equivariances via Relational Conditional Neural Processes](https://mlsanity.com/paper/2306.10915/) (2023)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Completeness of Atomic Structure Representations](https://mlsanity.com/paper/2302.14770/) (2023)
- [A dual basis approach to multidimensional scaling](https://mlsanity.com/paper/2303.05682/) (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)
- [An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function](https://mlsanity.com/paper/2503.23832/) (2025)
- [Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization](https://mlsanity.com/paper/2410.16982/) (2024)
- [Spectal Harmonics: Bridging Spectral Embedding and Matrix Completion in Self-Supervised Learning](https://mlsanity.com/paper/2305.19818/) (2023)
- [Structured Sampling for Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2412.10664/) (2024)
- [Sharp analysis of EM for learning mixtures of pairwise differences](https://mlsanity.com/paper/2302.10066/) (2023)
- [Riemannian Langevin Monte Carlo schemes for sampling PSD matrices with fixed rank](https://mlsanity.com/paper/2309.04072/) (2023)
- [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)
- [Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness](https://mlsanity.com/paper/2508.00091/) (2025)
- [Recovering Wasserstein Distance Matrices from Few Measurements](https://mlsanity.com/paper/2509.19250/) (2025)
- [Bayesian Matrix Completion Under Geometric Constraints](https://mlsanity.com/paper/2601.22765/) (2026)
- [Random features for Grassmannian kernel approximation with bounded rank-one projections](https://mlsanity.com/paper/2608.04227/) (2026)

## Abstract (arXiv)

The Euclidean distance geometry problem arises in a wide variety of applications, from determining molecular conformations in computational chemistry to localization in sensor networks. When the distance information is incomplete, the problem can be formulated as a nuclear norm minimization problem. In this paper, this minimization program is recast as a matrix completion problem of a low-rank r Gram matrix with respect to a suitable basis. The well known restricted isometry property can not be satisfied in this scenario. Instead, a dual basis approach is introduced to theoretically analyze the reconstruction problem. If the Gram matrix satisfies certain coherence conditions with parameter nu, the main result shows that the underlying configuration of n points can be recovered with very high probability from O(nrnulog2(n)) uniformly random samples. Computationally, simple and fast algorithms are designed to solve the Euclidean distance geometry problem. Numerical tests on different three dimensional data and protein molecules validate effectiveness and efficiency of the proposed algorithms.