Certifiable Outlier-Robust Geometric Perception: Exact Semidefinite Relaxations and Scalable Global Optimization

• URL: http://arxiv.org/abs/2109.03349v1
• Date: Tue, 7 Sep 2021 21:42:16 GMT
• Title: Certifiable Outlier-Robust Geometric Perception: Exact Semidefinite Relaxations and Scalable Global Optimization
• Authors: Heng Yang, Luca Carlone
• Abstract summary: We propose the first general framework to design cert algorithms for robust geometric perception in the presence of outliers. Our experiments demonstrate that our SDP relaxation is exact with up to outliers across applications.
• Score: 29.738513596063946
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose the first general and scalable framework to design certifiable algorithms for robust geometric perception in the presence of outliers. Our first contribution is to show that estimation using common robust costs, such as truncated least squares (TLS), maximum consensus, Geman-McClure, Tukey's biweight, among others, can be reformulated as polynomial optimization problems (POPs). By focusing on the TLS cost, our second contribution is to exploit sparsity in the POP and propose a sparse semidefinite programming (SDP) relaxation that is much smaller than the standard Lasserre's hierarchy while preserving exactness, i.e., the SDP recovers the optimizer of the nonconvex POP with an optimality certificate. Our third contribution is to solve the SDP relaxations at an unprecedented scale and accuracy by presenting STRIDE, a solver that blends global descent on the convex SDP with fast local search on the nonconvex POP. Our fourth contribution is an evaluation of the proposed framework on six geometric perception problems including single and multiple rotation averaging, point cloud and mesh registration, absolute pose estimation, and category-level object pose and shape estimation. Our experiments demonstrate that (i) our sparse SDP relaxation is exact with up to 60%-90% outliers across applications; (ii) while still being far from real-time, STRIDE is up to 100 times faster than existing SDP solvers on medium-scale problems, and is the only solver that can solve large-scale SDPs with hundreds of thousands of constraints to high accuracy; (iii) STRIDE provides a safeguard to existing fast heuristics for robust estimation (e.g., RANSAC or Graduated Non-Convexity), i.e., it certifies global optimality if the heuristic estimates are optimal, or detects and allows escaping local optima when the heuristic estimates are suboptimal.

Related papers

• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• Uncertainty-Aware Testing-Time Optimization for 3D Human Pose Estimation [68.75387874066647]
  We propose an Uncertainty-Aware testing-time optimization framework for 3D human pose estimation. Our approach outperforms the previous best result by a large margin of 4.5% on Human3.6M.
  arXiv  Detail & Related papers  (2024-02-04T04:28:02Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  We propose a sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with objectives and deterministic equality constraints. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices.
  arXiv  Detail & Related papers  (2022-11-29T05:52:17Z)
• STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations [27.353023427198806]
  We consider solving high-order semidefinite programming relaxations of nonconstrained optimization problems (POPs) Existing approaches, which solve the SDP independently from the POP, either cannot scale to large problems or suffer from slow convergence due to the typical uneneracy of such SDPs. We propose a new algorithmic framework called SpecTrahedral vErtices (STRIDE)
  arXiv  Detail & Related papers  (2021-05-28T18:07:16Z)
• Towards Optimal Branching of Linear and Semidefinite Relaxations for Neural Network Robustness Certification [10.349616734896522]
  We study certifying the robustness of ReLU neural networks against adversarial input perturbations. We take a branch-and-bound approach to propose partitioning the input uncertainty set and solving the relaxations on each part separately. We show that this approach reduces relaxation error, and that the error is eliminated entirely upon performing an LP relaxation with a partition intelligently designed to exploit the nature of the ReLU activations.
  arXiv  Detail & Related papers  (2021-01-22T19:36:40Z)
• Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras [0.0]
  Relative Pose problem (RPp) for cameras aims to the relative orientation translation (pose) given a set of pair-wise rotations between two cameras. In this paper, we introduce a family of certifiers that is shown to increase the ratio of detected optimal solutions. We prove through synthetic and real data that the proposed framework provides a fast and robust relative pose estimation.
  arXiv  Detail & Related papers  (2021-01-21T10:07:05Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)
• One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers [32.1176248075545]
  We propose the first general and practical to design certifiable algorithms for perception in the presence of a large amount of outliers. Our dual certifiers leverage solution-of-any suboptimal optimality of any problem.
  arXiv  Detail & Related papers  (2020-06-11T19:46:42Z)
• TEASER: Fast and Certifiable Point Cloud Registration [30.19476775410544]
  First fast and robust certifiable algorithm for the registration of 3D points in the presence of large amounts of outliers. Second fast and robust certifiable translation, named TEASER++, uses graduated non-componentity to solve a large subproblem.
  arXiv  Detail & Related papers  (2020-01-21T18:56:00Z)

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.