# Efficient (approximate) projection onto the special orthogonal group

I need to carry out an optimization on the special orthogonal group $SO(n)$. For the line search I use a simple back-projection method

$$\mbox{minimize}_\tau f(\pi(X+\tau Z))$$

where $X\in SO(n)$ is the current point on the orthogonal group, $Z \in T_XSO(n)$ is the gradient of $f$ w.r.t. $X$ projected onto the tangent space, and $\pi$ is the projection onto the special orthogonal group. My problem is that $\pi$ involves either a matrix inverse or a singular value decomposition which both have time complexity $\mathcal O(n^3)$.

Does anybody know a more efficient way to project a matrix onto $SO(n)$? I would also be happy with an approximate approximation since $X+\tau Z$ is in the vincinity of an orthogonal matrix $X$. I thought a Taylor approximation to the Cayley transform might work, but that gets insufficient very quickly.

Any help is much appreciated!

-

Every rotation in $n$ dimensions can be decomposed into rotations in $\lfloor n/2\rfloor$ planes. Accordingly, every element of the tangent space of $SO(n)$ at the identity, that is, every antisymmetric matrix, is similar to a matrix with antisymmetric $2\times2$ blocks on the diagonal (see Wikipedia).
Thus, you can find the transformation that brings $Z$ into this form, and then exponentiating multiples of $Z$ merely involves exponentiating antisymmetric $2\times2$ matrices, i.e. computing two-dimensional rotation matrices, which merely involves computing a sine and a cosine.
(This is for $X$ the identity, but you can easily transform to that case.)
I hadn't thought about that. Do you know how I would efficiently transform $Z$ into the block-diagonal form (i.e. are there standard algorithms that do that)? –  fabee May 6 '13 at 11:13
@fabee: Yes, diagonalize $Z^2$. (Note that you only have to do this once, not in each line search step.) –  joriki May 6 '13 at 11:15