Vector Diffusion Maps and the Graph Connection Laplacian

Friday, September 30, 2016 - 2:30pm - 3:30pm
Lind 305
Amit Singer (Princeton University)
Vector diffusion maps (VDM) is a mathematical framework for organizing and analyzing high-dimensional datasets that generalizes diffusion maps and other nonlinear dimensionality reduction methods, such as LLE, ISOMAP, and Laplacian eigenmaps. Whereas weighted undirected graphs are commonly used to describe networks and relationships between data objects, in VDM each edge is endowed with an orthogonal transformation encoding the relationship between the data at its vertices. The graph structure and orthogonal transformations are summarized by the graph connection Laplacian. In manifold learning, VDM can infer topological properties from point cloud data such as orientability, and graph connection Laplacians converge to their manifold counterparts (Laplacians for vector fields and higher order forms) in the large sample limit. The graph connection Laplacian satisfies a Cheeger-type inequality that provides a theoretical performance guarantee for the popular spectral algorithm for rotation synchronization, a problem with many applications in robotics and computer vision. The application to 2D class averaging in cryo-electron microscopy will serve as our main motivation.