Euclidean Distance Matrices: Essential Theory, Algorithms and Applications
arXiv:1502.07541 · doi:10.1109/MSP.2015.2398954
Abstract
Euclidean distance matrices (EDM) are matrices of 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. We show how 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. Matlab code for all the described algorithms, and to generate the figures in the paper, is available online. Finally, we suggest directions for further research.
- 17 pages, 12 figures, to appear in IEEE Signal Processing Magazine - change of title in the last revision
References in corpus (1)
Cited by in corpus (51)
- Noise Learning Based Denoising Autoencoder
- ClaSP -- Parameter-free Time Series Segmentation
- LLMatic: Neural Architecture Search via Large Language Models and Quality Diversity Optimization
- Optimal noise-canceling networks
- Metric Factorization: Recommendation beyond Matrix Factorization
- Convex Iteration for Distance-Geometric Inverse Kinematics
- Completeness of Atomic Structure Representations
- Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection
- Safe and Smooth: Certified Continuous-Time Range-Only Localization
- Localizing Unsynchronized Sensors with Unknown Sources
- MYRiAD: A Multi-Array Room Acoustic Database
- Cooperative Navigation Using Pairwise Communication with Ranging and Magnetic Anomaly Measurements
- Efficient Rigid Body Localization based on Euclidean Distance Matrix Completion for AGV Positioning under Harsh Environment
- Quartic First-Order Methods for Low-Rank Minimization
- Sublinear Time Low-Rank Approximation of Distance Matrices
- On Procrustes Analysis in Hyperbolic Space
- Sample-Optimal Low-Rank Approximation of Distance Matrices
- Shapes from Echoes: Uniqueness from Point-to-Plane Distance Matrices
- Reconstruction of Protein Structures from Single-Molecule Time Series
- Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
- The body matrix and its determinant
- Don't take it lightly: Phasing optical random projections with unknown operators
- A new algorithm for the DMDGP subclass of Distance Geometry Problems
- Exploiting Rays in Blind Localization of Distributed Sensor Arrays
- Accurate Protein Structure Prediction by Embeddings and Deep Learning Representations
- Geometrically Mappable Image Features
- Riemannian Optimization for Distance-Geometric Inverse Kinematics
- Exploring Public Attention in the Circular Economy through Topic Modelling with Twin Hyperparameter Optimisation
- 3D genome reconstruction from partially phased Hi-C data
- Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion
- Invariance Measures for Neural Networks
- DynoLoc: Infrastructure-free RF Tracking in Dynamic Indoor Environments
- Ordinal Distance Metric Learning with MDS for Image Ranking
- Gromov-Wasserstein Distance based Object Matching: Asymptotic Inference
- SENATE: A Permissionless Byzantine Consensus Protocol in Wireless Networks
- Calculating the symmetry number of flexible sphere clusters
- Structured Sampling for Robust Euclidean Distance Geometry
- A two-phase rank-based algorithm for low-rank matrix completion
- Realizability of Planar Point Embeddings from Angle Measurements
- How can classical multidimensional scaling go wrong?
- Inducing a hierarchy for multi-class classification problems
- Geometry of Similarity Comparisons
- Generative inpainting of incomplete Euclidean distance matrices of trajectories generated by a fractional Brownian motion
- GISR: Geometric Initialization and Silhouette-based Refinement for Single-View Robot Pose and Configuration Estimation
- The trajectoRIR Database: Room Acoustic Recordings Along a Trajectory of Moving Microphones
- Satellite Autonomous Clock Fault Monitoring with Inter-Satellite Ranges Using Euclidean Distance Matrices
- An impossible utopia in distance geometry
- NEMR: Network Embedding on Metric of Relation
- Learning to recover orientations from projections in single-particle cryo-EM
- Inverse Kinematics as Low-Rank Euclidean Distance Matrix Completion
- Remarks on the interpolation method