Efficient methods for detecting low-rank substructure

Abstract: 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? 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.