Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness

Abstract

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-<inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> matrices locally converges linearly with high probability when the sampling probability satisfies <inline-formula> <tex-math notation="LaTeX">$p\geq {\mathcal {O}} (\nu ^{2} r^{2}\log (n)/n)$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$\nu $ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$p \geq {\mathcal {O}} (\nu r^{3/2}\log ^{3/4}(n)/n^{1/4})$ </tex-math></inline-formula>. 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 analysis of a second order degenerate U-statistic 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. Due to space constraints, the complete proofs of the convergence bounds and technical lemmas are provided in the extended pre-print 2508.00091, and the appendices containing said results are also available online at IEEE Xplore.