# Givens rotation and retraction mapping

Here's part of the texts in the book Optimization Algorithms on Matrix Manifolds, when talking about the retraction on a matrix sub-manifold. A retraction is a mapping that maps a tangent vector in a tangent space of a point to the original manifold, which is used in optimization algorithms of gradient descent family.

If I understand correctly, the point of finding a retraction for the orthogonal group, is to find a decomposition for a general matrix where orthogonal matrix appears. But I don't see this clearly for the Givens rotation method (below 4.6). Is it still under the view of matrix decomposition? If yes, what is the decomposition for a general matrix? Or, what's the intuition behind that Givens rotations method, which shows some hints for proof that the mapping is a retraction? Thank you.

For those who are not familiar with the tangent space of the orthogonal group, it's $T_XO=\{Z=X\Omega:\Omega^\mathrm{T}=-\Omega\}$.

-

You have some tangent direction $Z=QΩ$, $Ω^T=−Ω$ and consider the points on the tangent line $$A=Q+ε Z=Q(I+εΩ).$$ For that matrix you want to find a uniquely defined close matrix with an error $O(ε^2)$. The QR decomposition does that, as described. [Add] Usually, the QR decomposition is computed with Householder reflectors for general matrices and Givens rotations for banded or sparse matrices[/Add] Since the factor $(I+εΩ)$ is orthogonal up to second order, the $R$ factor will be of that same order $O(ε^2)$.

The metrically closest matrix can be obtained by the polar decomposition, some iterations of a related algorithm, for instance the Heron-like formula $$A_{k+1}=\tfrac12(A_k+A_k^{-T}),$$ followed by some orthogonalization will also do the trick.

Of course, depending on what you are given, the actual exponential map will give even better results, i.e., perform the QR decomposition on some partial sum $$Q(I+εΩ+\tfrac12ε^2Ω^2+...+\tfrac1{n!}ε^nΩ^n).$$

Update: One can even give an ad-hoc orthogonal matrix that is close to $Q(I+εΩ)$, which is $$Q(I+\tfrac12εΩ)(I-\tfrac12εΩ)^{-1}.$$ ([Add] Which reflects the Cayley transform described in the paper [/Add].)

One can use Pade approximants of $\exp(x)$ to get closer to the exponential, but the only one that is nice is $$Q(I+\tfrac12εΩ+\tfrac1{12}ε^2Ω^2)(I-\tfrac12εΩ+\tfrac1{12}ε^2Ω^2)^{-1}$$

[Add] For a matrix polynomial $p(Ω)$ and antisymmetric $Ω$, the fraction $U=p(Ω)p(-Ω)^{-1}$ has the transpose $$U^T=p(Ω)^{-1}p(-Ω)=p(-Ω)p(Ω)^{-1}=U^{-1}$$ proving the orthogonality, as long as the inverses exist.[/Add]

Comment: I'm obviously to tired to read long texts, these were almost all mentioned in the initial text.

-
Thanks. I am fine with the QR/polar decomposition and exponential mapping, but I am not clear about the part of Givens rotation in the text. Also, any references for the "closest" property of polar decomposition? – ziyuang Apr 20 '14 at 0:30
Givens rotations are one way to compute a QR decomposition. Householder reflectors are another one, but then you have to correct the signs on the diagonal of $R$ after the decomposition. QR of matrix $I$ using Householder gives $(Q,R)=(-I,-I)$. Demanding a positive diagonal of $R$ makes QR unique, independent of the computation method. – LutzL Apr 20 '14 at 0:40
Closest in the Frobenius norm sense. It might also be closest in the spectral norm sense. There was a survey article by Higham on matrix polar decompositions detailing also this, see (perhaps) wikipedia. – LutzL Apr 20 '14 at 0:42