Georgia Institute of Technology College of Sciences

The Euclidean Distance Matrix Completion (EDMC) problem is a foundational problem in engineering, data science, and machine learning. This problem can be simply described by the following question: given partial access to a set of pairwise Euclidean distances between $n$ points in $r$ dimensions, is it possible to reconstruct the set of $n$ points, up to rigid transformations, that generated the pairwise distances? This problem traces back to the 1950s, and its variations are still actively studied in the literature today. Much of the recent research on the EDMC problem relies on low-rank matrix completion techniques, with theoretical guarantees existing for nuclear-norm minimization over the cone of positive semidefinite matrices. These techniques scale poorly for large sets of points, however, so investigation into faster, non-convex surrogates is needed. This talk will discuss a state-of-the-art approach to provably solve this problem under uniform random sampling of pairwise distances using first-order Riemannian optimization techniques. In addition to this, we describe geometric conditions for recovery and provide a characterization of easy- and hard-to-recover point clouds. To solve the problem for hard-to-recover geometries, we provide a geometrically aware sampling scheme that provably recovers any point cloud with state-of-the-art sample complexity.