Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent

2025/04/28 by Yicheng Li, Xinghua Sun, Li, Yicheng +1
Computer Science · Engineering · Mathematics · #Bernoulli's principle #Curvature #Euclidean space #FOS: Computer and information sciences #FOS: Electrical engineering #Gradient descent #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Manifold (fluid mechanics) #Matrix (chemical analysis) #Matrix completion #Numerical methods in inverse problems #Random matrix #Restricted isometry property #Signal Processing (eess.SP) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Stochastic gradient descent #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.2504.19530

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2025/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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 O(μ² r³ κ² 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.

Citations

• Sensor network localization has a benign landscape after low-dimensional relaxation
• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees
• Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion
• Localization from structured distance matrices via low-rank matrix recovery
• A Riemannian Dimension-reduced Second Order Method with Application in Sensor Network Localization
• A dual basis approach to multidimensional scaling
• Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion
• Distance Geometry and Data Science
• A State-of-the-Art Survey on Multidimensional Scaling Based Localization\n Techniques
• Low-rank Matrix Completion in a General Non-orthogonal Basis
• Blind Deconvolution using Modulated Inputs
• Kinetic Euclidean Distance Matrices
• Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion
• Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA
• Spectral Compressed Sensing via Projected Gradient Descent
• Blind Demixing and Deconvolution at Near-Optimal Rate
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Matrix Completion has No Spurious Local Minimum
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• Recovery guarantee of weighted low-rank approximation via alternating minimization
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Euclidean Distance Matrices: Essential Theory, Algorithms and Applications
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Universal Matrix Completion
• Coherence and sufficient sampling densities for reconstruction in compressed sensing
• The Algebraic Combinatorial Approach for Low-Rank Matrix Completion
• Suprema of Chaos Processes and the Restricted Isometry Property
• Euclidean Distance Geometry and Applications
• Robust Localization from Incomplete Local Information
• User-Friendly Tail Bounds for Sums of Random Matrices
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Guaranteed Rank Minimization via Singular Value Projection
• Matrix Completion from a Few Entries
• Exact Matrix Completion via Convex Optimization
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

Related

• Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness
• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees
• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization
• Euclidean distance matrix completion and point configurations from the minimal spanning tree
• Convex Optimization Learning of Faithful Euclidean Distance Representations in Nonlinear Dimensionality Reduction