Structured Sampling for Robust Euclidean Distance Geometry

• URL: http://arxiv.org/abs/2412.10664v2
• Date: Tue, 18 Feb 2025 00:56:08 GMT
• Title: Structured Sampling for Robust Euclidean Distance Geometry
• Authors: Chandra Kundu, Abiy Tasissa, HanQin Cai,
• Abstract summary: This paper addresses the problem of estimating the positions of points from distance measurements corrupted by sparse outliers. We propose a novel algorithm powered by Nystr"om method and robust principal component analysis. Our algorithm achieves accurate recovery with a modest number of anchors, even in the presence of high levels of sparse outliers.
• Score: 6.422262171968397
• License:
• Abstract: This paper addresses the problem of estimating the positions of points from distance measurements corrupted by sparse outliers. Specifically, we consider a setting with two types of nodes: anchor nodes, for which exact distances to each other are known, and target nodes, for which complete but corrupted distance measurements to the anchors are available. To tackle this problem, we propose a novel algorithm powered by Nystr\"om method and robust principal component analysis. Our method is computationally efficient as it processes only a localized subset of the distance matrix and does not require distance measurements between target nodes. Empirical evaluations on synthetic datasets, designed to mimic sensor localization, and on molecular experiments, demonstrate that our algorithm achieves accurate recovery with a modest number of anchors, even in the presence of high levels of sparse outliers.

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)
• SPARE: Symmetrized Point-to-Plane Distance for Robust Non-Rigid Registration [76.40993825836222]
  We propose SPARE, a novel formulation that utilizes a symmetrized point-to-plane distance for robust non-rigid registration. The proposed method greatly improves the accuracy of non-rigid registration problems and maintains relatively high solution efficiency.
  arXiv  Detail & Related papers  (2024-05-30T15:55:04Z)
• A Robust and Efficient Boundary Point Detection Method by Measuring Local Direction Dispersion [0.6906005491572401]
  Boundary points pose a significant challenge to machine learning tasks, including classification, clustering, and dimensionality reduction. We propose a robust and efficient method for detecting boundary points using LoDD (Local Direction) Our results show that LoDD achieves robust detection accuracy in a time manner.
  arXiv  Detail & Related papers  (2023-12-07T06:09:21Z)
• Localization from structured distance matrices via low-rank matrix recovery [3.069335774032178]
  We study the problem of determining the configuration of $n$ points by using their distances to $m$ nodes, referred to as anchor nodes. One sampling scheme is Nystrom sampling, which assumes known distances between the anchors and between the anchors and the $n$ points. We propose a modified version of Nystrom sampling, where the distances from every node to one central node are known, but all other distances are incomplete.
  arXiv  Detail & Related papers  (2023-11-29T20:43:49Z)
• Vanishing Point Estimation in Uncalibrated Images with Prior Gravity Direction [82.72686460985297]
  We tackle the problem of estimating a Manhattan frame. We derive two new 2-line solvers, one of which does not suffer from singularities affecting existing solvers. We also design a new non-minimal method, running on an arbitrary number of lines, to boost the performance in local optimization.
  arXiv  Detail & Related papers  (2023-08-21T13:03:25Z)
• 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)
• Robust Ellipsoid Fitting Using Axial Distance and Combination [15.39157287924673]
  In random sample consensus (RANSAC), the problem of ellipsoid fitting can be formulated as a problem of minimization of point-to-model distance. We propose a novel distance metric called the axial distance, which is converted from the algebraic distance. A novel sample-consensus-based ellipsoid fitting method is proposed by using the combination between the axial distance and Sampson distance.
  arXiv  Detail & Related papers  (2023-04-02T11:52:33Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Information Entropy Initialized Concrete Autoencoder for Optimal Sensor Placement and Reconstruction of Geophysical Fields [58.720142291102135]
  We propose a new approach to the optimal placement of sensors for reconstructing geophysical fields from sparse measurements. We demonstrate our method on the two examples: (a) temperature and (b) salinity fields around the Barents Sea and the Svalbard group of islands. We find out that the obtained optimal sensor locations have clear physical interpretation and correspond to the boundaries between sea currents.
  arXiv  Detail & Related papers  (2022-06-28T12:43:38Z)
• Maximizing Cohesion and Separation in Graph Representation Learning: A Distance-aware Negative Sampling Approach [9.278968846447215]
  Unsupervised graph representation learning (GRL) is to learn a low-dimensional space of node embeddings that reflect the structure of a given unlabeled graph. Existing algorithms for this task rely on negative sampling objectives that maximize the similarity in node embeddings at nearby nodes. We present a novel Distance-aware Negative Sampling (DNS) which maximizes the separation of distant node-pairs.
  arXiv  Detail & Related papers  (2020-07-02T22:40:38Z)
• Robust 6D Object Pose Estimation by Learning RGB-D Features [59.580366107770764]
  We propose a novel discrete-continuous formulation for rotation regression to resolve this local-optimum problem. We uniformly sample rotation anchors in SO(3), and predict a constrained deviation from each anchor to the target, as well as uncertainty scores for selecting the best prediction. Experiments on two benchmarks: LINEMOD and YCB-Video, show that the proposed method outperforms state-of-the-art approaches.
  arXiv  Detail & Related papers  (2020-02-29T06:24: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.