Eigenvalues, Spielman Tutors

I made it to Providence, RI, in time to catch friends and the final tutorial at FOCS. Dan Spielman, dangling jewelry on his left ear, gently introduced eigenvalues and eigenvectors of matrices (adjacency, Laplacian) associated with graphs, used the "first" few eigenvectors to embed example graphs (polygons to polytopes) and drew the audience into the area nicely. He discussed using "large" eigenvectors to color nodes and pointed out the difficulties in using eigenvectors to solve the graph isomorphism problem (sign changes of eigenvectors and multiplicities of eigenvalues end up generating the problem of having to check exponential number of permutations). He showed the application of using eigenvectors for graph cutting to image segmentation (which has been a rage in the vision community for some time now), thanks to his daughter's image, and argued that the spectral partitioning method is useful in incorporating more of what we know about images (or the input data/domain). Planted versions of partitioning problems arise nicely, and he discussed eigenvalues of matrices associated with random graphs. He pointed to two large areas for research: eigenvalues (singular value substitutes) for directed graphs (check out some work on Dirichlet eigenvalues) and analyzing gaps in eigenvalue sequences, with emphasis on ultimately understanding graph properties via such research. He wrapped up the tutorial by discussing eigenvalue computation: power method, inverse power method, Lanczo's and other gems. There are some powerful open problems (sparsifying graph A by B, wavelets for graphs, etc). Check out the website Dan promises to set up soon with slides and slick code. It was a terrific tutorial.

PS: FOCS 2007 search on google reveals a (promoted!) sponsored search link to Krzysztof's masterpiece.