Euclidean Distance Matrices: Essential theory, algorithms, and applications

Ivan Dokmanic, Reza Parhizkar, Juri Ranieri, Martin Vetterli

TL;DR

This paper provides a comprehensive tutorial on Euclidean Distance Matrices (EDMs), bridging a knowledge gap between signal processing and EDM theory. It details fundamental EDM properties, presents algorithms for data completion and denoising, and showcases diverse applications from sensor networks to acoustics, aiming to equip practitioners with the tools to leverage EDMs.

What Problem Does This Paper Address?

The authors identify a disconnect: while Euclidean Distance Matrices (EDMs) possess valuable properties and find applications across various scientific domains (psychometrics, crystallography, machine learning, sensor networks, acoustics), they remain relatively unknown within the signal processing community. This lack of awareness hinders the adoption of powerful EDM-based techniques. The paper aims to rectify this by offering a concise and accessible introduction to EDM theory, algorithms, and practical applications, thereby accelerating their use in signal processing and related fields.

Methods

The paper covers a range of methods related to EDMs:

  • Fundamental Properties: It delves into core EDM properties like rank and (non)definiteness, explaining how these characteristics are derived from the underlying point configurations.
  • Classical Multidimensional Scaling (MDS): The paper explains classical MDS as a foundational algorithm for reconstructing point sets from distance data, often involving eigenvalue decomposition. It discusses variations of MDS based on different centering strategies.
  • EDM Completion and Denoising:
    • Rank-Based Approaches: Algorithms are presented that exploit the EDM rank property (Theorem 1, stating rank is at most $d+2$ for points in $\mathbb{R}^d$) for completing and denoising distance data.
  • Alternating Rank-Based EDM Completion (Algorithm 2): This algorithm iteratively enforces observed distances and the rank constraint.
  • OptSpace (Algorithm 3): A more advanced low-rank matrix completion algorithm adapted for EDM problems, particularly effective for large, randomly missing entries.
  • Semidefinite Relaxation (SDR) (Algorithm 5): This approach formulates EDM completion as a semidefinite program, offering a robust but computationally intensive solution.
  • Alternating Descent (Algorithm 4): An efficient algorithm for minimizing the s-stress cost function, particularly useful for large datasets.
  • Multidimensional Unfolding (MDU): A specialized EDM completion problem arising in scenarios like microphone calibration where distances are structured (e.g., between two distinct sets of points).
  • Orthogonal Procrustes Problem: A method for aligning reconstructed point sets with known anchor points, crucial when absolute orientation is lost in the distance representation.

Datasets

The paper does not explicitly mention specific named datasets for training or evaluation. Instead, it relies on:

  • Simulated Data: The algorithms are evaluated using synthetically generated data, often involving random point configurations in Euclidean spaces, with varying degrees of noise and missing entries.
  • Real-World Examples: Applications are illustrated using scenarios like Swiss train travel times (converted to distances), microphone calibration, and room shape reconstruction from echoes.

Key Insights and Ideas

  • EDMs are more than just distance matrices: Their inherent structure, particularly their rank property, makes them powerful tools for data completion and denoising, even with incomplete or noisy measurements.
  • Rigid transformations are invisible to EDMs: The absolute position and orientation of a point set are lost when converting to an EDM. This means reconstructions are unique only up to rigid transformations (rotations, translations, reflections).
  • The rank property is surprisingly strong: For points in $\mathbb{R}^d$, the EDM rank is at most $d+2$, meaning for large numbers of points ($n$), the EDM has a significantly lower rank than its dimensions suggest. This is key to efficient algorithms.
  • EDMs offer a unified framework: The paper demonstrates how seemingly disparate problems like sensor network localization, molecular conformation, and even phase retrieval can be framed as EDM problems, allowing for a common set of algorithmic tools.
  • Unlabeled distances are a significant challenge but solvable: For many point sets, distances uniquely determine the configuration (up to rigid transformations). However, identifying the correct pairing of distances to points (labeling) is a hard problem, especially with noise.
  • Semidefinite Programming offers robustness: While computationally expensive, SDR provides a principled way to handle noisy and incomplete EDM data.

Key Results

  • Algorithm Performance: The paper compares several algorithms (Alternating Descent, Rank Alternation, Semidefinite Relaxation, OptSpace, Crocco's Method) on simulated data with random deletions and noise.
  • OptSpace performs poorly on smaller matrices ($n=20$) with random deletions but is effective for very large matrices.
  • Semidefinite Relaxation (SDR) generally shows the highest success rate and robustness to noise, but is the slowest.
  • Alternating Descent offers a good balance of performance and speed, especially for large datasets.
  • Rank Alternation is the simplest but can be less robust.
  • MDU Performance: In the Multidimensional Unfolding scenario (structured missing data), SDR and Alternating Descent perform well, while OptSpace struggles due to the non-random missing entries.
  • Practical Applications: The paper demonstrates successful applications in:
  • Swiss Train Map Reconstruction: Illustrates classical MDS with real-world (noisy) data.
  • Microphone Calibration: Shows how MDU can be used to determine microphone and source locations.
  • Room Shape Reconstruction: Demonstrates how EDMs can robustly reconstruct room geometry from acoustic echoes.
  • Ultrasound Tomography Calibration: Highlights the use of rank-based EDM completion for sensor calibration.

Limitations and Future Work

  • Computational Cost: SDR, while robust, is computationally expensive, limiting its use for very large-scale problems.
  • OptSpace Limitations: OptSpace is designed for large matrices and random missing entries; it struggles with smaller matrices and structured missing data.
  • Unlabeled Distances: Efficient algorithms for reconstructing point sets from unlabeled, noisy distances remain an open challenge. The paper suggests further research into faster algorithms and understanding the impact of noise on the reconstructed point set distribution.
  • Manifolds and Geodesic Distances: The paper poses questions about EDM properties on manifolds and the use of geodesic distances, suggesting this as a direction for future research.
  • Analytical Minimum of s-stress: Finding an analytical minimum for the s-stress cost function is noted as an open problem.
  • Data Fidelity in SDR: The paper mentions that the data fidelity term in the SDR can be moved to constraints, suggesting alternative formulations.

Summary updated

Abstract

Euclidean distance matrices (EDMs) are matrices of the squared distances between points. The definition is deceivingly simple; thanks to their many useful properties, they have found applications in psychometrics, crystallography, machine learning, wireless sensor networks, acoustics, and more. Despite the usefulness of EDMs, they seem to be insufficiently known in the signal processing community. Our goal is to rectify this mishap in a concise tutorial. We review the fundamental properties of EDMs, such as rank or (non)definiteness, and show how the various EDM properties can be used to design algorithms for completing and denoising distance data. Along the way, we demonstrate applications to microphone position calibration, ultrasound tomography, room reconstruction from echoes, and phase retrieval. By spelling out the essential algorithms, we hope to fast-track the readers in applying EDMs to their own problems. The code for all of the described algorithms and to generate the figures in the article is available online at http://lcav.epfl.ch/ivan.dokmanic. Finally, we suggest directions for further research.
BibTeX
@inproceedings{dokmanic2015euclidean,
  author = {Ivan Dokmanic and Reza Parhizkar and Juri Ranieri and Martin Vetterli},
  title = {{Euclidean Distance Matrices: Essential theory, algorithms, and applications}},
  booktitle = {IEEE Signal Process. Mag},
  year = {2015},
  url = {https://openreview.net/forum?id=Dwf4IKT8wJV},
}
Figure