Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica, DIS
via Salaria 113, II piano
Aula C2

Abstract:
Experimental evidence suggests that spectral techniques are valuable for a wide range of applications. A partial list of such applications include (i) semantic analysis of documents used to cluster documents into areas of interest, (ii) collaborative filtering - the reconstruction of missing data items, and (iii) determining the relative importance of documents based on citation/link structure. Intuitive arguments can explain some of the phenomena that has been observed but little theoretical study has been done. In this paper we give several theoretical results that justify the robustness of the spectral approach while allowing errors and missing data. This gives strong justification of the use of spectral techniques for latent semantic indexing, collaborative filtering, and web site ranking. We give sufficient conditions under which spectral analysis will work, and make use of these results to justify new algorithms for several applications. Joint work with Yossi Azar (Tel-Aviv University), Anna Karlin, Frank McSherry and Jared Saia (University of Washington, Seattle)