TR 9:30-11am, Room: TBA.
Instructors: Santosh Vempala and Ravi Kannan (remotely).

Spectral methods have transcended their origin in numerical analysis and are now used in almost every domain with large data sets from web search (e.g., pagerank) and information retrieval (e.g., LSI) to medical diagnosis and prediction. This course is about the mathematics and the algorithmic insights driving these applications.

The course is designed to be accessible to graduate students in computing, mathematics, engineering and operations research. Linear algebra and Algorithms are the prerequisites. If you'd like to follow the course online, send me an email to add you to the mailing list for all announcements, including assignments and lecture notes.

The spectrum of a matrix (or a graph) captures many interesting properties in surprising ways. In this course, we will study spectral methods in several contexts: computing a least-squares fit and its generalizations (find a set of low-dimensional subspaces that minimize the sum of squared distances to a given point set), clustering and partitioning, characterization of topological properties (a graph is planar iff the nullspace of a certain class of adjacency matrices has rank at most 3), the regularity lemma, learning mixtures of distributions, finding large cliques etc.. We will highlight the important common elements, paying special attention to the role of spectral projections (the representation in the space of the top k singular vectors or in the nullspace). On the way, we will study the following fact and its algorithmic consequences: any matrix has a "small" submatrix from which a "good" approximation to the spectral representation can be computed.

Here is a more detailed list of topics. Note that this is a regular graduate course and not a seminar (in spite of the current course number). There will be homework assignments, a midterm exam and a final project.

Santosh Vempala