Abstract:

Given a set of objects, the goal of clustering is to construct disjoint subsets such that the objects inside each cluster are more similar than objects from different clusters. There are several algorithms to deal with this problem. In this talk, we will discuss the spectral clustering and its relationship with the diffusion maps. Similar to the positive semi-definite programming relaxation, the problem about how to find an optimal cut function to partition the objects is relaxed and is cast into the form of an eigenvalue problem. We will also discuss how to evaluate the quality of relaxation by the Cheeger’s inequality. This talk is based on the upcoming text book “Ten lectures in diffusion map”by Amit Singer and Hau-Tieng Wu.