Computer Science NASC Seminar
Efficient Methods for Detecting Lowrank Substructure
Aaditya Rangan, CIMS
February 03, 2012
10:00AM
Warren Weaver Hall, Room 1302
251 Mercer Street
New York, NY, 100121110
(Directions)
Spring 2012 NASC Seminars Calendar
Synopsis
A common goal of dataanalysis is to capture some subset of the data
using a reduced number of degreesoffreedom.
A common step in many matrixcompression algorithms is to represent
portions of a matrix via lowrank approximations.
Both of these methodologies beg the following question: If one is
given a large matrix (or a large collection of vectors) in a
highdimensional space, how can one efficiently determine if some
submatrix (or subset of vectors) admits a lowrank 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.
