Flag Logarithm & Geodesic Distance

Subspaces are important objects in the data analysis toolbox. Their importance is notably justified by the well-known manifold hypothesis, which roughly states that high-dimensional data lies close to a lower dimensional embedded submanifold. Subspace methods arise in a lot of contexts such as dimension reduction, denoising and domain adaptation. Many manifold learning methods exist to find such an intrinsic subspace of the data. Probably the simplest one is to perform Principal Component Analysis (PCA) and take the principal (linear) subspace accounting for most of the variability. With such a subspace representation of datasets, one can then compare datasets using subspace distances and make a shift between the data domains using subspace interpolation methods. From a geometric point of view, the adapted space for that is the Grassmann manifold.

Representing a dataset using a subspace however has the limit that it discards information on the hierarchy of the modes of variation. As a consequence, two datasets with very different modes of variability can be represented by the same subspace. For instance, these two Gaussians (blue ellipse) have the same 2D principal subspace (red plane) but their first modes of variabilty are respectively orthogonal. Hence there is a need for multiscale subspace methods.

A group of researchers [Draper et al. 2014, ..., Ma et al. 2021] has been proposing for the past ten years to replace subspaces by sequences of nested subspaces, i.e. flags (cf. Research page). One simple way to represent a dataset as a flag is, through PCA, to store the filtration induced by the eigenspaces of the sample covariance matrix. This hence provides a hierarchical information on the variability of the dataset. For instance, the two previous Gaussians now have two different flag representations. The second subspaces (red plane) of the flags are equal but the first ones (spanned respectively by the red arrows) are different, therefore the filtrations are different.

In this work, we exploit the quotient space structure of flag manifolds and rethink the geodesic endpoint problem (i.e. the search for a minimal-length curve joining two points) as an alignment problem. Recall that flags are equivalence classes of orthogonal matrices (cf. Research page). Since we know the geodesic distance and Riemannian logarithm between two orthogonal matrices (they are related to the matrix exponential and logarithm of skew-symmetric matrices), we can rethink their computation on flag manifolds as the search for the pair of points on two equivalence classes with minimal orthogonal geodesic distance.

Imagine that you have two points on two opposed walls. You want to make them the closest possible while being constrained to stay on the walls. Then you could achieve that by moving the second point at the same horizontal and vertical position as the first point, such that the two are linked by a perpendicular line to the two walls. This was in the case of two straight walls with the Euclidean distance.

In our case, the walls are curved, can be any dimension, and the distance is the orthogonal geodesic distance. Unfortunately, this alignment problem does not seem to enjoy an explicit solution, otherwise we would have solved the original question. However, what we found out it that relaxing the orthogonal geodesic distance to the Euclidean distance now enjoys a solution, which is related to the orthogonal Procrustes problem. Due to the equivalence of norms in finite dimension, we expect that the approximation is rather justified for small errors. Hence we decide to incorporate this approximate alignment step into the iterative algorithm of [Ma et al. 2022].

Our proposed alignment algorithm is the following. Let P and Q be two orthogonal matrices. The aim is to move Q in its equivalence class so that the orthogonal geodesic distance between P and Q gets minimal. One iteration consists in:

1. Computing the logarithm between P and Q ➡ X.

2. Projecting it onto the horizontal space at P ➡ H.

3. Shooting using the orthogonal exponential ➡ M.

4. Projecting the endpoint M onto [Q] using the Euclidean alignment step ➡ Q.

This algorithm was drawn from the one of [Ma et al. 2022], except that their projection onto the vertical space is now replaced by our Euclidean alignment step. We compare our algorithm to [Ma et al. 2022] and get drastic improvements in terms of accuracy, speed and radius of convergence, in addition to overcoming the combinatorial issues they get due to the non-connectedness of the equivalence classes.