Computer Science NASC Seminar
Efficient Methods for Detecting Low-rank Substructure
Aaditya Rangan, CIMS
February 03, 2012
Warren Weaver Hall, Room 1302
251 Mercer Street
New York, NY, 10012-1110
Spring 2012 NASC Seminars Calendar
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
scale well as the ambient dimension increases. In this talk I will
present a few methods that are fast, even when the ambient dimension