  This paper advocates a novel framework for segmenting a dataset in a
Riemannian manifold $M$ into clusters lying around low-dimensional submanifolds
of $M$. Important examples of $M$, for which the proposed clustering algorithm
is computationally efficient, are the sphere, the set of positive definite
matrices, and the Grassmannian. The clustering problem with these examples of
$M$ is already useful for numerous application domains such as action
identification in video sequences, dynamic texture clustering, brain fiber
segmentation in medical imaging, and clustering of deformed images. The
proposed clustering algorithm constructs a data-affinity matrix by thoroughly
exploiting the intrinsic geometry and then applies spectral clustering. The
intrinsic local geometry is encoded by local sparse coding and more importantly
by directional information of local tangent spaces and geodesics. Theoretical
guarantees are established for a simplified variant of the algorithm even when
the clusters intersect. To avoid complication, these guarantees assume that the
underlying submanifolds are geodesic. Extensive validation on synthetic and
real data demonstrates the resiliency of the proposed method against deviations
from the theoretical model as well as its superior performance over
state-of-the-art techniques.
