publications

2024

1. Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees (submitted)

   Chandler Smith, Hanqin Cai, and Abiy Tasissa

   IEEE Transactions on Information Theory, 2024

   Abs PDF Website

   The problem of determining the configuration of points from partial distance information, known as the Euclidean Distance Geometry (EDG) problem, is fundamental to many tasks in the applied sciences. In this paper, we propose two algorithms grounded in the Riemannian optimization framework to address the EDG problem. Our approach formulates the problem as a low-rank matrix completion task over the Gram matrix, using partial measurements represented as expansion coefficients of the Gram matrix in a non-orthogonal basis. For the first algorithm, under a uniform sampling with replacement model for the observed distance entries, we demonstrate that, with high probability, a Riemannian gradient-like algorithm on the manifold of rank-r matrices converges linearly to the true solution, given initialization via a one-step hard thresholding. This holds provided the number of samples, m, satisfies m ≥O(n^(7/4)r^2 log(n)). With a more refined initialization, achieved through resampled Riemannian gradient-like descent, we further improve this bound to m ≥O(nr^2 log(n)). Our analysis for the first algorithm leverages a non-self-adjoint operator and depends on deriving eigenvalue bounds for an inner product matrix of restricted basis matrices, leveraging sparsity properties for tighter guarantees than previously established. The second algorithm introduces a self-adjoint surrogate for the sampling operator. This algorithm demonstrates strong numerical performance on both synthetic and real data. Furthermore, we show that optimizing over manifolds of higher-than-rank-r matrices yields superior numerical results, consistent with recent literature on overparameterization in the EDG problem.

2023

1. Riemannian Optimization for Euclidean Distance Geometry

   Chandler Smith, Samuel Lichtenberg, Hanqin Cai, and 1 more author

   In OPT-ML, 2023

   Abs PDF Poster Slides Website

   The Euclidean distance geometry (EDG) problem is a crucial machine learning task that appears in many applications. Utilizing the pairwise Euclidean distance information of a given point set, EDG reconstructs the configuration of the point system. When only partial distance information is available, matrix completion techniques can be incorporated to fill in the missing pairwise dis- tances. In this paper, we propose a novel dual basis Riemannian gradient descent algorithm, coined RieEDG, for the EDG completion problem. The numerical experiments verify the effectiveness of the proposed algorithm. In particular, we show that RieEDG can precisely reconstruct various datasets consisting of 2- and 3-dimensional points by accessing a small fraction of pairwise distance information.