Searching, Clustering and Regression on non-Euclidean Spaces

Abstract

This dissertation considers three common tasks (e.g., searching, clustering, regression) over Riemannian spaces. The first task considers the problem of efficiently deciding which of a database of subspaces is most similar to a given input query. Motivated by applications in recognition, image retrieval and optimization, there has been significant recent interest in this problem. Current approaches to this problem have poor scaling in high dimensions, and may not guarantee sublinear query complexity. We present a new approach to approximate nearest subspace search, based on a simple, new locality sensitive hash for subspaces. For the second task, we advocates a novel framework for segmenting a dataset in a Riemannian manifold into clusters lying around low-dimensional submanifolds. This clustering problem is useful for applications such as action identification, dynamic texture clustering, brain fiber segmentation, and clustering of deformed images. The proposed clustering algorithm constructs an affinity matrix by exploiting the geometry and then applies spectral clustering. Theoretical guarantees are established for a variant of the algorithm. To avoid complication, these guarantees assume that the 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. In the third task, we proposes a novel framework for manifold-valued regression and establishes its consistency as well as its contraction rate for a particular setting. Our setting assumes a predictor with values in the interval [0,1] and response with values in a compact Riemannian manifold. This setting is useful for applications such as modeling dynamic scenes or shape deformations, where the visual scene or the deformed objects can be modeled by a manifold. The proposed framework uses the heat kernel on manifolds as an averaging procedure. It directly generalizes the use of the Gaussian kernel in vector-valued regression problems. In order to avoid explicit dependence on estimates of the heat kernel, we follow a Bayesian setting, where Brownian motion induces a prior distribution on the space of continuous functions. We study the posterior consistency and contraction rate of the discrete and continuous Brownian motion priors.