Abiy Tasissa, Tufts University

Title: From missing distances to structures: Theory, algorithms and applications

Abstract: The advancement of technology has significantly enhanced our capacity to collect data. However, in many real-world applications, certain inherent limitations—such as the precision of measurement devices, environmental conditions, or operating costs—can result in missing data. In this talk, we focus on the setting where the available data consist of pairwise distances between a set of points, with the goal of estimating the configuration of the underlying points from incomplete distance measurements. This is known as the Euclidean distance geometry (EDG) problem and is central to many applications.

We first start by describing the solution when all distances are given using the classical multidimensional scaling (MDS) technique and then discuss a constructive approach to interpret the key mathematical objects in MDS. Next, we introduce a mathematical framework to address the EDG problem under two sampling models of the distance matrix: global sampling (uniform sampling of the entries of the distance matrix) and structured local sampling, where the measurements are limited to a subset of rows and columns. We discuss the conditions required for the exact recovery of the point configuration and the associated algorithms. The last part of the talk will illustrate the algorithms using synthetic and real data and discuss ongoing work.