PaperlayerView exact revision on arXiv

Source-linked AI summary

Euclidean Distance Matrices: Essential Theory, Algorithms and Applications

Ivan Dokmanic, Reza Parhizkar, Juri Ranieri, Martin Vetterli

arXiv:1502.07541v2cs.OH

TL;DR

The paper presents EDMs as broadly useful tools for distance-based reconstruction and completion, including sensor-network calibration and room reconstruction from echoes. It explains algorithms exploiting EDM structure and concludes that semidefinite relaxation performs best for ad-hoc microphone array localization, while SDR is computationally slow for large matrices.

  • Problem

    EDMs deserve more attention because common distance measurements support applications including sensor calibration and room reconstruction.

  • Method

    The tutorial develops EDM-based completion and reconstruction methods, including trimming over-represented observations, Procrustes alignment, and semidefinite programming.

  • Results

    Semidefinite relaxation is reported as the best-performing algorithm for ad-hoc microphone array localization, while SDR is the slowest tested method.

  • Takeaways & Limitations

    EDMs provide a practical framework for filtering unlabeled echoes and solving distance-based localization problems.

  • Takeaways & Limitations

    SDR becomes impractical for larger matrices because CVX can run out of memory and essentially never finish for n = 1000.

Abstract

from arXiv · show

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.

I. INTRODUCTION

EDMs encode squared pairwise distances and support reconstruction, completion, and denoising across applications including sensor localization, molecular conformation, psychometrics, acoustics, and phase retrieval. This tutorial introduces their essential theory and practical algorithms for signal-processing readers.

  • EDM motivation: EDMs are matrices of squared Euclidean distances used to represent point configurations and estimate network topology from measured distance proxies.Wireless sensors may infer distances from received signal strengths or time-of-arrival measurements.
  • Problem variations: Practical EDM problems commonly involve noisy or missing distances, and some applications additionally lose the labels identifying which distances belong to which pairs.Unlabeled distances arise in room reconstruction from echoes and sparse phase retrieval.
  • Illustrative application: Classical MDS, essentially an eigenvalue decomposition, reconstructs a usable Swiss city map from train-time data despite speed variation, stops, nonstraight railroads, and unknown distances.The resulting configuration was rotated and scaled to align with the actual map.
  • Core problems: Distance-geometry problems ask whether a matrix is an EDM and whether incomplete distances admit a point configuration in a specified embedding dimension.The embedding dimension is the dimension of the smallest affine space containing the points.
  • Tutorial scope: The tutorial reviews EDM properties and algorithms while emphasizing applications such as microphone calibration, molecular conformation, sensor localization, and room reconstruction.It also provides online implementations and deliberately focuses on accessible examples rather than an exhaustive treatment.

II. FROM POINTS TO EDMS AND BACK

The section develops EDMs from point coordinates and shows that their structure is low-rank and invariant to rigid transformations. Consequently, distances contain enough information to recover shape but not absolute position or orientation.

  • EDM construction: For points stored as columns of X, squared pairwise distances form an EDM that can be expressed using the Gram matrix X⊤X and rank-one diagonal terms.This assembly formula underlies structural analysis and reconstruction algorithms.
  • Rank property: An EDM generated by points in R^d has rank at most d + 2, because the Gram-matrix term has rank at most d and two remaining terms each have rank one.The bound is independent of the number of generating points.
  • Affine dimension: The relevant dimension is the affine dimension of the point set, so points lying on a plane in R3 can generate an EDM of rank four rather than five.Subtracting a point or the centroid translates the affine subspace to its parallel linear subspace without changing its dimension.
  • Recoverability: Although an EDM can contain more scalars than the coordinate list, its encoding loses the degrees of freedom associated with rigid transformations.This identifies what is recoverable from distances and what is intrinsically unidentifiable.
  • Rigid invariance: Rotations, reflections, and translations preserve all pairwise distances, so EDMs cannot determine a point set’s absolute position or orientation.Different reconstruction procedures may therefore return rigidly transformed realizations of the same configuration.

B. Reconstructing the Point Set From Distances

