The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
Euclidean Distance Matrices: Essential theory, algorithms, and applications
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Global Geometric Framework for Nonlinear Dimensionality Reduction
Tenenbaum, J. B., Silva, V. D., & Langford, J. C. (2000) · Science · doi:10.1126/science.290.5500.2319 · Cited by 13,585
Multidimensional Scaling by Optimizing Goodness of Fit to a Nonmetric Hypothesis
Kruskal, J. B. (1964) · Psychometrika · doi:10.1007/bf02289565 · Cited by 7,317
Nonmetric Multidimensional Scaling: A Numerical Method
Kruskal, J. B. (1964) · Psychometrika · doi:10.1007/bf02289694 · Cited by 4,846
Protein Structure Comparison by Alignment of Distance Matrices
Holm, L., & Sander, C. (1993) · Journal of Molecular Biology · doi:10.1006/jmbi.1993.1489 · Cited by 3,984
Image method for efficiently simulating small-room acoustics
Allen, J. B., & Berkley, D. A. (1979) · The Journal of the Acoustical Society of America · doi:10.1121/1.382599 · Cited by 3,742
Locating the nodes: cooperative localization in wireless sensor networks
Patwari, N., Ash, J. N., Kyperountas, S., Hero, A. O., Moses, R. L., & Correal, N. S. (2005) · IEEE Signal Processing Magazine · doi:10.1109/msp.2005.1458287 · Cited by 3,031
Graph Implementations for Nonsmooth Convex Programs
Grant, M. C., & Boyd, S. P. (2007) · Lecture Notes in Control and Information Sciences · doi:10.1007/978-1-84800-155-8_7 · Cited by 2,666
Modern Multidimensional Scaling: Theory and Applications
Borg, I., & Groenen, P. (2003) · Journal of Educational Measurement · doi:10.1111/j.1745-3984.2003.tb01108.x · Cited by 2,197
Multidimensional Scaling: I. Theory and Method
Torgerson, W. S. (1952) · Psychometrika · doi:10.1007/bf02288916 · Cited by 2,126
Convex position estimation in wireless sensor networks
Doherty, L., pister, K. S. J., & El Ghaoui, L. (2002) · Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213) · doi:10.1109/infcom.2001.916662 · Cited by 1,632
Guttman, L. (1968) · Psychometrika · doi:10.1007/bf02290164 · Cited by 1,343
Modern Multidimensional Scaling: Theory and Applications
O'Connell, A. A., Borg, I., & Groenen, P. (1999) · Journal of the American Statistical Association · doi:10.2307/2669710 · Cited by 1,048
Theory and Applications of Distance Geometry
Blumenthal, L. M. (1970) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,003
Matrix Completion From a Few Entries
Keshavan, R. H., Montanari, A., & Oh, S. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2046205 · Cited by 974
Takane, Y., Young, F. W., & de Leeuw, J. (1977) · Psychometrika · doi:10.1007/bf02293745 · Cited by 947
Discussion of a Set of Points in Terms of their Mutual Distances
Young, G., & Householder, A. S. (1938) · Psychometrika · doi:10.1007/bf02287916 · Cited by 753
Phase retrieval in crystallography and optics
Millane, R. P. (1990) · Journal of the Optical Society of America A · doi:10.1364/josaa.7.000394 · Cited by 720
Unsupervised Learning of Image Manifolds by Semidefinite Programming
Weinberger, K. Q., & Saul, L. K. (2006) · International Journal of Computer Vision · doi:10.1007/s11263-005-4939-z · Cited by 692
Matrix completion from a few entries
Keshavan, R. H., Oh, S., & Montanari, A. (2009) · 2009 IEEE International Symposium on Information Theory · doi:10.1109/isit.2009.5205567 · Cited by 650
Semidefinite programming for ad hoc wireless sensor network localization
Biswas, P., & Ye, Y. (2004) · Proceedings of the 3rd international symposium on Information processing in sensor networks · doi:10.1145/984622.984630 · Cited by 573
Euclidean Distance Geometry and Applications
Liberti, L., Lavor, C., Maculan, N., & Mucherino, A. (2014) · SIAM Review · doi:10.1137/120875909 · Cited by 523
Schoenberg, I. J. (1935) · The Annals of Mathematics · doi:10.2307/1968654 · Cited by 453
Semidefinite Programming Approaches for Sensor Network Localization With Noisy Distance Measurements
Biswas, P., Liang, T.-C., Toh, K.-C., Ye, Y., & Wang, T.-C. (2006) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2006.877401 · Cited by 451
Havel, T. F., & Wüthrich, K. (1985) · Journal of Molecular Biology · doi:10.1016/0022-2836(85)90346-8 · Cited by 378
Applications of Convex Analysis to Multidimensional Scaling
de Leeuw, J. (2000) · eScholarship (California Digital Library) · Cited by 326
Theory of semidefinite programming for Sensor Network Localization
So, A. M.-C., & Ye, Y. (2007) · Mathematical Programming · doi:10.1007/s10107-006-0040-1 · Cited by 326
Acoustic echoes reveal room shape
Dokmanić, I., Parhizkar, R., Walther, A., Lu, Y. M., & Vetterli, M. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1221464110 · Cited by 249
Self-citationMatrix Completion from Noisy Entries
Keshavan, R. H., Andrea Montanari, A., & Oh, S. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0906.2027 · Cited by 202
A Bilinear Approach to the Position Self-Calibration of Multiple Sensors
Crocco, M., Bue, A. D., & Murino, V. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2175387 · Cited by 121
Euclidean Distance Matrices and Applications
Krislock, N., & Wolkowicz, H. (2011) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4614-0769-0_30 · Cited by 110
On reconstructing n-point configurations from the distribution of distances or areas
Boutin, M., & Kemper, G. (2003) · Advances in Applied Mathematics · doi:10.1016/s0196-8858(03)00101-5 · Cited by 90
Direct computation of sound and microphone locations from time-difference-of-arrival data
Pollefeys, M., & Nistér, D. (2008) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2008.4518142 · Cited by 90
Distance Geometry : Theory, Methods, and Applications
Mucherino, A., Lavor, C., Liberti, L., & Maculan, N. (2013) · HAL · doi:10.1007/978-1-4614-5128-0 · Cited by 74
Phase Retrieval for Sparse Signals: Uniqueness ConditionsPreprint
Ranieri, J., Chebira, A., Lu, Y. M., & Vetterli, M. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1308.3058 · Cited by 57
Self-citation
Cited by
Ahmad, G. N., Fatima, H., Ullah, S., Salah Saidi, A., & Imdadullah (2022) · IEEE Access · doi:10.1109/access.2022.3165792 · Cited by 289
LLMatic: Neural Architecture Search Via Large Language Models And Quality Diversity Optimization
Nasir, M. U., Earle, S., Togelius, J., James, S., & Cleghorn, C. (2024) · Proceedings of the Genetic and Evolutionary Computation Conference · doi:10.1145/3638529.3654017 · Cited by 52
Massive CSI Acquisition for Dense Cloud-RANs With Spatial-Temporal Dynamics
Liu, X., Shi, Y., Zhang, J., & Letaief, K. B. (2018) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2018.2797969 · Cited by 11
Mapping Single-Molecule Protein Complexes in 3D with DNA Nanoswitch Calipers
(2023) · doi:10.1021/jacs.3c10262 · Cited by 5
Metadata
- Authors
- Dokmanic, I., Parhizkar, R., Ranieri, J., & Vetterli, M.
- Venue
- IEEE Signal Processing Magazine
- Published
- 2015-11
- Volume
- 32
- Issue
- 6
- Pages
- 12-30
- ISSN
- 1053-5888 (ISSN-L)
- OpenAlex
- W1898843043
- Cited by
- 611
- References
- 34
- FWCI
- 24.68
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.