3
$\begingroup$

I'm interested in sampling uniformly from the Stiefel manifold $V(k, n)$, but while researching how to do this I came to wonder the following.

In Edelman et al. [1] there are presented two perspectives on the Stiefel manifold: (i) as an embedded submanifold of $\mathbb{R}^{n \times k}$ with $X^\top X = I_k$, and (ii) as a quotient space $O(n) / O(n - k)$ where two matrices $Q_1, Q_2 \in O(n)$ are part of the same equivalence class if their first $k$ columns are the same.

Now, if I understand correctly, the two views are equivalent as differentiable manifolds, but when one wants to endow it with a Riemannian structure, the "natural" choice is different in the two perspectives. More precisely, in the quotient view one restricts to the horizontal space which makes the metric weigh each degree of freedom equally (i.e., it only adds the upper/lower part of the skew-symmetric part of the tangent vectors). This makes it the canonical one, as the authors in [1] say.

How does this relate to my confusion about uniform sampling? Essentially my question can be summarized as, does the "usual approach" to sampling uniformly from $V(k, n)$ agree with any of the measures induced by the Riemannian structure above? If so, which one?

By "usual approach" I mean sampling from the normalized Haar measure, which in the case of the Stiefel manifold is the measure invariant with respect to left orthogonal transformations, $X \mapsto Q X$ with $X \in V(k, n)$ and $Q \in O(n)$. This is discussed in the book by Chikuse [2]. See also this math SE question which summarizes the algorithm he proposes for sampling uniformly from $V(k, n)$.


[1]: Alan Edelman, Tomás A Arias, and Steven T Smith. The geometry of algorithms with orthogonality constraints.

[2]: Chikuse, Y. (2003). Statistics on Special Manifolds.

$\endgroup$
3
  • $\begingroup$ It seems from this answer to a related question that the Haar measure agrees with the Riemannian volume if both are invariant with respect to the action of the orthogonal group. That's actually intuitive. So I guess it comes down to the question, which one of the two Riemannian metrics on the Stiefel manifold yield a volume that is invariant with respect to orthogonal transformations? $\endgroup$
    – Călin
    Oct 8 '19 at 10:53
  • $\begingroup$ I don't understand the notation in your previous comment. But, since the natural Euclidean metric on $\mathbb{R}^{n\times k}$ is invariant under left multiplication by $Q\in O(n)$, and that the Killing form (the negative of which gives the natural invariant Riemannian metric on $O(n)$) is also invariant under left multiplication by $Q\in O(n)$, I would expect that in both cases the induced Riemannian metrics are (left) $O(n)$ invariant, and hence so are the induced measures. $\endgroup$ Oct 8 '19 at 16:04
  • $\begingroup$ Actions of $O(n)$ on $V(k,n)$ is transitive, and generically moves the base point. So you cannot just look at $g_q(Q\Delta_1, Q\Delta_2)_X$, you need to look at $g_q (Q\Delta_1, Q\Delta_1)_{QX}$. $\endgroup$ Oct 8 '19 at 16:19
3
$\begingroup$

We will use $g_e$ to denote the metric induced from the ambient $\mathbb{R}^{n\times k}$ structure, and $g_q$ the metric induced from the bi-invariant Killing metric of $O(n)$.

We will denote by $V(n,k)$ the Stiefel manifold, i.e. the set of $k$ frames on $\mathbb{R}^n$.

Euclidean metric

Using the ambient coordinates for $\mathbb{R}^{n\times k}$, the Euclidean metric has the form (here tangent vectors $\Delta$ are elements of $\mathbb{R}^{n\times k}$ through the obvious inclusion)

$$ g_e(\Delta_1, \Delta_2) = \mathrm{Tr} \Delta_1^T \Delta_2 $$

There is an obvious left action of $O(n)$ on $\mathbb{R}^{n\times k}$: multiply the $n \times k$ matrices on the left by the $n\times n$ matrix $Q\in O(n)$. Note that this action acts by isometry on $\mathbb{R}^{n\times k}$ with the given metric. Furthermore, it preserves the defining condition $X^T X = I_k$ for the submanifold $V(n,k)$. Therefore we see that left multiplication by $O(n)$ matrices generate diffeomorphisms of $V(n,k)$ to itself, and the fact that this is an isometric action on $\mathbb{R}^{n\times k}$ means that the Riemannian metric on $V(n,k)$ induced by $g_e$ is invariant under the $O(n)$ action.

Notice that there is no obvious $O(n)$ action on the right: as the elements of $\mathbb{R}^{n\times k}$ are matrices, action on the right is most naturally given by multiplication by $k\times k$ matrices. The same argument as above shows that $O(k)$ acts by this right multiplication invariantly on $V(n,k)$.

Killing metric

