mlsanityData to 7 Oct 2026

Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search

arXiv 2207.08350 ↗First posted 18 Jul 2022math.OC cs.CVcited by 2

Not on the map. Why?

Abstract (arXiv)

The rotation search problem aims to find a 3D rotation that best aligns a given number of point pairs. To induce robustness against outliers for rotation search, prior work considers truncated least-squares (TLS), which is a non-convex optimization problem, and its semidefinite relaxation (SDR) as a tractable alternative. Whether this SDR is theoretically tight in the presence of noise, outliers, or both has remained largely unexplored. We derive conditions that characterize the tightness of this SDR, showing that the tightness depends on the noise level, the truncation parameters of TLS, and the outlier distribution (random or clustered). In particular, we give a short proof for the tightness in the noiseless and outlier-free case, as opposed to the lengthy analysis of prior work.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 31 of its 64 references that are in the map. First posted on arXiv 18 Jul 2022.

Builds on

31 of 64 references.

References · 31

  1. 2021Convex optimizationcited by 2,479
  2. 2020TEASER: Fast and Certifiable Point Cloud Registrationcited by 274
  3. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
  4. 2019Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejectioncited by 92
  5. 2016SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Groupcited by 80
  6. 2017Guaranteed Outlier Removal for Point Cloud Registration with Correspondencescited by 62
  7. 2017Near-optimal bounds for phase synchronizationcited by 32
  8. 2019A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outlierscited by 29
  9. 2020Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applicationscited by 26
  10. 2018Robust Fitting in Computer Vision: Easy or Hard?cited by 25
  11. 2018Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Modelscited by 24
  12. 2014Tightness of the maximum likelihood semidefinite relaxation for angular synchronizationcited by 23
19 more
  1. 2018Convex Relaxations for Pose Graph Optimization with Outlierscited by 19
  2. 2015Lagrangian Duality in 3D SLAM: Verification Techniques and Optimal Solutionscited by 18
  3. 2013Global registration of multiple point clouds using semidefinite programmingcited by 17
  4. 2019Distributed Certifiably Correct Pose-Graph Optimizationcited by 17
  5. 2019An Efficient Solution to Non-Minimal Case Essential Matrix Estimationcited by 16
  6. 2021Optimal Pose and Shape Estimation for Category-level 3D Object Perceptioncited by 15
  7. 2022ARCS: Accurate Rotation and Correspondence Searchcited by 15
  8. 2017On the local stability of semidefinite relaxationscited by 12
  9. 2019CvxPnPL: A Unified Convex Solution to the Absolute Pose Estimation Problem from Point and Line Correspondencescited by 12
  10. 2020Certifiable Relative Pose Estimationcited by 11
  11. 2019A convex relaxation to compute the nearest structured rank deficient matrixcited by 7
  12. 2020Certifiably Optimal Monocular Hand-Eye Calibrationcited by 7
  13. 2021On the Tightness of Semidefinite Relaxations for Rotation Estimationcited by 7
  14. 2018Certifiably Globally Optimal Extrinsic Calibration from Per-Sensor Egomotioncited by 6
  15. 2021Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Camerascited by 5
  16. 2015Non-iterative rigid 2D/3D point-set registration using semidefinite programmingcited by 4
  17. 2021Near-Optimal Bounds for Generalized Orthogonal Procrustes Problem via Generalized Power Methodcited by 4
  18. 2019Convex Relaxations for Consensus and Non-Minimal Problems in 3D Visioncited by 3
  19. 2017Tightness of a new and enhanced semidefinite relaxation for MIMO detectioncited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 0; 2024: 0; 2025: 0; 2026: 1.

2 papers.

  1. 2026Advances in Global Solvers for 3D Visioncited by 12
  2. 2022Estimation Contracts for Outlier-Robust Geometric Perceptioncited by 11