Sparse dimensionality reduction: beyond worst-case analysis

Tuesday, February 25, 2014 - 4:15pm to 5:15pm
3:45pm in 32-G449 (Patil/Kiva)
Jelani Nelson, Harvard University

Abstract: This talk will discuss sparse Johnson-Lindenstrauss
transforms, i.e. sparse linear maps into much lower dimension which
preserve the Euclidean geometry of a set of vectors. We derive upper
bounds on the sufficient target dimension and sparsity of the
projection matrix to achieve good dimensionality reduction. Our bounds
depend on the geometry of the set of vectors, moving us away from
worst-case analysis and toward instance-optimality.

Joint work with Jean Bourgain.