Searching, Clustering and Regression on non-Euclidean Spaces

Thumbnail Image

Persistent link to this item

View Statistics

Journal Title

Journal ISSN

Volume Title


Searching, Clustering and Regression on non-Euclidean Spaces


Published Date




Thesis or Dissertation


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.


University of Minnesota Ph.D. dissertation. August 2015. Major: Mathematics. Advisor: Gilad Lerman. 1 computer file (PDF); x, 141 pages.

Related to




Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Wang, Xu. (2015). Searching, Clustering and Regression on non-Euclidean Spaces. Retrieved from the University Digital Conservancy,

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.