Computer Science Colloquium
Spectral Algorithms and Representations
Monday, April 10, 2006 11:45 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185
Colloquium Information: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html
Joel Spencerspencer@cs.nyu.edu, (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.
| contact email@example.com