Classical MDS reconstructs points by converting an EDM into a positive semidefinite Gram matrix and applying an eigenvalue decomposition. Centering choices determine the coordinate origin, while truncating eigenvalues handles noisy data.

  • First-point reconstruction: Fixing the first point at the origin allows the first EDM column to provide the squared norms needed to construct a Gram matrix.This corresponds to translating all points by the first point.
  • Eigenvalue reconstruction: Classical MDS obtains the point set from an eigenvalue decomposition of the positive semidefinite Gram matrix and retains the corresponding nonzero eigendirections.The reconstructed coordinates generate the original EDM up to a rigid transformation.
  • EDM characterization: Gower’s criterion states that D is an EDM exactly when an appropriate centered transform of D is positive semidefinite.The geometric centering matrix provides a systematic choice, and different admissible centering vectors correspond to different translations.
  • Noisy data: For noisy distances, classical MDS can discard all but the d largest eigenvalues to obtain a d-dimensional reconstruction.This extends the procedure beyond the noiseless setting assumed in the derivation.
  • Coordinate choice: Using the centering matrix places the reconstructed point set’s centroid at the origin, whereas first-column centering places its first point at the origin.Both coordinate choices preserve the same distance matrix.

C. Orthogonal Procrustes Problem

Distances lose a point set’s absolute position and orientation, so reconstructed configurations must be aligned to known anchors. Orthogonal Procrustes centers the anchor subsets and finds the best rotation or reflection, while degrees-of-freedom analysis clarifies what EDM structure retains.

  • Alignment: Distances cannot recover a point set’s absolute position or orientation, leaving reconstructions equivalent up to rigid transformations.
  • Alignment: Procrustes alignment uses known anchor coordinates to align a reconstructed subset with the target configuration.The anchors are typically a small subset of all points.
  • Alignment: The procedure first removes the centroids of the anchor sets, then solves an orthogonal Procrustes problem for the best rotation or reflection.
  • Alignment: The optimal orthogonal transformation is obtained from the SVD of the centered cross-product matrix, with R = V U^⊤.
  • Degrees of freedom: Rank, symmetry, and hollowness do not fully characterize an EDM, because additional geometric constraints remain.
  • Degrees of freedom: For d = 3, using rank alone requires about 30% more data than exploiting the full EDM structure, while little is lost for large n and d = o(n).

E. Summary

The tutorial consolidates EDM theory, reconstruction, and algorithms for noisy or incomplete distance data. Its summary emphasizes classical MDS, rank-based methods, and degrees-of-freedom analysis as practical organizing principles.

  • Summary: Classical MDS reconstructs points through an eigenvalue decomposition, while the rank property provides a basis for completion and denoising algorithms.
  • Summary: EDM rank is useful but not sufficient: degrees-of-freedom analysis shows that additional EDM structure matters, especially at finite dimensions.
  • Summary: EDM measurements are often noisy or incomplete because of measurement errors, limited sensing range, or structured missingness.
  • Summary: The tutorial treats EDM approximation and completion together, using observed entries and the desired embedding dimension as constraints.
  • Summary: A mask matrix selects observed entries and supports entrywise comparison, restriction, and enforcement during completion.

A. Exploiting the Rank Property

EDMs for points in R^d have rank at most d + 2, enabling conceptually simple completion and denoising methods. These include alternating rank enforcement and low-rank matrix-completion approaches such as OptSpace.

  • Rank property: An EDM generated by points in R^d has rank at most d + 2, a property that supports completion and denoising.
  • Alternating completion: Alternating enforcement may converge to an EDM, a non-EDM matrix with the correct rank, or fail to converge.
  • OptSpace: OptSpace recovers a low-rank matrix from noisy, incomplete observations by trimming over-represented rows and columns before factorized optimization.
  • OptSpace: The OptSpace objective is nonconvex, but correctly initialized gradient descent reaches the global optimum with high probability under the stated conditions.
  • OptSpace: OptSpace initializes gradient descent from a scaled rank-r SVD projection, and its optimization separates the convex update of S from gradient-based updates of A and B.

B. Multidimensional Scaling

Multidimensional scaling fits point configurations to noisy distances, while EDM rank-based calibration addresses incomplete ultrasound measurements. The section also presents stress objectives and coordinate-descent methods, with nonconvexity limiting general guarantees.

  • Multidimensional scaling: Multidimensional scaling finds a best-fitting point configuration from noisy distances and originated as a way to visualize similarities between objects.
  • Multidimensional scaling: Classical MDS minimizes a Frobenius-norm discrepancy involving the input matrix and the Gram matrix in the target embedding dimension.
  • Ultrasound calibration: In ultrasound tomography, rank-based EDM calibration handles sensor-position uncertainty and yields error bounds; reported calibration error vanishes as sensor count increases.
  • Stress objectives: Distance-based objectives compare observed dissimilarities with distances between estimated locations, but their feasible EDM sets are generally nonconvex.
  • Stress objectives: Raw stress is not globally differentiable, motivating iterative majorization, convex-analysis methods, and steepest descent approaches.
  • Alternating descent: The s-stress objective is separable across points and coordinates, enabling alternating coordinate descent with analytically solvable one-coordinate subproblems.

