publications

2025

1. Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness (submitted)

   Chandler Smith, HanQin Cai, and Abiy Tasissa

   2025

   Abs PDF Website

   The problem of recovering the configuration of points from their partial pairwise distances, referred to as the Euclidean Distance Matrix Completion (EDMC) problem, arises in a broad range of applications, including sensor network localization, molecular conformation, and manifold learning. In this paper, we propose a Riemannian optimization framework for solving the EDMC problem by formulating it as a low-rank matrix completion task over the space of positive semi-definite Gram matrices. The available distance measurements are encoded as expansion coefficients in a non-orthogonal basis, and optimization over the Gram matrix implicitly enforces geometric consistency through nonnegativity and the triangle inequality, a structure inherited from classical multidimensional scaling. Under a Bernoulli sampling model for observed distances, we prove that Riemannian gradient descent on the manifold of rank-r matrices locally converges linearly with high probability when the sampling probability satisfies $p≥O(ν^2 r^2\log(n)/n), where νis an EDMC-specific incoherence parameter. Furthermore, we provide an initialization candidate using a one-step hard thresholding procedure that yields convergence, provided the sampling probability satisfies p ≥O(νr^3/2\log^3/4(n)/n^1/4)$. A key technical contribution of this work is the analysis of a symmetric linear operator arising from a dual basis expansion in the non-orthogonal basis, which requires a novel application of the Hanson-Wright inequality to establish an optimal restricted isometry property in the presence of coupled terms. Empirical evaluations on synthetic data demonstrate that our algorithm achieves competitive performance relative to state-of-the-art methods. Moreover, we provide a geometric interpretation of matrix incoherence tailored to the EDMC setting and provide robustness guarantees for our method.

2. Provable Convergence of Non-Uniform Sampling Models for Arbitrarily Poor Geometries in the Euclidean Distance Geometry Problem (in preparation)

   Chandler Smith, and Abiy Tasissa

   2025

2024

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

   Chandler Smith, Hanqin Cai, and Abiy Tasissa

   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.