Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

You can avoid the entire projection by explicitly computing the exponential map.

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.)

share|improve this answer
    
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
    
Yes, of course! I totally missed that. Thanks a lot. –  fabee May 6 '13 at 11:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.