# Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 80 references that are in the map.
- First posted on arXiv 22 Oct 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (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)
- [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (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)
- [Robust Spectral Compressed Sensing via Structured Matrix Completion](https://mlsanity.com/paper/1304.8126/) (2013)
- [Multidimensional Scaling, Sammon Mapping, and Isomap: Tutorial and Survey](https://mlsanity.com/paper/2009.08136/) (2020)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence](https://mlsanity.com/paper/2011.08360/) (2020)
- [Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries](https://mlsanity.com/paper/2002.01849/) (2020)
- [Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression](https://mlsanity.com/paper/2208.11846/) (2022)
- [Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery](https://mlsanity.com/paper/1703.05038/) (2017)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [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)
- [Distance Geometry and Data Science](https://mlsanity.com/paper/1909.08544/) (2019)

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

- [Structured Sampling for Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2412.10664/) (2024)
- [A Dual Basis Approach for Structured Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2505.18414/) (2025)
- [Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training](https://mlsanity.com/paper/2511.04485/) (2025)

## Abstract (arXiv)

The problem of finding suitable point embedding or geometric configurations given only Euclidean distance information of point pairs arises both as a core task and as a sub-problem in a variety of machine learning applications. In this paper, we aim to solve this problem given a minimal number of distance samples. To this end, we leverage continuous and non-convex rank minimization formulations of the problem and establish a local convergence guarantee for a variant of iteratively reweighted least squares (IRLS), which applies if a minimal random set of observed distances is provided. As a technical tool, we establish a restricted isometry property (RIP) restricted to a tangent space of the manifold of symmetric rank-r matrices given random Euclidean distance measurements, which might be of independent interest for the analysis of other non-convex approaches. Furthermore, we assess data efficiency, scalability and generalizability of different reconstruction algorithms through numerical experiments with simulated data as well as real-world data, demonstrating the proposed algorithm's ability to identify the underlying geometry from fewer distance samples compared to the state-of-the-art.