Low dimensional embedding with compressed, incomplete and inaccurate measurements

Start: 03/02/2011 - 4:15pm
End  : 03/02/2011 - 5:00pm


Blake Hunter (University of California, Davis)


As the size and complexity of data continues to grow, extracting knowledge becomes
exponentially more challenging. Active areas of research for mining this high dimensional
data can be found across a broad range of scientific fields including pure and applied math-
ematics, statistics, computer science and engineering. Spectral embedding is one of the
most powerful and widely used techniques for extracting the underlying global structure of
a data set. Compressed sensing and matrix completion have emerged as prevailing methods
for efficiently recovering sparse and partially observed signals. In this talk, we combine the
distance preserving measurements of compressed sensing and matrix completion with the
robust power of spectral embedding. Our analysis provides rigorous bounds on how small
perturbations from using compressed sensing and matrix completion affect the affinity ma-
trix and in succession the spectral coordinates.
Theoretical guarantees are complemented with numerical results. A number of examples
of the unsupervised organization and clustering of synthetic and real world image data are
also shown.

Roberts North 15, Claremont McKenna College