Semidefinite descriptions of the convex hull of rotation matrices

Abstract

We study the convex hull of $SO(n)$, thought of as the set of $n\times n$ orthogonal matrices with unit determinant, from the point of view of semidefinite programming. We show that the convex hull of $SO(n)$ is doubly spectrahedral, i.e. both it and its polar have a description as the intersection of a cone of positive semidefinite matrices with an affine subspace. Our spectrahedral representations are explicit, and are of minimum size, in the sense that there are no smaller spectrahedral representations of these convex bodies.

arXiv comment29 pages, 1 figure

References in corpus (9)

• Symmetry groups, semidefinite programs, and sums of squares
• Lifts of convex sets and cone factorizations
• Orbitopes
• On the existence of 0/1 polytopes with high semidefinite extension complexity
• Convex Relaxations of SE(2) and SE(3) for Visual Pose Estimation
• Worst-Case Results For Positive Semidefinite Rank
• Efficient Rounding for the Noncommutative Grothendieck Inequality
• A convex solution to Psiaki's first joint attitude and spin-rate estimation problem
• Convex Geometry of Orbits

Cited by in corpus (16)

• Spectral Motion Synchronization in SE(3)
• Robust Rotation Synchronization via Low-rank and Sparse Matrix Decomposition
• A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints
• Convex Optimisation for Inverse Kinematics
• New limits on neutrino non-standard mixings based on prescribed singular values
• Equivariant semidefinite lifts and sum-of-squares hierarchies
• A generalized MBO diffusion generated motion for orthogonal matrix-valued fields
• Pose Graph Optimization in the Complex Domain: Lagrangian Duality, Conditions For Zero Duality Gap, and Optimal Solutions
• A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers
• Maximizing robustness of point-set registration by leveraging non-convexity
• Efficient Projection-Free Online Convex Optimization with Membership Oracle
• On extremal points for some vectorial total variation seminorms
• On the Computability of Continuous Maximum Entropy Distributions: Adjoint Orbits of Lie Groups
• Expanding the reach of quantum optimization with fermionic embeddings
• Spectral Polyhedra
• Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory