Denoising and completion of Euclidean distance matrix from multiple observations

Abstract

For a point set, Euclidean distance matrix (EDM) is the matrix consisting of squared distances between every pair of points in the set. It frequently appears in wide ranging applications such as sensor networks, acoustic arrays, crystallography, and self localization among others. Often the measured EDM are inaccurate (due to noise) and incomplete (due to limited availability of measurements) requiring denoising and completion algorithms, frequently both. We focus on two methods from the literature: the first one is the Rank Alternation algorithm, which is based on the rank property of EDM, and the second one is the Semi-definite Relaxation (SDR) algorithm, which hinges on the mapping between EDMs and Gram matrices. Both have demonstrated success, albeit confined to handling single noisy and/or incomplete input EDM. In this thesis we propose extensions of these two algorithms which can process multiple noisy and incomplete EDM simultaneously. We verified this through simulations where we varied multiple parameters such as the number of points, the number of EDM inputs, Signal-to-Noise Ratio (SNR) value, amount of missing entries, and noise types such as zero-mean Uniform noise, zero-mean Gaussian noise, and zero-mean Laplacian noise. Simulations show that the proposed joint algorithms (which process multiple EDM) outperform the corresponding individual algorithms (which process individual EDM and combine the results).