# Convex Hulls of Special Euclidean Groups

Don’t get bogged down by the heavy sounding title. Let’s dissect the title first. “Special Euclidean Group” refers to the Euclidean transform aka the rotation and translation matrix together. Recall that the rotation matrix is a 3×3 matrix (9 numbers in all) but have special structure where the determinant of matrix need to be 1.0 and the matrix be an orthogonal matrix (ie. $R^{T} R = I$). These constraint (on the rotation matrix) presents a formidable challenge when we try to formulate and solve numerically complex problems involving the SE(3), SE(2) (special euclidean group). The rotation matrix is said to belong to the special orthogonal group ( $R_{3x3} \in SO(3)$ also $R_{2x2} \in SO(2)$ ). This clarifies the second part of the title.

Convex hull of these groups (written as $conv(SO(3)$ or $conv(SO(2)$) are commonly used relaxations of the rotational matrix. In this post we shall explore how this relaxation is obtained.

## SO(2)

The rotation matrix in 2D is parameterized as follows: \begin{aligned}SO\left( 2\right) =\{ \begin{bmatrix} \cos \left( \theta \right) & \sin \left( \theta \right) \\ -\sin \left( \theta \right) & \cos \left( \theta \right) \end{bmatrix}: \theta \in [0,2\pi] \} \end{aligned} \begin{aligned}SO\left( 2\right) =\{ \begin{bmatrix} x & y \\ -y & x \end{bmatrix}: x^2 + y^2 = 1 \} \end{aligned}

The above definition is relaxed as: \begin{aligned}SO\left( 2\right) =\{ \begin{bmatrix} x & y \\ -y & x \end{bmatrix}: x^2 + y^2 \le 1 \} \end{aligned}

Now, the constraint $x^2 + y^2 \le 1$ can be written as a LMI (Linear Matrix Inequality) by using the Schur Complement trick.

And hence, we can write, \begin{aligned}SO\left( 2\right) =\{ \begin{bmatrix} x & y \\ -y & x \end{bmatrix}: \begin{bmatrix} I_{2x2} & \begin{pmatrix} x \\ y \end{pmatrix} \\ \left( xy\right) & 1 \end{bmatrix} \succcurlyeq 0 \} \end{aligned}

## SO(3)

Convex hull relaxation are also commonly used for the SO(3) group. Since the derivation is complicated (I haven’t looked into the details yet), I simply give the result and reference to the original derivation. This screenshot from Matanya B. Horowitz, Nikolai Matni, Joel W. Burdick, “Convex Relaxations ofSE(2)andSE(3)for Visual Pose Estimation” 2014, https://arxiv.org/pdf/1401.3700.pdf. The reference  in this screenshot is the paper: https://arxiv.org/pdf/0911.5436.pdf

## Conclusion

Thus, we have learnt about how SO(2) and SO(3) can be relaxed by their convex hull. The convex hulls of those in term can be written as a Linear Matrix Inequality (LMI). The point of converting a non-convex constraint like SO(2) and SO(3) to an LMI is that the problem can be solved using the Semidefinite programming (SDP) and Cone Programming (CP). See Convex Optimization book by Boyd and Vandenberghe for details for SDP and CP.