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 can not 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 three dimensional data and protein molecules validate effectiveness and efficiency of the proposed algorithms.
Introduction
The Euclidean Distance Geometry (EDG) problem is a classic challenge: given a set of points where only a subset of pairwise distances is known, can one reconstruct the full 3D coordinates? This problem is central to fields like structural biology—specifically determining protein shapes from NMR data—and telecommunications for sensor network localization.
Mathematically, this is often treated as completing a "Distance Matrix." However, distance matrices are cumbersome to work with directly. A more elegant approach is to complete the "Gram Matrix" (the matrix of inner products of the point coordinates). The primary challenge is that standard matrix completion theory assumes sampling individual entries in an orthonormal basis. In EDG, measurements are linear combinations of Gram matrix entries, and the underlying basis is non-orthogonal, causing traditional "exact recovery" proofs to fail.
Methodology
To bridge this gap, the authors introduce two primary innovations: a theoretical framework based on dual bases and a computationally efficient algorithm.
Dual Basis Framework
To handle the non-orthogonal nature of EDG measurements, the authors introduce a "dual basis" approach. This allows for a theoretical analysis using a "golfing scheme"—a mathematical technique used to construct a "dual certificate." This certificate guarantees that the solution to the nuclear norm minimization problem is both unique and correct, even without the standard restricted isometry property.
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, they enforce the positive semi-definite constraint by factorizing the Gram matrix $X$ as $PP^T$. This factorization makes the algorithm significantly faster and more scalable to large datasets.
Key Insights
- 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 $X$, the authors reduce the complexity of the problem and the number of samples required for recovery.
- Coherence and Sample Complexity: The paper defines specific "coherence" conditions ($\nu$) for the EDG basis. If the points are "incoherent" (information is spread out), recovery is highly efficient. They establish a rigorous bound: for $n$ points in $r$ dimensions, only $O(nr\nu \log^2 n)$ random distance samples are needed for perfect reconstruction.
Experimental Results
The researchers evaluated their approach on synthetic 3D objects (spheres, cow models) and real-world protein molecules (PDB IDs: 1AX8, 1RGS, etc.) from the Protein Data Bank.
- Performance Gains: The proposed algorithm significantly outperformed existing state-of-the-art methods. For a dataset of 2,920 points (US Cities), the method converged in 72.5 seconds, compared to 2,417 seconds for the baseline ADM method.
- Accuracy: The method achieves near-perfect reconstruction (relative errors near $10^{-9}$) even with sampling rates as low as 3-5%.
- Robustness: The framework remains stable under Gaussian noise, demonstrating its practicality for real-world laboratory data where measurements are imperfect. Numerical tests also confirmed a sharp "phase transition," where the probability of success jumps to 1 once the sample threshold is met.
Conclusion
This work provides a robust theoretical and computational foundation for solving the EDG problem via low-rank matrix completion. While the current model assumes uniform random sampling, future research will address non-uniform, local sampling patterns typical of NMR data. Furthermore, the dual basis approach developed here may be generalized to recover low-rank matrices from measurements in any non-orthogonal basis.
Summary updated