Euclidean Distance Matrices: Essential theory, algorithms, and applications

Ivan Dokmanic, Reza Parhizkar, Juri Ranieri, Martin Vetterli

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Article number7298562
Pages (from-to)12-30
Number of pages19
JournalIEEE Signal Processing Magazine
Volume32
Issue number6
DOIs
StatePublished - Nov 1 2015
Externally publishedYes

Keywords

  • Eigenvalues and eigenfunctions
  • Euclidean distance
  • Image reconstruction
  • Reflection
  • Signal processing algorithms
  • Symmetric matrices

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Euclidean Distance Matrices: Essential theory, algorithms, and applications'. Together they form a unique fingerprint.

Cite this