|
Applied Math Seminar
FAST MATRIX COMPUTATIONS VIA RANDOMIZED SAMPLING
|
|
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 e.g. 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. |