Aarhus University Seal

MADALGO Seminar

MADALGO Theory Seminar: Jelani Nelson (Harvard University)

Info about event

Time

Wednesday 10 June 2015,  at 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)