Computer Science Colloquium

Spectral Algorithms and Representations

Santosh Vempala

Monday, April 10, 2006 11:45 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185

Colloquium Information:


Joel, (212) 998-3219


The spectrum of a matrix (or a graph) captures many interesting properties in surprising ways. Spectral methods (based on eigenvalues and eigenvectors) are already used for unsupervised learning, image segmentation, to improve precision and recall in databases and broadly for information retrieval. The common component of these methods is a projection to the space of a few singular vectors of the data. In this talk, we describe this idea and focus on the vital role it plays in efficient algorithms for (a) clustering object-feature (document-term) matrices and (b) the classical problem of learning a mixture of Gaussians. We also highlight a property that makes these methods particularly attractive for large data sets: any matrix (of any size) contains a "constant-size" submatrix from which an approximate spectral representation can be efficiently computed.

top | contact