Toward a unified theory of sparse dimensionality reduction in Euclidean space

EADS Talk by Jelani Nelson, Harvard University, USA


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 (IAS) and Sjoerd Dirksen (RWTH Aachen)

Scientific host: Mikkel Thorup. The talk is open to all interested parties. Registration is not required.

Short Bio of Jelani Nelson

Assistant Professor, Computer Science. Member of the Theory of Computation group at Harvard University.

Previous Positions as Research or postdoctoral fellow at i.a. Institute for Advanced Study Princeton, NJ, Mathematical Sciences Research Institute Berkeley, CA, Microsoft Research New England Cambridge, MA, as well as IBM Almaden Research Center

Teaching includes Advanced Algorithms; Data Structures and Algorithms and Algorithms for Big Data.

More info on research and projects: