mlsanityData to 7 Oct 2026

Structured Sampling for Robust Euclidean Distance Geometry

arXiv 2412.10664 ↗First posted 14 Dec 2024cs.LG cs.IT math.ITcited by 2

Not on the map. Why?

Abstract (arXiv)

This paper addresses the problem of estimating the positions of points from distance measurements corrupted by sparse outliers. Specifically, we consider a setting with two types of nodes: anchor nodes, for which exact distances to each other are known, and target nodes, for which complete but corrupted distance measurements to the anchors are available. To tackle this problem, we propose a novel algorithm powered by Nystr"om method and robust principal component analysis. Our method is computationally efficient as it processes only a localized subset of the distance matrix and does not require distance measurements between target nodes. Empirical evaluations on synthetic datasets, designed to mimic sensor localization, and on molecular experiments, demonstrate that our algorithm achieves accurate recovery with a modest number of anchors, even in the presence of high levels of sparse outliers.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 19 of its 65 references that are in the map. First posted on arXiv 14 Dec 2024.

Builds on

19 of 65 references.

References · 19

  1. 2013Efficient Estimation of Word Representations in Vector Spacecited by 4,346
  2. 2013Revisiting the Nystrom Method for Improved Large-Scale Machine Learningcited by 76
  3. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
  4. 2021Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detectioncited by 34
  5. 2017Accelerated Alternating Projections for Robust Principal Component Analysiscited by 25
  6. 2021Robust CUR Decomposition: Theory and Imaging Applicationscited by 20
  7. 2018Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completioncited by 18
  8. 2020Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimationcited by 16
  9. 2017Robust PCA by Manifold Optimizationcited by 13
  10. 2022Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Samplingcited by 12
  11. 2022Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completioncited by 11
  12. 2018Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learningcited by 9
7 more
  1. 2022Riemannian CUR Decompositions for Robust Principal Component Analysiscited by 7
  2. 2024On the Robustness of Cross-Concentrated Sampling for Matrix Completioncited by 5
  3. 2023Localization from structured distance matrices via low-rank matrix recoverycited by 4
  4. 2024Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guaranteescited by 4
  5. 2024Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recoverycited by 4
  6. 2024Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descentcited by 3
  7. 2024Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimizationcited by 3

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025A Dual Basis Approach for Structured Robust Euclidean Distance Geometrycited by 1
  2. 2025Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustnesscited by 0