Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On the Tightness of Semidefinite Relaxations for Rotation Estimation

Brynte, Lucas ; Larsson, Viktor ; Iglesias, José Pedro ; Olsson, Carl LU and Kahl, Fredrik LU (2022) In Journal of Mathematical Imaging and Vision 64(1). p.57-67
Abstract

Why is it that semidefinite relaxations have been so successful in numerous applications in computer vision and robotics for solving non-convex optimization problems involving rotations? In studying the empirical performance, we note that there are few failure cases reported in the literature, in particular for estimation problems with a single rotation, motivating us to gain further theoretical understanding. A general framework based on tools from algebraic geometry is introduced for analyzing the power of semidefinite relaxations of problems with quadratic objective functions and rotational constraints. Applications include registration, hand–eye calibration, and rotation averaging. We characterize the extreme points and show that... (More)

Why is it that semidefinite relaxations have been so successful in numerous applications in computer vision and robotics for solving non-convex optimization problems involving rotations? In studying the empirical performance, we note that there are few failure cases reported in the literature, in particular for estimation problems with a single rotation, motivating us to gain further theoretical understanding. A general framework based on tools from algebraic geometry is introduced for analyzing the power of semidefinite relaxations of problems with quadratic objective functions and rotational constraints. Applications include registration, hand–eye calibration, and rotation averaging. We characterize the extreme points and show that there exist failure cases for which the relaxation is not tight, even in the case of a single rotation. We also show that some problem classes are always tight given an appropriate parametrization. Our theoretical findings are accompanied with numerical simulations, providing further evidence and understanding of the results.

(Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Algebraic geometry, Almost minimal varieties, Duality, Rotation estimation, SDP relaxations, Sum-of-squares
in
Journal of Mathematical Imaging and Vision
volume
64
issue
1
pages
57 - 67
publisher
Springer
external identifiers
  • scopus:85116735145
ISSN
0924-9907
DOI
10.1007/s10851-021-01054-y
language
English
LU publication?
yes
additional info
Publisher Copyright: © 2021, The Author(s).
id
2c933d89-f9a3-430d-80f9-589246fa5591
date added to LUP
2021-11-12 12:43:49
date last changed
2022-06-29 12:55:51
@article{2c933d89-f9a3-430d-80f9-589246fa5591,
  abstract     = {{<p>Why is it that semidefinite relaxations have been so successful in numerous applications in computer vision and robotics for solving non-convex optimization problems involving rotations? In studying the empirical performance, we note that there are few failure cases reported in the literature, in particular for estimation problems with a single rotation, motivating us to gain further theoretical understanding. A general framework based on tools from algebraic geometry is introduced for analyzing the power of semidefinite relaxations of problems with quadratic objective functions and rotational constraints. Applications include registration, hand–eye calibration, and rotation averaging. We characterize the extreme points and show that there exist failure cases for which the relaxation is not tight, even in the case of a single rotation. We also show that some problem classes are always tight given an appropriate parametrization. Our theoretical findings are accompanied with numerical simulations, providing further evidence and understanding of the results.</p>}},
  author       = {{Brynte, Lucas and Larsson, Viktor and Iglesias, José Pedro and Olsson, Carl and Kahl, Fredrik}},
  issn         = {{0924-9907}},
  keywords     = {{Algebraic geometry; Almost minimal varieties; Duality; Rotation estimation; SDP relaxations; Sum-of-squares}},
  language     = {{eng}},
  number       = {{1}},
  pages        = {{57--67}},
  publisher    = {{Springer}},
  series       = {{Journal of Mathematical Imaging and Vision}},
  title        = {{On the Tightness of Semidefinite Relaxations for Rotation Estimation}},
  url          = {{http://dx.doi.org/10.1007/s10851-021-01054-y}},
  doi          = {{10.1007/s10851-021-01054-y}},
  volume       = {{64}},
  year         = {{2022}},
}