One can also identify elements of $\mathbb{R}^{n\times k}$ as the "right-most $k$ columns of an $n\times n$ matrix, ignoring the first $n-k$ columns." Since we are looking at $V(n,k)$ whose representation as elements of $\mathbb{R}^{n\times k}$ satisfy $X^T X = I_k$, we can consider the ambient space not as the full set of $\mathbb{R}^{n\times n}$ matrices, but as the set of orthogonal $O(n)$ matrices. It is easy to check that the final $k$ columns of an orthogonal matrix satisfy the condition $X^T X = I_k$.

Given an $X$, there are multiple elements of $O(n)$ that realize $X$. They have the same final $k$ columns. The first $n-k$ columns however can be different: but those column vectors must span an $n-k$ dimension space, be mutually orthogonal, and all are orthogonal to the final $k$ columns. In other words, they form an $(n-k)$-frame that is orthogonal to $X$. The set of all such $(n-k)$ frames have an obvious $O(n-k)$ symmetry: you can embed $O(n-k)$ into $O(n)$ by making it block diagonal, with the top left block the $O(n-k)$ and the bottom right block $I_k$.

And this is what we mean by $V(n,k) = O(n) / O(n-k)$: we take the set of $O(n)$ matrices, and quotient it out by right action of $O(n-k)$ using the above embedding, thereby identifying $\tilde{X}\in O(n)$ with $\tilde{X}\tilde{Q} \in O(n)$ where $\tilde{Q}$ is the block diagonal matrix $\mathrm{diag}(Q, I_k)$ where $Q\in O(n-k)$.

Since $O(n)$ (or the connected component of the identity) is a compact Lie group, it has a non-degenerate Killing form which induces a Riemannian metric $g_n$ on $O(n)$.

Multiplication of $O(n)$ on either the left or the right by a fixed orthogonal matrix $Q\in O(n)$ is a diffeomorphism of $O(n)$ to itself. The Killing form (and hence the Riemannian metric $g_n$)is invariant under both the left and right multiplications.

We can induce a metric $g_q$ on $V(n,k)$ by the following procedure: given tangent vectors $\Delta_1, \Delta_2$ at the points $X$, and a representative $\tilde{X}$ in $O(n)$ for $X$, there exists unique lifts $\tilde{\Delta}_1, \tilde{\Delta}_2$ being tangent vectors at $\tilde{X}$ that is orthogonal to orbits of $\tilde{X}$ under the $O(n-k)$ action. We can set $g_q(\Delta_1, \Delta_2)_X = g_n(\tilde{\Delta}_1, \tilde{\Delta}_2)_\tilde{X}$.

To show that this inner product is well-defined, you need to check that this construction is independent of the choice of $\tilde{X}$. This is thanks to the right invariance of $g_n$.

As this entire construction is based on right multiplication by the subgroup $O(n-k)$, and as left multiplication commutes with right multiplication, we have that $g_q$ is automatically left invariant under the action of $O(n)$.

(Left) invariant measure

On $V(n,k)$ there exists a preferred invariant measure $\mu$. We can obtain this from pushing forward the Haar measure $\tilde{\mu}$ on $O(n)$. (The Haar measure is the measure associated to the bi-invariant metric $g_n$ on $O(n)$.) You can simply define, for a subset $A \subset V(n,k)$, its measure to be $$ \mu(A) = \tilde{\mu}(\tilde{A}) $$ where $\tilde{A}$ is the set whose elements are precisely all the representatives $\tilde{X}$ of elements $X\in A$.

Automatically (since we are quotienting on the right to get $V(n,k)$) this measure is invariant under the left action by $O(n)$ on $V(n,k)$.

