Covariance and Principal Component Analysis on Riemannian Manifolds and Graphs

Abstract

We develop notions of covariance and principal component analysis (PCA) for probability measures on Riemannian manifolds of bounded geometry and a discrete counterpart for distributions on the vertex sets of weighted simple graphs. Rather than anchoring variation at the Fr\'{e}chet mean, whose uniqueness and usefulness can fail in this context, we consider variation about every point. This leads to a representation of each point on the manifold by a vector field derived from the heat kernel and thus to a map of the underlying manifold into a Hilbert space of vector fields, in which covariance and PCA carry over from the Euclidean setting. A distinguishing feature of this formulation is that one typically obtains infinitely many principal components, capable of capturing highly nonlinear geometric features and patterns of variation. We prove an embedding theorem for the mapping into the space of vector fields and develop two computational reductions of the theory: RiePCA, a finite-dimensional reduction based on vector fields supported on finitely many points, and GraphPCA, a discrete formulation for measures on weighted graphs in which vector fields assign orientations and magnitudes to edges. Numerical examples and experiments illustrate the behavior of the proposed methods on both synthetic and real data.