Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization

• URL: http://arxiv.org/abs/2410.16982v1
• Date: Tue, 22 Oct 2024 13:02:12 GMT
• Title: Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization
• Authors: Ipsita Ghosh, Abiy Tasissa, Christian Kümmerle,
• Abstract summary: 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.
• Score: 7.114174944371803
• License:
• Abstract: The problem of finding suitable point embedding or geometric configurations given only Euclidean distance information of point pairs arises both as a core task and as a sub-problem in a variety of machine learning applications. In this paper, we aim to solve this problem given a minimal number of distance samples. To this end, we leverage continuous and non-convex rank minimization formulations of the problem and establish a local convergence guarantee for a variant of iteratively reweighted least squares (IRLS), which applies if a minimal random set of observed distances is provided. As a technical tool, we establish a restricted isometry property (RIP) restricted to a tangent space of the manifold of symmetric rank-$r$ matrices given random Euclidean distance measurements, which might be of independent interest for the analysis of other non-convex approaches. Furthermore, we assess data efficiency, scalability and generalizability of different reconstruction algorithms through numerical experiments with simulated data as well as real-world data, demonstrating the proposed algorithm's ability to identify the underlying geometry from fewer distance samples compared to the state-of-the-art.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• 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)
• Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares [0.8702432681310401]
  We propose a new algorithm for recovering data that adheres to multiple, heterogeneous low-dimensional structures from linear observations. We show that the IRLS method favorable in identifying low/comckuele state measurements.
  arXiv  Detail & Related papers  (2023-06-08T06:35:47Z)
• Diffeomorphic Mesh Deformation via Efficient Optimal Transport for Cortical Surface Reconstruction [40.73187749820041]
  Mesh deformation plays a pivotal role in many 3D vision tasks including dynamic simulations, rendering, and reconstruction. A prevalent approach in current deep learning is the set-based approach which measures the discrepancy between two surfaces by comparing two randomly sampled point-clouds from the two meshes with Chamfer pseudo-distance. We propose a novel metric for learning mesh deformation, defined by sliced Wasserstein distance on meshes represented as probability measures that generalize the set-based approach.
  arXiv  Detail & Related papers  (2023-05-27T19:10:19Z)
• 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)
• Multi-Fidelity Covariance Estimation in the Log-Euclidean Geometry [0.0]
  We introduce a multi-fidelity estimator of covariance matrices that employs the log-Euclidean geometry of the symmetric positive-definite manifold. We develop an optimal sample allocation scheme that minimizes the mean-squared error of the estimator given a fixed budget. Evaluations of our approach using data from physical applications demonstrate more accurate metric learning and speedups of more than one order of magnitude compared to benchmarks.
  arXiv  Detail & Related papers  (2023-01-31T16:33:46Z)
• 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)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  We propose two variants of the Truncated Orthogonal Iteration to compute multiple leading eigenvectors with sparsity constraints simultaneously. We then apply our algorithms to solve the sparse principle component analysis problem for a wide range of test datasets.
  arXiv  Detail & Related papers  (2021-03-24T23:11:32Z)
• New Methods for Detecting Concentric Objects With High Accuracy [0.0]
  Fitting geometric objects to digitized data is an important problem in many areas such as iris detection, autonomous navigation, and industrial robotics operations. There are two common approaches to fitting geometric shapes to data: the geometric (iterative) approach and algebraic (non-iterative) approach. We develop new estimators, which can be used as reliable initial guesses for other iterative methods.
  arXiv  Detail & Related papers  (2021-02-16T08:19:18Z)
• Stochastic Approximation for Online Tensorial Independent Component Analysis [98.34292831923335]
  Independent component analysis (ICA) has been a popular dimension reduction tool in statistical machine learning and signal processing. In this paper, we present a by-product online tensorial algorithm that estimates for each independent component.
  arXiv  Detail & Related papers  (2020-12-28T18:52:37Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)

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.