Title: Theory (and Some Practice) of Randomized Algorithms for Matrices and Data
Speaker: Michael W. Mahoney (Stanford University)

Abstract:
Matrix problems are ubiquitous in many large-scale data 
applications, and in recent years randomization has proved to be 
a valuable resource for the design of better algorithms for many 
of these problems. Depending on the situation, better might mean 
faster in worst-case theory, faster in high-quality numerical 
implementation, e.g., in RAM or in parallel and distributed 
environments, or more useful for downstream domain scientists. 
The talk will describe the theory underlying randomized 
algorithms for matrix problems such as least-squares regression 
and low-rank matrix approximation. Although the use of 
randomization is sometimes a relatively-straightforward 
application of Johnson-Lindenstrauss ideas, Euclidean spaces are 
much more structured objects than general metric spaces, and 
thus the best---both in theory and in numerical analysis and 
data analysis practice---randomized matrix algorithms take this 
into account. An emphasis will be placed on highlighting a few 
key concepts that are responsible for the improvements in worst 
case theory and also for the usefulness of these algorithms in 
large-scale numerical and data applications