Localization from structured distance matrices via low-rank matrix recovery

• URL: http://arxiv.org/abs/2311.18076v2
• Date: Tue, 30 Jul 2024 22:54:45 GMT
• Title: Localization from structured distance matrices via low-rank matrix recovery
• Authors: Samuel Lichtenberg, Abiy Tasissa,
• Abstract summary: 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.
• Score: 3.069335774032178
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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, while the distances among the $n$ points are unknown. For this scheme, a simple adaptation of the Nystrom method, which is often used for kernel approximation, is a viable technique to estimate the configuration of the anchors and the $n$ points. In this manuscript, 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. In this setting, the standard Nystrom approach is not applicable, necessitating an alternative technique to estimate the configuration of the anchors and the $n$ points. We show that this problem can be framed as the recovery of a low-rank submatrix of a Gram matrix. Using synthetic and real data, we demonstrate that the proposed approach can exactly recover configurations of points given sufficient distance samples. This underscores that, in contrast to methods that rely on global sampling of distance matrices, the task of estimating the configuration of points can be done efficiently via structured sampling with well-chosen reliable anchors. Finally, our main analysis is grounded in a specific centering of the points. With this in mind, we extend previous work in Euclidean distance geometry by providing a general dual basis approach for points centered anywhere.

Related papers

• Structured Sampling for Robust Euclidean Distance Geometry [6.422262171968397]
  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.
  arXiv  Detail & Related papers  (2024-12-14T03:42:18Z)
• 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)
• Arbitrary-Scale Point Cloud Upsampling by Voxel-Based Network with Latent Geometric-Consistent Learning [52.825441454264585]
  We propose an arbitrary-scale Point cloud Upsampling framework using Voxel-based Network (textbfPU-VoxelNet) Thanks to the completeness and regularity inherited from the voxel representation, voxel-based networks are capable of providing predefined grid space to approximate 3D surface. A density-guided grid resampling method is developed to generate high-fidelity points while effectively avoiding sampling outliers.
  arXiv  Detail & Related papers  (2024-03-08T07:31:14Z)
• Anchor-free Clustering based on Anchor Graph Factorization [17.218481911995365]
  We introduce a novel method termed Anchor-free Clustering based on Anchor Graph Factorization (AFCAGF) AFCAGF innovates in learning the anchor graph, requiring only the computation of pairwise distances between samples. We evolve the concept of the membership matrix between cluster centers and samples in FKM into an anchor graph encompassing multiple anchor points and samples.
  arXiv  Detail & Related papers  (2024-02-24T02:16:42Z)
• 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)
• Neural Inverse Kinematics [72.85330210991508]
  Inverse kinematic (IK) methods recover the parameters of the joints, given the desired position of selected elements in the kinematic chain. We propose a neural IK method that employs the hierarchical structure of the problem to sequentially sample valid joint angles conditioned on the desired position.
  arXiv  Detail & Related papers  (2022-05-22T14:44:07Z)
• Local optimisation of Nystr\"om samples through stochastic gradient descent [32.53634754382956]
  We consider an unweighted variation of the squared-kernel discrepancy criterion as a surrogate for the classical criteria used to assess the Nystr"om approximation accuracy. We perform numerical experiments which demonstrate that the local minimisation of the radial SKD yields Nystr"om samples with improved Nystr"om approximation accuracy.
  arXiv  Detail & Related papers  (2022-03-24T18:17:27Z)
• Point-Set Anchors for Object Detection, Instance Segmentation and Pose Estimation [85.96410825961966]
  We argue that the image features extracted at a central point contain limited information for predicting distant keypoints or bounding box boundaries. To facilitate inference, we propose to instead perform regression from a set of points placed at more advantageous positions. We apply this proposed framework, called Point-Set Anchors, to object detection, instance segmentation, and human pose estimation.
  arXiv  Detail & Related papers  (2020-07-06T15:59:56Z)
• 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.