@inproceedings{
ghosh2024sampleefficient,
title={Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization},
author={Ipsita Ghosh and Abiy Tasissa and Christian K{\"u}mmerle},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=Yu7H8ZOuI2}
}
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-$r$ 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 \href{https://github.com/ipsita-ghosh-1/EDG-IRLS}{github\_SEGRED}
Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization
Ipsita Ghosh Abiy Tasissa Christian Kümmerle