The Flag Median and FlagIRLS
  Finding prototypes (e.g., mean and median) for a dataset is central to a
number of common machine learning algorithms. Subspaces have been shown to
provide useful, robust representations for datasets of images, videos and more.
Since subspaces correspond to points on a Grassmann manifold, one is led to
consider the idea of a subspace prototype for a Grassmann-valued dataset. While
a number of different subspace prototypes have been described, the calculation
of some of these prototypes has proven to be computationally expensive while
other prototypes are affected by outliers and produce highly imperfect
clustering on noisy data. This work proposes a new subspace prototype, the flag
median, and introduces the FlagIRLS algorithm for its calculation. We provide
evidence that the flag median is robust to outliers and can be used effectively
in algorithms like Linde-Buzo-Grey (LBG) to produce improved clusterings on
Grassmannians. Numerical experiments include a synthetic dataset, the MNIST
handwritten digits dataset, the Mind's Eye video dataset and the UCF YouTube
action dataset. The flag median is compared the other leading algorithms for
computing prototypes on the Grassmannian, namely, the $\ell_2$-median and to
the flag mean. We find that using FlagIRLS to compute the flag median converges
in $4$ iterations on a synthetic dataset. We also see that Grassmannian LBG
with a codebook size of $20$ and using the flag median produces at least a
$10\%$ improvement in cluster purity over Grassmannian LBG using the flag mean
or $\ell_2$-median on the Mind's Eye dataset.
