Computer Science NASC Seminar

Efficient Methods for Detecting Low-rank Substructure

Aaditya Rangan, CIMS

February 03, 2012 10:00AM
Warren Weaver Hall, Room 1302
251 Mercer Street
New York, NY, 10012-1110
(Directions)

Spring 2012 NASC Seminars Calendar

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.


top | contact webmaster