Title: Sparser Johnson-Lindenstrauss Transforms
Speaker: Jelani Nelson, Princeton University and the Institute for Advanced Study
Date: Wednesday, March 21, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The Johnson-Lindenstrauss (JL) lemma (1984) states that any n points in d-dimensional Euclidean space can be embedded into k = O((log n)/eps^2) dimensions so that all pairwise distances are preserved up to 1+/-eps. Furthermore, this embedding can be achieved via a linear mapping. The JL lemma is a useful tool for speeding up solutions to several high-dimensional problems: closest pair, nearest neighbor, diameter, minimum spanning tree, etc. It also speeds up some clustering and string processing algorithms, has connections to RIP_2 matrices from compressed sensing, reduces the amount of storage required to store a dataset, and can be used to reduce memory required for numerical linear algebra problems such as linear regression and low rank approximation.
The early proofs of the JL lemma let the linear mapping be specified by a random dense k x d matrix (e.g. i.i.d. Gaussian entries). Thus, performing an embedding required dense matrix-vector multiplication. We give a construction of linear mappings for JL in which only an O(eps)-fraction of the embedding matrix is non-zero, thus speeding up the embedding time. Previous constructions only achieved sparse embedding matrices for 1/eps >> log n.
This is joint work with Daniel Kane (Stanford).