Computational Mathematics and Scientific Computing Seminar

---

Efficient Methods for Detecting Low-rank Substructure

Speaker: Aaditya Rangan, CIMS

Location: Warren Weaver Hall 1302

Date: Feb. 3, 2012, 10 a.m.

Synopsis:

A common goal of data-analysis is to capture some subset of the data using a reduced number of degrees-of-freedom. A common step in many matrix-compression algorithms is to represent portions of a matrix via low-rank approximations. Both of these methodologies beg the following question: If one is given a large matrix (or a large collection of vectors) in a high-dimensional space, how can one efficiently determine if some submatrix (or subset of vectors) admits a low-rank representation? Most naive methods for solving this problem are either very slow, or do not scale well as the ambient dimension increases. In this talk I will present a few methods that are fast, even when the ambient dimension is large.