skip to content

On the approximation of quadratic forms and sparse matrix products

Tuesday 3rd June 2008 - 11:00 to 12:00
INI Seminar Room 1

Thus far, sparse representations have been exploited largely in the context of robustly estimating functions in a noisy environment from a few measurements. In this context, the existence of a basis in which the signal class under consideration is sparse is used to decrease the number of necessary measurements while controlling the approximation error. In this talk, we instead focus on sparse representations of linear operators, with the objective of minimizing the number of operations required to perform basic operations (here, multiplication) on their matrix representations. We employ a representation in terms of sums of rank-one operators, and show how solving a sparse approximation problem akin to model selection for an induced quadratic form in turn guarantees a bounded approximation error for the product of two matrices. Connections to multilinear algebra by way of exterior products in turn yield new randomized algorithms for this and other tasks involving the large matrices and high-dimensional covariance operators that arise in modern statistical practice.

(joint work with Mohamed-Ali Belabbas)

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons