Getting Around $\mbox{Stief}(n,k)$

We've now laid the groundwork for a meaningful definition of the gradient in the setting of a constraint manifold. At this point, one could run off and try to do a steepest descent search to maximize one's objective functions. Trouble will arise, however, when one discovers that there is no sensible way to combine a point and a displacement to produce a new point because, for finite $s$, $Y+sH$ violates the constraint equations and thus does not give a point on the manifold.

For any manifold, one updates $Y$ by solving a set of differential equations of motion of the form

$$\begin{eqnarray*} \frac{d}{dt} Y &=& H, \\ \frac{d}{dt} H &=& - \Gamma(H,H). \end{eqnarray*}$$

The $\Gamma$ term is crafted to ensure that $H$ remains a tangent vector for all times $t$, thus keeping the path on the manifold. It is called the connection. (The connection term also depends on $Y$.)

To see how these equations could be satisfied, we take the infinitesimal constraint equation for $H$,

$$H^* Y + Y^* H = 0,$$

and differentiate it with respect to $t$, to get

$$\Gamma(H,H)^*Y + Y^* \Gamma(H,H) = 2 H^*H.$$

This can be satisfied generally by $\Gamma(H,H) = Y(H^* H) + T(H,H)$, where $T(H,H)$ is some arbitrary tangent vector.

In the next subsection, we will have reason to consider $\Gamma(H_1,H_2)$ for $H_1 \ne H_2$. For technical reasons, one usually requests that

$$\Gamma(H_1,H_2) = \Gamma(H_2,H_1)$$

(this is called the torsion-free property) and that

$$ip(\Gamma(H_1,H_3),H_2)+ip(H_1,\Gamma(H_2,H_3))=0$$

(this is called the metric compatibility property). These two properties uniquely determine the $T(H_1,H_2)$ term, and thereby uniquely specify the connection. On any manifold, the unique connection with these properties is called the Levi-Civita connection.

The connection for the Stiefel manifold using two different inner products (the Euclidean and the canonical) can be found in the work by Edelman, Arias, and Smith (see [151,155,416]). The function connection computes $\Gamma(H_1,H_2)$ in the template software.

Usually the solution of the equations of motions on a manifold are very difficult to carry out. For the Stiefel manifold, analytic solutions exist and can be found in the aforementioned literature, though we have found very little performance degradation between moving along paths via the equations of motion and simply performing some orthogonalizing factorization on $Y+sH$, as long as the displacements are small. The move function supports multiple methods of geodesic motion, depending on the degree of approximation desired.