7
$\begingroup$

The following theorem appears without proof in :

Helmke, Uwe, and John B. Moore. Optimization and dynamical systems. Springer Science & Business Media, 2012.

Let $A$ be a symmetric $n\times n$ real matrix. Define the Stiefel manifold as $St(k,n)=\{X\in \mathbb{R}^{n\times k}|X^TX=I\}$.

Then, we consider the following equation :

$\dot{X}=(I-XX^T)AX$, where $X\in St(k,n)$

It is a matrix ODE which is invariant under right multiplication by $O(k)$. Hence it can be considered as an ODE on the Grassmannian.

Helmke and Moore state that it almost-surely converges to an $A$-invariant subspace spanned by a dominant $k$-dimensional eigenbasis of $A$.

I am looking for proof of this theorem. Does anyone know any suitable references ?

$\endgroup$
  • 2
    $\begingroup$ I think the statement is not quite correct: The equation is compatible with right multiplication by $G\in O(k)$. This means that the best one can hope for is that the limit $X_\infty$ spans a subspace also spanned by $k$ dominant eigenvectors. Or in other words, this should more naturally be considered as an ODE on a Grassmann manifold. $\endgroup$ – Sebastian Goette Mar 13 '17 at 17:08
  • $\begingroup$ @SebastianGoette Lets consider the vector field on St(k,n) not Grassmanian.Is it true (and obvious) that the columns of every singularity $X$ of the vector field span a k dimensional dominant eigen space? $\endgroup$ – Ali Taghavi Mar 13 '17 at 20:17
  • $\begingroup$ @mystupid_acct What is a description of the singularities of the vector field. Please see my previous comment. $\endgroup$ – Ali Taghavi Mar 13 '17 at 20:18
  • $\begingroup$ @SebastianGoette You are correct, i have modified my question. $\endgroup$ – mystupid_acct Mar 13 '17 at 22:02
  • 1
    $\begingroup$ @AliTaghavi If the columns of $X$ span an invariant subspace of $A$, then $X$ is a fixpoint. This is because $(1-XX^T)$ projects onto the orthogonal complement of the span of the columns of $X$. But not all fixpoints are stable ... $\endgroup$ – Sebastian Goette Mar 13 '17 at 22:21
5
$\begingroup$

On the Stiefel manifold, consider the function $f(X)=\operatorname{tr}(X^TAX)$. It evolves under the flow of the given vector field as $$\frac d{dt}f=2\operatorname{tr}(X^TA(1-XX^T)AX)\;.$$ Because $1-XX^T$ describes the projection onto the orthogonal complement of the span $V_X$ of the columns of $X$, we have \begin{gather*}\frac d{dt}f\ge 0\;,\\\frac d{dt}f=0\iff \dot X=0\iff\text{$V_X$ is $A$-invariant.}\end{gather*} Hence, $X$ is a generalised gradient field for $f$ (it might in fact be half the actual gradient, but I have not checked).

Now it is easy to see that $f$ induces a Morse-Bott function on the Grassmannian (Morse if the eigenvalues of $A$ are distinct). The only stable fixpoints therefore correspond to the maximum, and the points that don't flow into one of the maxima form a stratified subset of lower dimension.

$\endgroup$
  • $\begingroup$ Is it easy to compute the index of each invariant subspace as a singularity of the morse function? $\endgroup$ – Ali Taghavi Mar 14 '17 at 16:03
  • $\begingroup$ @AliTaghavi Yes, I think so. Take a basis of eigenvectors and see what happens if you modify one of them at a time. $\endgroup$ – Sebastian Goette Mar 14 '17 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.