Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent

• URL: http://arxiv.org/abs/2504.19530v1
• Date: Mon, 28 Apr 2025 07:13:23 GMT
• Title: Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent
• Authors: Yicheng Li, Xinghua Sun,
• Abstract summary: This paper proposes and analyzes a gradient-type algorithm based on Burer-Monteiro factorization, called the Asymmetric Descented Gradient (APGD)
• Score: 13.27202712518471
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization [7.114174944371803]
  The problem of finding suitable point embedding Euclidean distance information point pairs arises both as a core task and as a sub-machine learning learning problem. In this paper, we aim to solve this problem given a minimal number of samples.
  arXiv  Detail & Related papers  (2024-10-22T13:02:12Z)
• Asymptotics of Stochastic Gradient Descent with Dropout Regularization in Linear Models [8.555650549124818]
  This paper proposes a theory for online inference of the gradient descent (SGD) iterates with dropout regularization in linear regression. For sufficiently large samples, the proposed confidence intervals for ASGD with dropout nearly achieve the nominal coverage probability.
  arXiv  Detail & Related papers  (2024-09-11T17:28:38Z)
• Intrinsic Bayesian Cramér-Rao Bound with an Application to Covariance Matrix Estimation [49.67011673289242]
  This paper presents a new performance bound for estimation problems where the parameter to estimate lies in a smooth manifold. It induces a geometry for the parameter manifold, as well as an intrinsic notion of the estimation error measure.
  arXiv  Detail & Related papers  (2023-11-08T15:17:13Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Orthogonal Matrix Retrieval with Spatial Consensus for 3D Unknown-View Tomography [58.60249163402822]
  Unknown-view tomography (UVT) reconstructs a 3D density map from its 2D projections at unknown, random orientations. The proposed OMR is more robust and performs significantly better than the previous state-of-the-art OMR approach.
  arXiv  Detail & Related papers  (2022-07-06T21:40:59Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent [22.851500417035947]
  Factorization-based gradient descent is a scalable and efficient algorithm for solving the factorrank matrix completion. We show that gradient descent enjoys fast convergence to estimate a solution of the global nature problem.
  arXiv  Detail & Related papers  (2021-02-04T03:41:54Z)
• Sparse Representations of Positive Functions via First and Second-Order Pseudo-Mirror Descent [15.340540198612823]
  We consider expected risk problems when the range of the estimator is required to be nonnegative. We develop first and second-order variants of approximation mirror descent employing emphpseudo-gradients. Experiments demonstrate favorable performance on ingeneous Process intensity estimation in practice.
  arXiv  Detail & Related papers  (2020-11-13T21:54:28Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.