SVD vs. QR retractions

[jmc...@princeton.edu]

When optimizing over the Stiefel manifold, what is the difference between using the SVD retraction and the QR retraction (as defined in the Absil et al book, page 59)?

[BM]

Hello, 

They are two different types of retractions (related up to rotations), but the convergence properties (of the algorithm)  are the same for both of them. 

If eta is the search direction at a point X on the Stiefel manifold, then the retractions are as follows.

SVD: R_X(eta) = UV', where USV' is the thin SVD of X + eta. Its also called the Polar decomposition.

QR: R_X(eta) = Q-factor of the QR decomposition of X + eta.  

If Y and Z are the retracted points by using SVD and QR, respectively, then verify that Y'*Z is an orthogonal matrix. 

Regards,

Bamdev

[Nicolas Boumal]

Hello,

Bamdev gave the essentials already. I just want to point out the reason why (at least in the current version of Manopt) we use a different default retraction for Stiefel and fro Grassmann:

SVD (polar factor) is typically more expensive than QR (Q factor) by some multiplicative factor, but it has a nice theoretical advantage which is explained (briefly) here: http://www.sciencedirect.com/science/article/pii/S0024379515001342 page 209 (the end of section 2).

In a nutshell: because Grassmann is here defined as a quotient manifold of Stiefel by the orthogonal group, we have some extra consistency requirements for the retraction. These requirements are fulfilled by the polar factor but not by the Q factor.

(The same article is also in free access here: http://www.optimization-online.org/DB_FILE/2012/09/3619.pdf, see page 7)

Best,

Nicolas