Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-Rank Matrix Completion

Abiy Tasissa, Rongjie Lai

TL;DR

This paper provides a theoretical and computational framework for solving the Euclidean Distance Geometry (EDG) problem—reconstructing the 3D coordinates of points from a limited set of pairwise distances. By recasting the problem as a low-rank matrix completion of the Gram matrix and employing a novel "dual basis" analysis, the authors prove that exact reconstruction is possible with high probability using relatively few random samples, while offering a fast algorithm that significantly outperforms existing methods.

What Problem Does This Paper Address?

The Euclidean Distance Geometry (EDG) problem is a classic challenge: if you are given a set of points but only know the distances between some of them, can you figure out where all the points are located? This has massive implications for fields like structural biology (determining protein shapes from NMR data) and telecommunications (localizing sensors in a network).

Mathematically, this is often treated as completing a "Distance Matrix." However, distance matrices are cumbersome. A more elegant approach is to complete the "Gram Matrix" (the matrix of inner products of the point coordinates). The challenge is that standard matrix completion theory assumes you are sampling individual entries of a matrix in an orthonormal basis. In EDG, the "measurements" are linear combinations of the Gram matrix entries, and the underlying basis is not orthogonal. This makes traditional proofs of "exact recovery" fail.

Methods

The authors bridge this gap using two primary innovations:

  1. Dual Basis Framework: To handle the non-orthogonal nature of the EDG measurements, the authors introduce a "dual basis" approach. This allows them to theoretically analyze the reconstruction using a "golfing scheme"—a mathematical technique used to construct a "dual certificate" that guarantees the solution to the nuclear norm minimization problem is unique and correct.
  2. Factorized Augmented Lagrangian Algorithm: On the computational side, the authors solve the nuclear norm minimization problem using an Augmented Lagrangian Method (ALM). Crucially, instead of performing a costly eigendecomposition at every iteration (standard in many solvers), they enforce the positive semi-definite constraint by factorizing the Gram matrix $X$ as $PP^T$. This makes the algorithm much faster and scalable to large datasets.

Datasets

The researchers evaluated their approach on both synthetic and real-world structural data:

  • Synthetic 3D Objects: A sphere, a 3D model of a cow, and a map of US cities.
  • Protein Molecules: Real atomic coordinates for proteins (PDB IDs: 1AX8, 1RGS, 1PTQ, 1KDH, 1BPM) sourced from the Protein Data Bank. These represent complex, non-uniform geometries typical of biological research.

Key Insights and Ideas

  • Rank Efficiency: The Gram matrix $X$ has rank $r$ (usually 3 for 3D space), whereas the Distance matrix $D$ has rank $r+2$. By focusing on completing $X$, the authors reduce the complexity of the problem and the number of samples required for recovery.
  • Coherence is Key: The paper defines specific "coherence" conditions for the EDG basis. Intuitively, coherence measures how "spread out" the information is. If the points are arranged such that the information is concentrated in just a few measurements, recovery is harder. They prove that for "incoherent" point sets, recovery is highly efficient.
  • Sample Complexity: They establish a rigorous bound: for $n$ points in $r$ dimensions, you only need roughly $O(nr\nu \log^2 n)$ random distance samples to achieve perfect reconstruction.

Key Results

  • Speedup: In head-to-head comparisons with previous state-of-the-art algorithms (like the ADM method), the proposed algorithm was orders of magnitude faster. For example, on a dataset of 2,920 points (US Cities), the authors' method converged in 72.5 seconds, compared to 2,417 seconds for the baseline.
  • Accuracy: The method achieves near-perfect reconstruction (relative errors as low as $10^{-9}$) even with very low sampling rates (e.g., 3-5% of total possible distances).
  • Noise Robustness: The framework remains stable when Gaussian noise is added to the distance measurements, showing that it is practical for real-world laboratory data where measurements are never perfect.
  • Phase Transition: Numerical tests confirmed a sharp "phase transition," where the probability of successful recovery jumps from 0 to 1 once a specific threshold of samples is reached, validating the theoretical predictions.

Limitations and Future Work

While the paper provides a "sketch" of how the method handles noise, the authors acknowledge that a more rigorous, precise characterization of the noise stability (specifically the function $f$ relating noise level to error) is needed.

Additionally, the current work assumes distances are sampled uniformly at random. In many real-world applications (like NMR), distance information is "local" (you only know distances between nearby atoms). Extending this dual basis theory to non-uniform, local sampling patterns is a primary direction for future research. Finally, the authors suggest that this dual basis approach could be generalized to recover low-rank matrices from measurements in any non-orthogonal basis.

Summary updated

Abstract

The Euclidean distance geometry problem arises in a wide variety of applications, from determining molecular conformations in computational chemistry to localization in sensor networks. When the distance information is incomplete, the problem can be formulated as a nuclear norm minimization problem. In this paper, this minimization program is recast as a matrix completion problem of a low-rank $r$ Gram matrix with respect to a suitable basis. The well-known restricted isometry property cannot be satisfied in this scenario. Instead, a dual basis approach is introduced to theoretically analyze the reconstruction problem. If the Gram matrix satisfies certain coherence conditions with parameter $\nu $ , the main result shows that the underlying configuration of $n$ points can be recovered with very high probability from $O(nr\nu \log ^{2}(n))$ uniformly random samples. Computationally, simple and fast algorithms are designed to solve the Euclidean distance geometry problem. Numerical tests on different 3-D data and protein molecules validate the effectiveness and efficiency of the proposed algorithms.
BibTeX
@article{tasissa2019exact,
  author = {Abiy Tasissa and Rongjie Lai},
  title = {{Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-Rank Matrix Completion}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=nGWf7l4fzY},
}

Loading related content...

Figure