Cheeger Cuts and p-Spectral Clustering

author: Matthias Hein, Max Planck Institute for Biological Cybernetics, Max Planck Institute
published: July 30, 2009,   recorded: June 2009,   views: 5624


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


Spectral clustering has become in recent years one of the most popular clustering algorithm. In this talk I discuss a generalized version of spectral clustering based on the second eigenvector of the graph p-Laplacian, a non-linear generalization of the graph Laplacian. The clustering obtained for 1<=2 can be seen as an interpolation of the relaxation of the normalized cut (p=2) and the Cheeger cut (p=1). However, the main motivation for p-spectral clustering is the fact, that one can show that the cut value obtained by thresholding the second eigenvector of the p-Laplacian converges towards the optimal Cheeger cut as p tends to 1. I will also present an efficient implementation which allows to do p-spectral clustering for large scale datasets.

See Also:

Download slides icon Download slides: mlss09us_hein_ccpsc_01.pdf (1.9┬áMB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: