[Brown CS Talks] Brown CS Seminar: Frank McSherry in Lubrano on 3/13/02 at noon

[talks-admin@list.cs.brown.edu]

			      CS Seminar
		  
		  The Department of Computer Science
			   BROWN UNIVERSITY

			      
			       presents

			    Frank McSherry

		       University of Washington

		  Wednesday, March 13, 2002 at noon
	       Lubrano Conference Room (CIT 4th floor)
	       Refreshments will be served at 11:45 am
			       

		  Data Mining via Spectral Analysis


			       Abstract

Much attention has recently been paid to the analysis of data by
casting the data set as a matrix, and considering its eigenvectors.
This spectral analysis of data has been applied successfully in many
domains; examples include Google's PageRank algorithm, Latent Semantic
Analysis, and Kernel PCA.  However, the success of spectral analysis
is largely empirical, with little analytic understanding of why this
approach works so well.

In this talk I will present a general framework for data mining
problems and show how this framework justifies spectral analysis.
Specifically, we will see that the problems of collaborative
filtering, web search, and data clustering fall into the framework and
give rigorous bounds on the performance of spectral analysis on each
problem. Furthermore, we will see how we can immediately translate
ideas and understanding developed through this framework into new
algorithms which address problems in graph theory, and numerical
analysis.

This research is joint work with Yossi Azar and Amos Fiat at Tel Aviv
University, Dimitris Achlioptas at Microsoft Research, and Anna Karlin
and Jared Saia at the University of Washington.


		     Host:  Professor Steve Reiss