Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent
This addresses the problem of reconstructing point sets from partial distance measurements for applications like sensor network localization, but it is incremental as it builds on existing gradient-type methods with new theoretical guarantees.
The paper tackles the Euclidean Distance Matrix Completion (EDMC) problem by proposing the Asymmetric Projected Gradient Descent (APGD) algorithm, achieving global convergence with exact recovery given O(μ²r³κ²n log n) random observations and demonstrating exact linear convergence in rich-sample regions but rapid deterioration with limited samples.
This paper proposes and analyzes a gradient-type algorithm based on Burer-Monteiro factorization, called the Asymmetric Projected Gradient Descent (APGD), for reconstructing the point set configuration from partial Euclidean distance measurements, known as the Euclidean Distance Matrix Completion (EDMC) problem. By paralleling the incoherence matrix completion framework, we show for the first time that global convergence guarantee with exact recovery of this routine can be established given $\mathcal{O}(μ^2 r^3 κ^2 n \log n)$ Bernoulli random observations without any sample splitting. Unlike leveraging the tangent space Restricted Isometry Property (RIP) and local curvature of the low-rank embedding manifold in some very recent works, our proof provides extra upper bounds that act as analogies of the random graph lemma under EDMC setting. The APGD works surprisingly well and numerical experiments demonstrate exact linear convergence behavior in rich-sample regions yet deteriorates rapidly when compared with the performance obtained by optimizing the s-stress function, i.e., the standard but unexplained non-convex approach for EDMC, if the sample size is limited. While virtually matching our theoretical prediction, this unusual phenomenon might indicate that: (i) the power of implicit regularization is weakened when specified in the APGD case; (ii) the stabilization of such new gradient direction requires substantially more samples than the information-theoretic limit would suggest.