# Reconstructing Point Sets from Distance Distributions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2018.

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

- [Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors](https://mlsanity.com/paper/2309.09032/) (2023)
- [Total Least Squares Phase Retrieval](https://mlsanity.com/paper/2102.00927/) (2021)
- [Orthogonal Matrix Retrieval with Spatial Consensus for 3D Unknown-View Tomography](https://mlsanity.com/paper/2207.02985/) (2022)
- [High-Rate Phase Association with Travel Time Neural Fields](https://mlsanity.com/paper/2307.07572/) (2023)

## Abstract (arXiv)

We address the problem of reconstructing a set of points on a line or a loop from their unassigned noisy pairwise distances. When the points lie on a line, the problem is known as the turnpike; when they are on a loop, it is known as the beltway. We approximate the problem by discretizing the domain and representing the N points via an N-hot encoding, which is a density supported on the discretized domain. We show how the distance distribution is then simply a collection of quadratic functionals of this density and propose to recover the point locations so that the estimated distance distribution matches the measured distance distribution. This can be cast as a constrained nonconvex optimization problem which we solve using projected gradient descent with a suitable spectral initializer. We derive conditions under which the proposed distance distribution matching approach locally converges to a global optimizer at a linear rate. Compared to the conventional backtracking approach, our method jointly reconstructs all the point locations and is robust to noise in the measurements. We substantiate these claims with state-of-the-art performance across a number of numerical experiments. Our method is the first practical approach to solve the large-scale noisy beltway problem where the points lie on a loop.