Euclidean Distance Matrices : Properties, Algorithms and Applications

Euclidean distance matrices (EDMs) are central players in many diverse fields including psychometrics, NMR spectroscopy, machine learning and sensor networks. However, they are not often exploited in signal processing. In this thesis, we analyze attributes of EDMs and derive new key properties of them. These analyses allow us to propose algorithms to approximate EDMs and provide analytic bounds on the performance of our methods. We use these techniques to suggest new solutions for several practical problems in signal processing. Together with these properties, algorithms and applications, EDMs can thus be considered as a fundamental toolbox to be used in signal processing. In more detail, we start by introducing the structure and properties of EDMs. In particular, we focus on their rank property; the rank of an EDM is at most the dimension of the set of points generating it plus 2. Using this property, we introduce the use of low rank matrix completion methods for approximating and completing noisy and partially revealed EDMs. We apply this algorithm to the problem of sensor position calibration in ultrasound tomography devices. By adapting the matrix completion framework, in addition to proposing a self calibration process for these devices, we also provide analytic bounds for the calibration error. We then study the problem of sensor localization using distance information by minimizing a non-linear cost function known as the s-stress function in the multidimensional scaling (MDS) community. We derive key properties of this cost function that can be used to reduce the search domain for finding its global minimum. We provide an efficient, low cost and distributed algorithm for minimizing this cost function for incomplete networks and noisy measurements. In randomized experiments, the proposed method converges to the global minimum of the s-stress in more than 99% of the cases. We also address the open problem of existence of non-global minimizers of the s-stress and reduce this problem to a hypothesis. If the hypothesis is true then the cost function has only global minimizers, otherwise, it has non-global minimizers. Using the rank property of EDMs and the proposed minimization algorithm for approximating them, we address an interesting and practical problem in acoustics. We show that using five microphones and one loudspeaker, we can hear the shape of a room. We reformulate this problem as finding the locations of the image sources of the loudspeaker with respect to the walls. We propose an algorithm to find these positions only using first-order echoes. We prove that the reconstruction of the room is almost surely unique. We further introduce a new algorithm for locating a microphone inside a known room using only one loudspeaker. Our experimental evaluations conducted on the EPFL campus and also in the Lausanne cathedral, confirm the robustness and accuracy of the proposed methods. By integrating further properties of EDMs into the matrix co