C. Semidefinite Programming

The paper characterizes EDMs through centered Gram matrices, combining rank and positive-semidefinite constraints to formulate completion and approximation as semidefinite programs. Relaxations improve tractability but may produce solutions in higher dimensions or face numerical issues from nullspaces.

  • EDM characterization: An EDM is characterized by the positive-semidefiniteness of its centered Gram matrix, with the centering constraint enforcing zero column sums.The centered Gramian lies in a reduced geometrically centered cone.
  • Rank-constrained formulation: Embedding dimension d can be enforced by constraining the centered Gram matrix to have rank at most d.Thus, rank and definiteness jointly characterize EDMs for a specified dimension.
  • Relaxations: The rank-constrained semidefinite program is non-convex, so omitting the rank constraint yields a tractable semidefinite relaxation.The relaxed feasible set is the full semidefinite cone after a reduced-dimensional transformation.
  • Reduced formulation: The reduced Gram matrix removes the implicit nullspace constraint G1 = 0 and can improve numerical stability for optimization methods.The transformation uses an orthonormal basis for the subspace orthogonal to the all-ones vector.
  • Limitations: Omitting the rank constraint can yield a higher-dimensional completion even when a completion exists in the target dimension.This is the principal dimensionality caveat of the semidefinite relaxation.
  • Rank promotion: Maximizing the trace promotes lower-rank solutions by stretching the point configuration subject to the available distance information.Distance bounds can be added as linear constraints while preserving convexity.

D. Multidimensional Unfolding: A Special Case of Completion

Multidimensional unfolding treats cross-distances between two point subsets as a structured EDM completion problem. The paper reformulates microphone calibration this way, reducing the geometric reconstruction to matrix-completion algorithms while noting that some sensor-network methods are poorly matched to its missing-entry pattern.

  • Problem setup: Metric multidimensional unfolding is EDM completion when distances are known between two subsets but missing within each subset.The missing entries therefore occupy the two diagonal blocks of the distance matrix.
  • Problem setup: Microphone calibration uses distances from m unknown microphones to k unknown synchronized acoustic sources, producing the MDU block structure.The microphones and sources can be ordered so the unknown within-group distances form diagonal blocks.
  • Geometric derivation: After double centering the cross-distance matrix, the result is a matrix of inner products between separately centered microphone and source coordinates.The two centered point sets generally use different coordinate systems and have noncoincident centroids.
  • Geometric derivation: Factoring the centered cross-Gram matrix introduces an invertible transformation, and in 3D the remaining consistency problem requires only ten scalars.The parameters are determined by enforcing consistency with the measured cross-distances.
  • EDM completion formulation: MDU can be solved as structured matrix completion by constructing a mask and applying the semidefinite relaxation or other EDM completion algorithms.This replaces the more convoluted direct geometric procedure with a general EDM-toolbox formulation.
  • Algorithmic comparison: Sensor-network-localization algorithms tailored to limited-range communication do not perform well on MDU because its missing-entry structure is opposite to theirs.This limitation concerns algorithmic fit to the observation pattern rather than EDM completion in general.

E. Performance Comparison of Algorithms

The experiments compare EDM algorithms under random versus structured missing entries and varying noise. SDR is broadly robust, while scalability and missing-entry structure determine which faster methods are preferable.

  • Experimental settings: The experiments evaluate algorithms under uniformly random deletions and deterministic block-structured missing entries in multidimensional unfolding.Success rate is measured for exact observed entries, while noisy experiments report mean relative Frobenius error across jitter levels.
  • Algorithm performance: OptSpace performs worst for randomly deleted entries when n = 20, but becomes fast and attractive for large matrices with randomly scattered missing entries.Its intended regime is larger n; the ultrasonic calibration example used n = 200 or more, with thousands or tens of thousands preferred for full benefit.
  • Algorithm performance: SDR achieves the highest success rate in both random-deletion and MDU settings and behaves well under noise.Alternating coordinate descent can perform slightly better under some noisy conditions, but may produce large errors for particular point configurations.
  • Limitations: SDR is the slowest tested algorithm, and for n = 1000 the CVX implementation runs out of desktop memory or essentially never finishes.Alternating coordinate descent, rank alternation, and OptSpace have much faster Matlab implementations.
  • Practical choices: Crocco’s microphone-calibration algorithm performs equally well for any number of acoustic events and is attractive when calibration events are few.Its reduction to ten unknowns may explain this behavior, and multiple random initializations can further improve success rate.
  • Algorithm performance: Rank alternation worsens as acoustic events increase at low noise because structured unknown blocks grow while known entries in event-associated rows and columns decrease.The method uses matrix rank without exploiting the geometrical meaning of the entries.
  • Practical choices: For smaller matrices SDR is recommended overall, whereas alternating coordinate descent, rank alternation, or OptSpace are alternatives as matrix size increases.OptSpace is most attractive for matrices with n on the order of thousands or tens of thousands; detailed runtime comparisons were deliberately omitted.

