Aarhus University Seal / Aarhus Universitets segl

MADALGO Seminar

MADALGO Theory Seminar: Jelani Nelson (Harvard University)

2015.05.28 | Katrine Østerlund Rasmussen

Date Wed 10 Jun
Time 14:15 15:00
Location Building 5335, Nygaard-327

Title
Toward a unified theory of sparse dimensionality reduction in Euclidean space 

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