Sparse dimensionality reduction: beyond worst-case analysis

Speaker: Jelani Nelson , Harvard University

Date: Tuesday, February 25, 2014

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Ankur Moitra

Contact: Holly A Jones, hjones01@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/491

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, toc@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Sparse dimensionality reduction: beyond worst-case analysis

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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2013.

Created by Holly A Jones at Wednesday, February 19, 2014 at 10:42 AM.