Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent
Preprint
Abstract
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}(\mu^2 r^3 \kappa^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 new upper bounds to replace 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 fast 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.
Keywords
All Related Versions
This publication has 47 references indexed in Scilit:
- Low-rank matrix completion in a general non-orthogonal basisLinear Algebra and its Applications, 2021
- Distance geometry and data scienceTOP, 2020
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind DeconvolutionFoundations of Computational Mathematics, 2019
- Gradient descent with random initialization: fast global convergence for nonconvex phase retrievalMathematical Programming, 2019
- Suprema of Chaos Processes and the Restricted Isometry PropertyCommunications on Pure and Applied Mathematics, 2014
- Localization from Incomplete Noisy Distance MeasurementsFoundations of Computational Mathematics, 2012
- User-Friendly Tail Bounds for Sums of Random MatricesFoundations of Computational Mathematics, 2011
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- Conformational analysis by energy embeddingJournal of Computational Chemistry, 1982
- Nonmetric Individual Differences Multidimensional Scaling: An Alternating Least Squares Method with Optimal Scaling FeaturesPsychometrika, 1977