Per-Gunnar Martinsson
Department of Applied Mathematics
University of Colorado
Boulder, Colorado, USA
The talk will describe a set of techniques based on randomized
sampling that dramatically accelerate several key matrix
computations, including many needed for solving partial differential
equations and for extracting information from large data-sets (such
as those arising from genomics, the link structure of the World Wide
Web, etc). The algorithms are applicable to any matrix that can in
principle be approximated by a low-rank matrix, are as accurate as
deterministic methods, and are for practical purposes 100% reliable
(the risk of "failure" can easily be rendered less than 1e-12).
Connections between this work and other randomized algorithms will be discussed; in particular the connection to recent work in functional analysis and probability theory (by Johnson and Lindenstrauss, Bourgain, and others) utilizing random projections to embed objects into low-dimensional Euclidean spaces, while preserving important geometrical properties of the objects.