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.