Euclidean Distance Matrices: Essential theory, algorithms, and applications

By Ivan Dokmanić, Reza Parhizkar, Juri Ranieri, Martin Vetterli. IEEE Signal Processing Magazine, 2015

580 citations recorded by the source corpus.

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.

Subfields: Computer Vision and Pattern Recognition, Electrical and Electronic Engineering, Signal Processing

View Paper: https://www.semanticscholar.org/paper/e2b4090903fc408b0967874ddd20acaacf5fa4b2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

Inducing a hierarchy for multi-class classification problems (2021, methodology): “…methods such as multi-dimensional scaling (Wickelmaier, 2003) and spectral embedding (Von Luxburg, 2007) are well studied in particular settings (Dokmanic et al., 2015; Athreya et al., 2017) and are generally used as dimensionality reduction techniques for clustering (Lyzinski et al., 2014) and…”