More Like this

1. Riemannian Optimization for Euclidean Distance Geometry

   Smith, Chander; Lichtenberg, Samuel; Cai, HanQin; Tasissa, Abiy (October 2023, OPT2023: 15th Annual Workshop on Optimization for Machine Learning)

   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 distances. 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. 

   more » « less
2. Sample-efficient geometry reconstruction from euclidean distances using non-convex optimization

   Ghosh, Ipsita; Tasissa, Abiy; Kümmerle, Christian (December 2024, Neural Information Processing Systems Foundation, Inc. (NeurIPS))

   The problem of finding suitable point embedding or geometric configurations given only Euclidean distance information of point pairs arises both as a core task and as a sub-problem in a variety of machine learning applications. In this paper, we aim to solve this problem given a minimal number of distance samples. To this end, we leverage continuous and non-convex rank minimization formulations of the problem and establish a local convergence guarantee for a variant of iteratively reweighted least squares (IRLS), which applies if a minimal random set of observed distances is provided. As a technical tool, we establish a restricted isometry property (RIP) restricted to a tangent space of the manifold of symmetric rank- matrices given random Euclidean distance measurements, which might be of independent interest for the analysis of other non-convex approaches. Furthermore, we assess data efficiency, scalability and generalizability of different reconstruction algorithms through numerical experiments with simulated data as well as real-world data, demonstrating the proposed algorithm's ability to identify the underlying geometry from fewer distance samples compared to the state-of-the-art. The Matlab code can be found at https://github.com/ipsita-ghosh-1/EDG-IRLS. 

   more » « less
3. A dual basis approach to multidimensional scaling

   https://doi.org/10.1016/j.laa.2023.11.004  

   Lichtenberg, Samuel; Tasissa, Abiy (February 2024, Linear Algebra and its Applications)

   Classical multidimensional scaling (CMDS) is a technique that embeds a set of objects in a Euclidean space given their pairwise Euclidean distances. The main part of CMDS involves double centering a squared distance matrix and using a truncated eigendecomposition to recover the point coordinates. In this paper, motivated by a study in Euclidean distance geometry, we explore a dual basis approach to CMDS. We give an explicit formula for the dual basis vectors and fully characterize the spectrum of an essential matrix in the dual basis framework. We make connections to a related problem in metric nearness. 

   more » « less
4. Sharp analysis of EM for learning mixtures of pairwise differences

   Dhawan, Abhishek; Mao, Cheng; Pananjady, Ashwin (July 2023, Proceedings of Thirty Sixth Conference on Learning Theory)

   We consider a symmetric mixture of linear regressions with random samples from the pairwise comparison design, which can be seen as a noisy version of a type of Euclidean distance geometry problem. We analyze the expectation-maximization (EM) algorithm locally around the ground truth and establish that the sequence converges linearly, providing an $$\ell_\infty$$-norm guarantee on the estimation error of the iterates. Furthermore, we show that the limit of the EM sequence achieves the sharp rate of estimation in the $$\ell_2$$-norm, matching the information-theoretically optimal constant. We also argue through simulation that convergence from a random initialization is much more delicate in this setting, and does not appear to occur in general. Our results show that the EM algorithm can exhibit several unique behaviors when the covariate distribution is suitably structured. 

   more » « less
5. Geometric Invariants for Sparse Unknown View Tomography

   https://doi.org/10.1109/ICASSP.2019.8682401  

   Zehni, Mona; Huang, Shuai; Dokmanic, Ivan; Zhao, Zhizhen (April 2019, ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   In this paper, we study a 2D tomography problem for point source models with random unknown view angles. Rather than recovering the projection angles, we reconstruct the model through a set of rotation-invariant features that are estimated from the projection data. For a point source model, we show that these features reveal geometric information about the model such as the radial and pairwise distances. This establishes a connection between unknown view tomography and unassigned distance geometry problem (uDGP). We propose new methods to extract the distances and approximate the pairwise distance distribution of the underlying points. We then use the recovered distribution to estimate the locations of the points through constrained non-convex optimization. Our simulation results show that our point source reconstruction pipeline is robust to noise and outperforms the regularized expectation maximization (EM) baseline. 

   more » « less