Now, each of the left-invariant Riemannian metrics $g_q$ and $g_e$ (let's abuse notation and denote also by $g_e$ the induced metric on $V(n,k)$ by the Euclidean metric of $\mathbb{R}^{n\times k}$) also generate, via their volume forms, a left-invariant measure. What are their relations?

In the case of volume forms, one sees that the Riemannian volume forms of $g_q$ and $g_e$, being both volume forms, must be proportional to each other in the sense that there exists some function $\eta: V(n,k) \to \mathbb{R}_+$ such that $\mathrm{dvol}_{g_q} = \eta \mathrm{dvol}_{g_e}$. Since $O(n)$ acts transitively on $V(n,k)$, for any $x,y\in V(n,k)$ there exists an element $Q$ of $O(n)$ that sends $x \to y$. The invariance of both $\mathrm{dvol}_{g_e}$ and $\mathrm{dvol}_{g_q}$ under the action of $Q$ implies then we must have $\eta(x) = \eta(y)$. Showing that any two invariant volume forms must differ by only a constant multiple.

The case with measures are pretty much the same, plus some technical analysis details.

Two Riemannian structures with the same volume form?

It shouldn't be too surprising that you can have multiple different Riemannian structures with the same volume form. Consider the two dimensional torus which we parametrize by $[0,1)^2$. The two Riemannian metrics $dx^2 + dy^2$ and $\frac12 dx^2 + 2 dy^2$ are not isometric, and not even conformally isometric. But they generate exactly the same volume form. Alternatively, think about how $SL(n)$ matrices all preserve volume, but only $SO(n)$ matrices also preserve shape (metric).

In terms of your question about sampling, think simply about the case of $\mathbb{R}^2$. From a large scale, sampling all the points along $\mathbb{Z}^2$ and all the points along $\mathbb{2Z} \times \frac12 \mathbb{Z}$ have the same density (for any rectangular box with side lengths $\gg 1$, the two give the same number of points in the box). But you can make the case that the sampling you get are different.

Are there more than one Riemannian structures?

In general, there are infinitely many left-invariant Riemannian metrics on any Lie group. Take any basis of left-invariant vector fields $L_1, \ldots, L_m$ on your Lie group, you can define a dual Riemannian metric by simply forming $L_1\otimes L_1 + \cdots + L_m \otimes L_m$. This metric is automatically left-invariant.

In the case of your quotient space, notice that the infinitesimal generators of the right actions by $O(n-k)$ are left invariant vector fields. So you can take a basis of left-invariant vector fields on $O(n)$ such that the first $(n-k)(n-k-1)/2$ are along the fibres of the $O(n-k)$ action, and the other ones just to complete a basis. Then you can define a left (but now, not generally speaking right invariant) Riemannian metric as above.

Then, given $X\in V(n,k)$ and $\Delta$ a tangent vector, and $\tilde{X}$ an representative of $X$, there exists a unique choice of of $\tilde{\Delta}$, being a tangent vector at $\tilde{X}$, such that when decomposed using our basis vector fields, the coefficients for the first components (corresponding to the part tangential to $O(n-k)$ fibers) vanish identically. One would like to define the metric using just this lift. However, this is not possible as a priori the left-invariant metric on $O(n)$ is not right-invariant.

We can however exploit the fact that $O(n-k)$ is a compact group. So we can integrate over the representatives using the Haar measure on $O(n-k)$ to get an averaged version of an Riemannian metric. (Alternatively, we can integrate over the $O(n-k)$ action on $O(n)$ and obtain a Riemannian metric that is both $O(n)$ invariant on the left and $O(n-k)$ invariant on the right, and then do the same procedure as done previously using the Killing form.)

One sees then that, in general, different choices of bases initially would give rise to different left-invariant Riemannian metrics on $V(n,k)$.

$\endgroup$
1
  • $\begingroup$ Thanks a lot for the very comprehensive answer, @WillieWong. $\endgroup$
    – Călin
    Oct 9 '19 at 9:20
1
$\begingroup$

There exists a bi-invariant Haar measure on $V(k,n)$, coming from the bi-invariant measure on $SO(n)$ and "forgetting" the additional vectors. I believe it coincides with both your approaches. Let us discuss this.

The fact that the Haar measure on $SO(n)$ is a particular case of the general case of compact Lie groups $G$. Using the fact that a Lie group admits a unique left (resp. right) Haar probability measure $\mu_L$ (resp. $\mu_R$), you can form the bi-invariant probability measure $$ \mu(A) := \int_G \mu_L(A\cdot g)\,\mathrm d\mu_R(g). $$ In fact, because it is left- and right-invariant, and by uniqueness, it must equal $\mu_L$ and $\mu_R$. (Note that, in the particular case of $SO(n)$, there are left-invariant metrics that are not right-invariant (physically, the moment of inertia is not isotropic). However, their associated volume form is left-invariant, so they are a multiple of $\mu$ hence bi-invariant.)

Now let $\varphi:SO(n)\to V(k,n)$ be the map that forgets the last $n-k$ vectors. Then $g\cdot\varphi(h)=\varphi(gh)$, so the measure $\varphi_*\mu$ is left-invariant. In the same way as above, the measure $$ \nu(A) := \int_G \varphi_*\mu(A\cdot g)\,\mathrm d\mu(g) $$ is bi-invariant on $V(k,n)$, and again any left- or right-invariant measure must be a scalar multiple of it, hence bi-invariant.

Since I believe you showed above that the measures you described are either left- or right-invariant, they must agree, and be the same as the one I described.

One last thing: to actually sample an element of $V(k,n)$, I would if I were you sample $k$ independent standard Gaussian vectors in $\mathbb R^n$ (i.e. $nk$ independent variables with law $\mathcal N(0,1)$), and perform a Gram-Schmidt algorithm or similar. It is clear that it gives a right invariant measure, hence it must be the same as each of the ones described above.

$\endgroup$

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.