Vectors, Sampling and Massive Data

Distinguished Lecture Series
Principal Researcher, Microsoft Research, India; Adjunct Professor of Computer Science, Carnegie Mellon University
Vectors, Sampling and Massive Data
Thursday, October 20, 2011 - 12:00pm
4401, Rashid Auditorium 
Gates Hillman Complex
Abstract:
Modeling data as high-dimensional (feature) vectors is a staple in Computer Science, its use in ranking web pages reminding us again of its effectiveness. Algorithms from Linear Algebra (LA) provide a crucial toolkit. But, for modern problems with massive data, these algorithms may take too long. Random sampling to reduce the size suggests itself. I will give a from-first-principles description of the LA connection, then discuss sampling techniques developed over the last decade for vectors, matrices and graphs. Besides algorithmic efficiency, sampling leads to sparsification and compression of data. Speaker Bio: Ravi Kannan's research areas include Algorithms, Optimization and Probability. He has been on the faculty at CMU, MIT, and was the William Lanman Professor of Computer Science at Yale University before moving to Microsoft Research, India, where he is presently. Among his honors are the 2011 ACM-SIGACT Knuth Prize and the Fulkerson Prize in 1992.
For More Information, Please Contact:

Catherine Copetas, copetas [atsymbol] cs.cmu.edu