# Localization from structured distance matrices via low-rank matrix recovery

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 77 references that are in the map.
- First posted on arXiv 29 Nov 2023.

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

- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (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)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Matrix Coherence and the Nystrom Method](https://mlsanity.com/paper/1408.2044/) (2014)
- [CUR Algorithm for Partially Observed Matrices](https://mlsanity.com/paper/1411.0860/) (2014)
- [Solving Partial Differential Equations on Manifolds From Incomplete Inter-Point Distance](https://mlsanity.com/paper/1701.02843/) (2017)
- [Orthogonal Inductive Matrix Completion](https://mlsanity.com/paper/2004.01653/) (2020)
- [A dual basis approach to multidimensional scaling](https://mlsanity.com/paper/2303.05682/) (2023)
- [Low-rank Matrix Completion in a General Non-orthogonal Basis](https://mlsanity.com/paper/1812.05786/) (2018)
- [Positive Semidefinite Matrix Completion, Universal Rigidity and the Strong Arnold Property](https://mlsanity.com/paper/1301.6616/) (2013)
- [Matrix Completion from Non-Uniformly Sampled Entries](https://mlsanity.com/paper/1806.10308/) (2018)

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

- [Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees](https://mlsanity.com/paper/2410.06376/) (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)

We study the problem of determining the configuration of n points by using their distances to m nodes, referred to as anchor nodes. One sampling scheme is Nystrom sampling, which assumes known distances between the anchors and between the anchors and the n points, while the distances among the n points are unknown. For this scheme, a simple adaptation of the Nystrom method, which is often used for kernel approximation, is a viable technique to estimate the configuration of the anchors and the n points. In this manuscript, we propose a modified version of Nystrom sampling, where the distances from every node to one central node are known, but all other distances are incomplete. In this setting, the standard Nystrom approach is not applicable, necessitating an alternative technique to estimate the configuration of the anchors and the n points. We show that this problem can be framed as the recovery of a low-rank submatrix of a Gram matrix. Using synthetic and real data, we demonstrate that the proposed approach can exactly recover configurations of points given sufficient distance samples. This underscores that, in contrast to methods that rely on global sampling of distance matrices, the task of estimating the configuration of points can be done efficiently via structured sampling with well-chosen reliable anchors. Finally, our main analysis is grounded in a specific centering of the points. With this in mind, we extend previous work in Euclidean distance geometry by providing a general dual basis approach for points centered anywhere.