Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, November 03, 2005, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Ulrike von Luxburg (Fraunhofer IPSI, Darmstadt)

Convergence of random graph Laplacians

Clustering is a basic tool in exploratory data analysis which tries to identify meaningful groups among given data points. As for all sample based algorithms it is an important question whether a clustering algorithm is consistent: the more data points we get, the more stable and reliable the constructed partition should be. We want to discuss the question of consistency for the class of spectral clustering algorithms. Starting with a similarity graph representing the sample points, those algorithms use the first eigenvectors of the graph Laplacian matrix to construct a partition of the data points. By combining methods from graph theory, functional analysis, and empirical process theory we can show that different versions of the Laplace matrix (``normalized'' or ``unnormalized'') have very different large sample behavior: while the spectral properties of the normalized Laplacian always converge for increasing sample size, for the unnormalized Laplacian the same is only true under strong additional requirements which are often not satisfied in practice. Hence, from a statistical point of view, we advocate the use of normalized rather than unnormalized graph Laplacians.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login