A Dual Basis Approach for Structured Robust Euclidean Distance Geometry

• URL: http://arxiv.org/abs/2505.18414v1
• Date: Fri, 23 May 2025 22:40:21 GMT
• Title: A Dual Basis Approach for Structured Robust Euclidean Distance Geometry
• Authors: Chandra Kundu, Abiy Tasissa, HanQin Cai,
• Abstract summary: This paper considers the setting where only a set of anchor nodes is used to collect the distances between themselves and the rest.<n>In the presence of potential outliers, it results in a structured partial observation on EDM with partial corruptions.<n>We propose a novel algorithmic framework, dubbed Robust Euclidean Distance Geometry via Dual Basis (RoDEoDB) for recovering the Euclidean distance geometry.
• Score: 6.422262171968397
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Euclidean Distance Matrix (EDM), which consists of pairwise squared Euclidean distances of a given point configuration, finds many applications in modern machine learning. This paper considers the setting where only a set of anchor nodes is used to collect the distances between themselves and the rest. In the presence of potential outliers, it results in a structured partial observation on EDM with partial corruptions. Note that an EDM can be connected to a positive semi-definite Gram matrix via a non-orthogonal dual basis. Inspired by recent development of non-orthogonal dual basis in optimization, we propose a novel algorithmic framework, dubbed Robust Euclidean Distance Geometry via Dual Basis (RoDEoDB), for recovering the Euclidean distance geometry, i.e., the underlying point configuration. The exact recovery guarantees have been established in terms of both the Gram matrix and point configuration, under some mild conditions. Empirical experiments show superior performance of RoDEoDB on sensor localization and molecular conformation datasets.

Related papers

• Riemannian Optimization for Distance Geometry: A Study of Convergence, Robustness, and Incoherence [6.422262171968397]
  The Euclidean Distance Geometry (EDG) problem arises in a broad range of applications, including sensor network localization, molecular conformation, and manifold learning.<n>In this paper, we propose a framework for solving the EDG problem by formulating it as a low-rank matrix completion task over the space of positive semi-definite Gram matrices.<n>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 the triangle inequality.
  arXiv  Detail & Related papers  (2025-07-31T18:40:42Z)
• Enforcing Latent Euclidean Geometry in Single-Cell VAEs for Manifold Interpolation [79.27003481818413]
  We introduce FlatVI, a training framework that regularises the latent manifold of discrete-likelihood variational autoencoders towards Euclidean geometry.<n>By encouraging straight lines in the latent space to approximate geodesics on the decoded single-cell manifold, FlatVI enhances compatibility with downstream approaches.
  arXiv  Detail & Related papers  (2025-07-15T23:08:14Z)
• PAID: Pairwise Angular-Invariant Decomposition for Continual Test-Time Adaptation [70.98107766265636]
  This paper takes the geometric attributes of pre-trained weights as a starting point, systematically analyzing three key components: magnitude, absolute angle, and pairwise angular structure.<n>We find that the pairwise angular structure remains stable across diverse corrupted domains and encodes domain-invariant semantic information, suggesting it should be preserved during adaptation.
  arXiv  Detail & Related papers  (2025-06-03T05:18:15Z)
• Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent [13.27202712518471]
  This paper proposes and analyzes a gradient-type algorithm based on Burer-Monteiro factorization, called the Asymmetric Descented Gradient (APGD)
  arXiv  Detail & Related papers  (2025-04-28T07:13:23Z)
• On lower bounds of the density of planar periodic sets without unit distances [55.2480439325792]
  We introduce a novel approach to estimating $m_1(mathbbR2)$ by reformulating the problem as a Maximal Independent Set (MIS) problem on graphs constructed from flat torus.<n>Our experimental results, supported by theoretical justifications of proposed method, demonstrate that for a sufficiently wide range of parameters this approach does not improve the known lower bound.
  arXiv  Detail & Related papers  (2024-11-20T12:07:19Z)
• 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)
• Unleash the Potential of 3D Point Cloud Modeling with A Calibrated Local Geometry-driven Distance Metric [62.365983810610985]
  We propose a novel distance metric called Calibrated Local Geometry Distance (CLGD) CLGD computes the difference between the underlying 3D surfaces calibrated and induced by a set of reference points. As a generic metric, CLGD has the potential to advance 3D point cloud modeling.
  arXiv  Detail & Related papers  (2023-06-01T11:16:20Z)
• A dual basis approach to multidimensional scaling [3.069335774032178]
  CMDS is a technique that embeds objects in a Euclidean space given their pairwise Euclidean distances. We give an explicit formula for the dual basis vectors and fully characterize the spectrum of an essential matrix in the dual basis framework.
  arXiv  Detail & Related papers  (2023-03-10T03:20:03Z)
• Relative Pose from SIFT Features [50.81749304115036]
  We derive a new linear constraint relating the unknown elements of the fundamental matrix and the orientation and scale. The proposed constraint is tested on a number of problems in a synthetic environment and on publicly available real-world datasets on more than 80000 image pairs.
  arXiv  Detail & Related papers  (2022-03-15T14:16:39Z)
• Improving Metric Dimensionality Reduction with Distributed Topology [68.8204255655161]
  DIPOLE is a dimensionality-reduction post-processing step that corrects an initial embedding by minimizing a loss functional with both a local, metric term and a global, topological term. We observe that DIPOLE outperforms popular methods like UMAP, t-SNE, and Isomap on a number of popular datasets.
  arXiv  Detail & Related papers  (2021-06-14T17:19:44Z)
• Matrix factorisation and the interpretation of geodesic distance [6.445605125467574]
  Given a graph or similarity matrix, we consider the problem of recovering a notion of true distance between the nodes. We show that this can be accomplished in two steps: matrix factorisation, followed by nonlinear dimension reduction.
  arXiv  Detail & Related papers  (2021-06-02T16:11:33Z)
• An End-to-End Framework for Molecular Conformation Generation via Bilevel Programming [71.82571553927619]
  We propose an end-to-end solution for molecular conformation prediction called ConfVAE. Specifically, the molecular graph is first encoded in a latent space, and then the 3D structures are generated by solving a principled bilevel optimization program.
  arXiv  Detail & Related papers  (2021-05-15T15:22:29Z)
• A Unifying and Canonical Description of Measure-Preserving Diffusions [60.59592461429012]
  A complete recipe of measure-preserving diffusions in Euclidean space was recently derived unifying several MCMC algorithms into a single framework. We develop a geometric theory that improves and generalises this construction to any manifold.
  arXiv  Detail & Related papers  (2021-05-06T17:36:55Z)

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.