General form of optimization on manifolds.
General form of optimization methods on Riemannian manifolds: $x_{t+1} = x_t + v_t$, where $v_t$ is the update/step vector (Euclidean); $x_{t+1} = R(x_t, v_t)$ (Riemannian). Riemannian gradient descent on submanifolds with projection as retraction: $x_{t+1} = \Pi(x_t - c_t \nabla f(x_t))$, $c_t > 0$ is stepsize coefficient.
Retraction $R(x, v)$ around a point $x_0$ in a $C^k$ manifold $M$ (weaker than a smooth manifold), $k \ge 2$, is a $C^{k−1}$ mapping from a neighborhood $U$ of $(x_0, 0)$ in the tangent bundle to the manifold, such that (a) it maps every zero tangent vector to the point of tangent, and (b) the differential of every restricted retraction evaluated at the zero tangent vector is the identity map of the tangent space: $\forall (x, 0) \in U$, (a) $R(x, 0) = x$; (b) $d(R_x)_0 = \text{Id}$, where $R_x = R|_{U \cap T_x M}$ and $d(R_x)_0 : T_0 (T_x M) \cong T_x M \mapsto T_x M$, under the usual identification of $T_0 (T_x M)$ with $T_x M$. Retraction $R(x, v)$ on a $C^k$ manifold $M$, $k \ge 2$, is a $C^{k−1}$ mapping from an open subset of the tangent bundle to the manifold, such that it is a retraction around every point in the manifold: $R: \mathscr{D} \mapsto M$, $\mathscr{D} \subset T M$, $\{(x, 0) : x \in M\} \subset \mathscr{D}$, $\exists (U_i)_{i \in I}$: $\mathscr{D} = \cup_{i \in I} U_i$, $\forall i \in I$, $R|_{U_i}$ is a retraction around some point $x \in M$. Restricted retraction $R_x(v)$ at a point $x \in M$ is the restriction of the retraction to the intersection of its domain with the tangent space at the point: $R_x = R|_{\mathscr{D} \cap T_x M}$.
Second-order retraction on a $C^k$ manifold, $k \ge 3$, is a retraction on the manifold that has zero initial acceleration: $\forall (x, v) \in T M$, $D_t \gamma'(0) = 0$, where $\gamma: I \mapsto M$, $I = \{t : (x, t v) \in \mathscr{D}\}$, and $\gamma(t) = R_x(t v)$. Retraction can be generalized to higher orders, in several ways. Retraction of order i on a $C^k$ manifold, $1 \le i < k$, is a retraction that induces curves on the manifold whose velocities have zero initial covariant derivatives up to the $(i-1)$-th order: $\forall (x, v) \in T M$, $\forall j \in \{1, \cdots, i - 1\}$, $D_t^j \gamma'(0) = 0$. Alternatively, retraction of order i on a $C^k$ manifold, $1 \le i < k$, is a $C^{k−1}$ mapping from an open subset of the tangent bundle to the manifold, such that it agrees with the exponential map to the k-th order at the zero tangents: $\forall (x, v) \in \mathscr{D}$, $R_x(t v) = \exp_x(t v) + o(t^i)$, in the sense that, $\lim_{t \to 0} d_g(R_x(t v), \exp_x(t v)) / t^i = 0$. The retraction as defined earlier is a first-order retraction; second-order retraction is also consistent with this definition (see [@Absil2012, Prop 3] for a similar but not very rigorous notion). Higher-order retractions are found for several matrix manifolds [@Gawlik2018], in the sense of Taylor expansions of their analytic exponential maps.
Pullback $R^∗ f$ or $f \circ R$ of a real-valued function on a $C^k$ manifold by a retraction is the real-valued function on the domain of the retraction defined by the pullback of the function as a 0-form, which is equivalent to the composition of the function and the retraction: $R^∗ f: \mathscr{D} \mapsto \mathbb{R}$, $\forall (x, v) \in \mathscr{D}$, $(R^∗ f)_v = f_{R(v)} = f \circ R_x(v)$; or simply, $R^∗ f = f \circ R$. Pullback $R_x^∗ f$ or $f \circ R_x$ at a point is the restriction of the pullpack to the intersection of its domain with the tangent space at that point: $R_x^∗ f = (R^∗ f)|_{\mathscr{D} \cap T_x M}$; or simply $R_x^∗ f = f \circ R_x$. For every twice-differentiable real-valued function and second-order retraction on a $C^k$ manifold, the Hessian operator of the function at every point equals that of its pullback by the retraction at that point evaluated at the zero tangent vector [@Absil2008, Prop 5.5.5]: $\forall x \in M$, $(\text{Hess}~f)_x = \text{Hess}(f \circ R_x)(0)$.
Retractions can be constructed for:
Retractions on Stiefel manifolds are mostly based on matrix decompositions. Sphere: normalization, $R(x, v) = \frac{x + v}{\|x + v\|}$. Orthogonal group: let $V = X \Omega$ where $\Omega$ is a skew-symmetric matrix, (1) QR decomposition, via Gram-Schmidt orthonormalization, $R(X, X \Omega) = X \text{qf}(I + \Omega)$, where $\text{qf}(M) = Q$ such that $M = Q R$, $R \in U_+(n)$, the set of upper triangular matrices with positive diagonal entries; (2) polar decomposition, via eigen-decomposition: $R(X, X \Omega) = X (I + \Omega) (I - \Omega^2)^{-1/2}$; (3) Givens rotations: $R(X, X \Omega) = X~\text{Giv}(\Omega)$, where $\text{Giv}(\Omega) = \prod_{i < j} G(i, j, \Omega_{ij})$, $[G(i, j, \theta)]_{(i,j)} = \begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}$, and $[G(i, j, \theta)]_{k,l} = \delta_{kl}$ otherwise; (4) Cayley transform: $R(X, X \Omega) = X (I - \Omega/2)^{-1}(I + \Omega/2)$; (5) exponential map: $\exp(X, X \Omega) = X e^\Omega$, where matrix exponential $e^\Omega = \sum_{i=0}^\infty \frac{1}{i!} \Omega^i$. Algorithms for accurately evaluating this exponential map (5) have a numerical cost at best similar to those for (2). General Stiefel manifold: (1) QR decomposition, via the modified Gram-Schmidt algorithm, $R(X, V) = \text{qf}(X + V)$, (2) polar decomposition, via eigen-decomposition: $R(X, V) = (X + V) (I_k - V^T V)^{-1/2}$, which involves an eigen-decomposition in $O(k^3)$ time, and $O(nk^2)$ scalar additions and multiplications; the numerical cost is reasonable when $k$ is small. These retractions are all defined for the entire tangent bundle.
Retractions on Grassmann manifolds are mostly based on quotient. Let $\tilde M$ be an open, dense subset of a Euclidean space, $\pi: \tilde M \mapsto M$ be a Riemannian submersion, given a retraction $\tilde R$ on the domain, one can construct a retraction on the quotient manifold $M$ as $R(x, v) = \{\pi(\tilde R(\tilde x, \tilde v_{\tilde x})) : \tilde x \in \pi^{-1}(x)\}$ if it is a mapping, i.e. the right-hand side are singletons. The retraction on the domain could be $\tilde R(\tilde x, \tilde v) = \tilde x + \tilde v^H$, where $\tilde v^H$ is the projection of $\tilde v$ to the horizontal tangent space; this gives $R(x, v) = \pi(\tilde x + \tilde v^H_{\tilde x})$ where $\tilde x \in \pi^{-1}(x)$, or equivalently, $R(\pi(\tilde x), d \pi_{\tilde x} (\tilde v)) = \pi(\tilde x + \tilde v^H)$. In computation, we operate with $(\tilde x, \tilde v)$, and this retraction simply means $\tilde x + \tilde v^H$. Per quotient manifold theorem and Riemannian submersion theorem, given an isometric Lie group $G$ acting on $\tilde M$, if the quotient map $\pi: \tilde M \mapsto \tilde M / G$ takes every point to its orbit, i.e. $\pi(\tilde x) = G \cdot \tilde x$, then $R(x, v)$ is a mapping and thus a retraction on the quotient manifold. Because the general linear group $\text{GL}_k$ on the full-rank manifold $M^∗_{n,k}$ satisfies such condition, we have thus constructed a retraction on the Grassmann manifold $G_{k,n} = M^∗_{n,k} / \text{GL}_k$.
For retractions on rank-k manifolds, see [@Absil2015].
Retractions for the same manifold shall be evaluated by (1) their order of approximation and (2) its computational efficiency.
Constrained optimization (projected updates, uses projection):
Riemannian optimization (on intrinsic manifold, use exponential map by default):
Riemannian optimization is mostly applied to matrix manifolds, see [@Absil2008] for a book treatment.
Escaping saddle points (in smooth optimization):