F. Summary

The paper summarizes EDM methods spanning completion, multidimensional unfolding, semidefinite relaxations, and stress-based optimization. Their performance is assessed under both random and deterministic missing-entry structures.

  • EDM completion and denoising: The paper formulates EDM completion and denoising and exploits the EDM rank property through a rank-based completion algorithm.
  • Multidimensional scaling: It presents raw stress and s-stress as standard MDS objectives and gives a simple algorithm for minimizing s-stress.
  • Semidefinite methods: It develops semidefinite relaxations that exploit the connection between EDMs and positive semidefinite matrices.
  • Multidimensional unfolding: It explains multidimensional unfolding and solves it efficiently through EDM completion.
  • Evaluation: The algorithms are evaluated with randomly unobserved entries and with deterministic block-structured unobserved entries in MDU.

IV. UNLABELED DISTANCES

Unlabeled-distance problems require recovering both a point configuration and the correspondence between distances and point pairs. EDM consistency supports feasible searches in applications including room reconstruction and sparse phase retrieval.

  • Problem setting: Unlabeled-distance data provide all or some distances without identifying which point pair produced each measurement.The task is to arrange the distances into a realizable EDM.
  • Computational limitation: No efficient algorithm is known for localization from unlabeled distances in the general noisy case.A polynomial-time algorithm exists for relatively large point sets with unordered, noiseless distances, albeit with high degree.
  • Label recovery: Exhaustive assignment search can be feasible when the number of candidate labelings is sufficiently small, using EDM constraints to select the best labeling.
  • Identifiability: For independently sampled points, the configuration is almost surely unique up to a rigid transformation given its unlabeled distances.This uniqueness does not itself provide an efficient method for finding the correct labeling.
  • Sparse phase retrieval: Sparse phase retrieval exposes unlabeled pairwise support distances through the autocorrelation function, so support recovery reduces to a distance-labeling problem.Correctly labeling those distances permits exact support recovery under the stated setup.
  • Room reconstruction: Room reconstruction from echoes treats reflected signals as distances to image sources, but requires sorting unlabeled peaks across microphone impulse responses.The image-source model links echoes to room geometry, and first-order image sources determine a convex planar-walled room.
  • Room reconstruction: An incremental algorithm grows a microphone EDM by selecting one echo from each impulse response and testing the augmented matrix for EDM consistency.
  • Room reconstruction: Room reconstruction achieved centimeter precision with one loudspeaker and an array of five microphones.

B. Summary

The tutorial summarizes EDM applications and contributions, while identifying unresolved problems in manifold distances, projections, labeling, noise, and s-stress. It concludes that EDMs deserve broader attention, with semidefinite relaxation performing best for ad-hoc microphone array localization.

  • Summary: Most point sets have unique distances, while room reconstruction uses EDMs to robustly filter echoes from the same image source.These properties support reconstruction and echo-labeling tasks.
  • Summary: Sparse phase retrieval can be formulated as a distance problem by interpreting autocorrelation support as distances between deltas.Echo sorting can then be adapted from the EDM perspective.
  • Summary: The paper argues that EDM power and associated algorithms remain insufficiently recognized in signal processing and presents EDMs as a starting reference.It aims to inspire further research and provide practitioners with a useful toolbox.
  • Ideas for future research: Open questions concern EDMs for points on general manifolds and the effects of projecting generating points into lower-dimensional subspaces.These questions are connected to machine learning, X-ray crystallography, and seismic imaging.
  • Ideas for future research: Efficient labeling remains difficult without application-specific heuristics, especially for incomplete or noisy unlabeled distances.Further questions include reconstruction-error distributions and whether incorrect assignments can occur with positive probability.
  • Conclusion: No analytical minimum of s-stress had yet been found, while semidefinite relaxation was reported as the best-performing algorithm for ad-hoc microphone array localization.The conclusion suggests that solving the labeling problem could fuel future progress.
Loading 1502.07541v2…