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!

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