# A Dual Basis Approach for Structured Robust Euclidean Distance Geometry

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 66 references that are in the map.
- First posted on arXiv 23 May 2025.

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

- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Non-convex Robust PCA](https://mlsanity.com/paper/1410.7660/) (2014)
- [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016)
- [Accelerated Alternating Projections for Robust Principal Component Analysis](https://mlsanity.com/paper/1711.05519/) (2017)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion](https://mlsanity.com/paper/1804.04310/) (2018)
- [Phase retrieval with random Gaussian sensing vectors by alternating projections](https://mlsanity.com/paper/1609.03088/) (2016)
- [Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning](https://mlsanity.com/paper/1810.09569/) (2018)
- [Compressed sensing of low-rank plus sparse matrices](https://mlsanity.com/paper/2007.09457/) (2020)
- [Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version](https://mlsanity.com/paper/2403.08442/) (2024)
- [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)
- [Outlier Detection for Robust Multi-dimensional Scaling](https://mlsanity.com/paper/1802.02341/) (2018)
- [Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization](https://mlsanity.com/paper/2410.16982/) (2024)
- [Robust Multi-Dimensional Scaling via Accelerated Alternating Projections](https://mlsanity.com/paper/2501.02208/) (2025)
- [Structured Sampling for Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2412.10664/) (2024)

## 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)

Euclidean Distance Matrix (EDM), which consists of pairwise squared Euclidean distances of a given point configuration, finds many applications in modern machine learning. This paper considers the setting where only a set of anchor nodes is used to collect the distances between themselves and the rest. In the presence of potential outliers, it results in a structured partial observation on EDM with partial corruptions. Note that an EDM can be connected to a positive semi-definite Gram matrix via a non-orthogonal dual basis. Inspired by recent development of non-orthogonal dual basis in optimization, we propose a novel algorithmic framework, dubbed Robust Euclidean Distance Geometry via Dual Basis (RoDEoDB), for recovering the Euclidean distance geometry, i.e., the underlying point configuration. The exact recovery guarantees have been established in terms of both the Gram matrix and point configuration, under some mild conditions. Empirical experiments show superior performance of RoDEoDB on sensor localization and molecular conformation datasets.