UC Berkeley

This thesis covers two distinct topics connected by their use of graphs. First is a theoretical analysis of graph Laplacians and locally linear embedding (LLE) on manifolds using tools for diffusion processes. The implications of this analysis are (1) a better understanding of the relationship between graph Laplacians and LLE, (2) understanding how a graph construction method affects the limit operator, and (3) obtaining a graph has nice properties such as sparsity or a well-behaved spectrum given a desired limit.

In the second topic we examine random graphs and their relationship to nonparametric Bayesian methods. We give combinatorial processes describing several nonparametric hierarchical Bayesian models. These processes lead to the development of new MCMC samplers and provide a new perspective on the models. We introduce the idea of discrete coagulation and fragmentation processes to describe various hierarchical models and identify a particular model of interest using coagulation-fragmentation duality. We consider these random graphs in the more general context of random combinatorial objects and give an application of random trees to drawing a random sample without replacement from a distributed stream.