Randomized Algorithms in Linear Algebra and the Column Subset Selection Problem

April 4, 2012

ABSTRACT:

The introduction of randomization in the design and analysis of algorithms for matrix computations (such as matrix multiplication, least-squares regression, the Singular Value Decomposition (SVD), etc.) over the last decade provided a new paradigm and a complementary perspective to traditional numerical linear algebra approaches. These novel approaches were motivated by technological developments in many areas of scientific research that permit the automatic generation of large data sets, which are often modeled as matrices. In this talk we will outline how such approaches can be used to approximately solve the so-called Column Subset Selection Problem, namely the problem of selecting a subset of "representative" columns from a matrix.

The introduction of randomization in the design and analysis of algorithms for matrix computations (such as matrix multiplication, least-squares regression, the Singular Value Decomposition (SVD), etc.) over the last decade provided a new paradigm and a complementary perspective to traditional numerical linear algebra approaches. These novel approaches were motivated by technological developments in many areas of scientific research that permit the automatic generation of large data sets, which are often modeled as matrices. In this talk we will outline how such approaches can be used to approximately solve the so-called Column Subset Selection Problem, namely the problem of selecting a subset of "representative" columns from a matrix.