Reconstructing Point Sets From Distance Distributions

Shuai Huang, Ivan DokmanicIEEE TSP 2018 · DOI · OpenReview

TL;DR

This paper introduces a novel "distance distribution matching" approach to reconstruct the positions of points on a line (turnpike problem) or a loop (beltway problem) using only unassigned, noisy pairwise distances. The method is robust to noise and is the first practical solution for large-scale, noisy beltway problems.

What Problem Does This Paper Address?

The paper tackles the "unassigned distance geometry problem" (uDGP) in one dimension. This means we're given a set of distances between pairs of points, but we don't know which distance corresponds to which pair of points. This is a harder problem than the "assigned" version where we know the pairings. Specifically, the authors focus on two related problems: the "turnpike problem" (points on a line) and the "beltway problem" (points on a loop). These problems have applications in areas like DNA sequencing (partial digestion) and peptide sequencing. Existing methods struggle with noise and large datasets, especially for the beltway problem.

Methods

The core idea is to represent the unknown point locations as a probability distribution over a discretized domain. This distribution is then used to derive a "distance distribution" that can be compared to the measured distances. The authors formulate this as a constrained, non-convex optimization problem. They solve this using projected gradient descent, a common optimization technique. A key innovation is the use of a spectral initializer to provide a good starting point for the optimization, inspired by techniques from phase retrieval. For extracting the final point locations from the estimated distribution, they employ agglomerative clustering. The method is designed to naturally handle noise by approximating the true distance distribution.

Datasets

Not explicitly discussed in terms of standard benchmark datasets. The authors use simulated data generated from various point configurations and noise levels. They also mention experiments on real genome data for the partial digestion application.

Key Insights and Ideas

  • Distance Distribution as a Proxy: The paper cleverly uses the distribution of pairwise distances as an intermediate representation. This allows them to bypass the difficult combinatorial problem of assigning distances to pairs.
  • Non-Convex Optimization for Robustness: By framing the problem as a non-convex optimization task, they can incorporate noise directly into the objective function, leading to more robust solutions than methods that assume perfect data.
  • Spectral Initialization: The spectral initializer, borrowed from phase retrieval, proves effective in guiding the optimization towards good solutions, especially in challenging scenarios with many repeated distances.
  • Beltway Problem Breakthrough: The paper presents the first practical algorithm for the large-scale, noisy beltway problem, a significant advancement in this area.

Key Results

  • State-of-the-Art Turnpike Recovery: The proposed method achieves state-of-the-art performance on the turnpike problem, outperforming conventional backtracking approaches, especially in the presence of noise.
  • First Practical Beltway Solution: The paper offers the first practical algorithm for the large-scale, noisy beltway problem, demonstrating its ability to reconstruct point configurations on a loop.
  • Robustness to Noise: Numerical experiments show that the method is significantly more robust to noise compared to existing backtracking algorithms.
  • Efficiency: While not explicitly quantified in terms of speedup, the method is described as computationally efficient and suitable for large-scale problems.

Limitations and Future Work

  • Discretization: The method relies on discretizing the domain, which can increase the problem size. While they explore ways to mitigate this, it remains a potential limitation.
  • Theoretical Guarantees for Initialization: The authors acknowledge that a rigorous proof for the convergence of the spectral initializer to a global optimum is still an open question, though it performs well empirically.
  • Convergence in Noisy Case: Theoretical analysis of convergence in the presence of noise is left as an open question.
  • Uniqueness: While the problem is often uniquely solvable, the paper assumes this for its analysis.
  • Future Work: The authors suggest extending the approach to 3D unknown view tomography and exploring new biological applications. They also leave the theoretical analysis of convergence in the presence of noise as an open problem.

Summary updated

Abstract

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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N$</tex-math></inline-formula> points via an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N$</tex-math></inline-formula> -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.
BibTeX
@article{huang2018reconstructing,
  author = {Shuai Huang and Ivan Dokmanic},
  title = {{Reconstructing Point Sets From Distance Distributions}},
  journal = {IEEE Trans. Signal Process.},
  year = {2018},
  doi = {10.1109/tsp.2021.3063458},
}
Figure