Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Randomized algorithms in linear algebra

Special Events

Speaker: Ravi Kannan, Microsoft Research, India
Related Webpage:
Location: 1147 MSB
Start time: Fri, Apr 7 2017, 4:10PM

Small random samples of rows and columns of any matrix are sufficient to compute an approximation to the whole matrix as well as solve several other Linear Algebra problems like low-rank approximation, provided, the sampling is done with probabilities proportional to squared lengths. Since the early theorems on length-squared sampling from the 90's, there has been a substantial body of work using sampling (random projections and probabilities based on leverage scores are two examples) to reduce matrix sizes for many computations. The talk will describe theorems, applications and challenges in the area.

This is a joint math/stat colloquium.