Master's Thesis

Euclidean Distance Matrix Completion and Related Problems

David Silveira de Sousa — 2024

Key information

Authors:

David Silveira de Sousa (David Silveira de Sousa)

Supervisors:

Lina Maria Mateus de Oliveira (Lina Maria Mateus de Oliveira); Maria do Rosário De Oliveira Silva (Maria do Rosário De Oliveira Silva)

Published in

July 15, 2024

Abstract

This thesis explores the challenges and methodologies involved in the completion of Euclidean Distance Matrices (EDMs) and the reconstruction of point configurations from incomplete and noisy data. We extend the classical theorem for EDM completion, which originally addressed a single missing entry, to accommodate multiple missing entries within a single column. This generalization is crucial for practical applications where multiple distances might be missing due to various limitations such as sensor range or data corruption. We delve into the theoretical aspects of the Wasserstein distance for interval data and demonstrate its representation as a Euclidean metric, allowing the application of classical EDM techniques to a broader class of interval data. Various algorithms for EDM completion are reviewed and extended, including rank-based methods, OptScape, and multidimensional scaling. Through extensive simulations, we evaluate the performance of these algorithms under different conditions of noise levels. For the chosen algorithm we demonstrate the robustness of clustering and data integrity preservation even with significant data omissions. The findings have significant implications for fields requiring robust distance matrix completions, such as sensor network localization, protein structure determination, and data visualization.

Publication details

Authors in the community:

Supervisors of this institution:

Fields of Science and Technology (FOS)

mathematics - Mathematics

Publication language (ISO code)

por - Portuguese

Rights type:

Embargo lifted

Date available:

April 28, 2025

Institution name

Instituto Superior Técnico