Foundations and Trends® in Theoretical Computer Science > Vol 4 > Issue 3–4

Spectral Algorithms

By Ravindran Kannan, Microsoft Research, India, kannan@microsoft.com | Santosh Vempala, Georgia Institute of Technology, USA, vempala@cc.gatech.edu

 
Suggested Citation
Ravindran Kannan and Santosh Vempala (2009), "Spectral Algorithms", Foundations and Trends® in Theoretical Computer Science: Vol. 4: No. 3–4, pp 157-288. http://dx.doi.org/10.1561/0400000025

Publication Date: 20 Oct 2009
© 2009 R. Kannan and S. Vempala
 
Subjects
Design and analysis of algorithms,  Computational Number Theory
 

Free Preview:

Download extract

Share

Download article
In this article:
I Applications 
1 The Best-Fit Subspace 
2 Mixture Models 
3 Probabilistic Spectral Clustering 
4 Recursive Spectral Clustering 
5 Optimization via Low-Rank Approximation 
II Algorithms 
6 Matrix Approximation via Random Sampling 
7 Adaptive Sampling Methods 
8 Extensions of SVD 
References 

Abstract

Spectral methods refer to the use of eigenvalues, eigenvectors, singular values, and singular vectors. They are widely used in Engineering, Applied Mathematics, and Statistics. More recently, spectral methods have found numerous applications in Computer Science to "discrete" as well as "continuous" problems. This monograph describes modern applications of spectral methods and novel algorithms for estimating spectral parameters. In the first part of the monograph, we present applications of spectral methods to problems from a variety of topics including combinatorial optimization, learning, and clustering. The second part of the monograph is motivated by efficiency considerations. A feature of many modern applications is the massive amount of input data. While sophisticated algorithms for matrix computations have been developed over a century, a more recent development is algorithms based on "sampling on the fly" from massive matrices. Good estimates of singular values and low-rank approximations of the whole matrix can be provably derived from a sample. Our main emphasis in the second part of the monograph is to present these sampling methods with rigorous error bounds. We also present recent extensions of spectral methods from matrices to tensors and their applications to some combinatorial optimization problems.

DOI:10.1561/0400000025
ISBN: 978-1-60198-274-2
148 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-60198-275-9
148 pp. $150.00
Buy E-book (.pdf)
Table of contents:
Part I Applications
1: The Best-Fit Subspace
2: Mixture Models
3: Probabilistic Spectral Clustering
4: Recursive Spectral Clustering
5: Optimization via Low-Rank Approximation
Part II Algorithms
6: Matrix Approximation via Random Sampling
7: Adaptive Sampling Methods
8: Extensions of SVD
References

Spectral Algorithms

Spectral methods refer to the use of eigenvalues, eigenvectors, singular values and singular vectors. They are widely used in Engineering, Applied Mathematics and Statistics. More recently, spectral methods have found numerous applications in Computer Science to "discrete" as well "continuous" problems. Spectral Algorithms describes modern applications of spectral methods, and novel algorithms for estimating spectral parameters. The first part of the book presents applications of spectral methods to problems from a variety of topics including combinatorial optimization, learning and clustering. The second part of the book is motivated by efficiency considerations. A feature of many modern applications is the massive amount of input data. While sophisticated algorithms for matrix computations have been developed over a century, a more recent development is algorithms based on "sampling on the y" from massive matrices. Good estimates of singular values and low rank approximations of the whole matrix can be provably derived from a sample. The main emphasis in the second part of the book is to present these sampling methods with rigorous error bounds. It also presents recent extensions of spectral methods from matrices to tensors and their applications to some combinatorial optimization problems.

 
TCS-025