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.

Image result for convex hull

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 [30] 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.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s