Master's Thesis
Euclidean Distance Matrix Completion and Related Problems
— 2024
Key information
Authors:
Supervisors:
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:
David Silveira de Sousa
ist192624
Supervisors of this institution:
Lina Maria Mateus de Oliveira
ist12383
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