Sparse dimensionality reduction: beyond worst-case analysis

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.