# Sparser Johnson-Lindenstrauss Transforms

Thursday, February 16, 2012 - 10:15am - 11:15am

Keller 3-180

Jelani Nelson (Princeton University)

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, 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 original 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 requires dense matrix-vector

multiplication. We give the first construction of linear mappings for

JL in which only a subconstant fraction of the embedding matrix is

non-zero, regardless of how eps and n are related, thus always

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).

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, 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 original 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 requires dense matrix-vector

multiplication. We give the first construction of linear mappings for

JL in which only a subconstant fraction of the embedding matrix is

non-zero, regardless of how eps and n are related, thus always

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).

MSC Code:

20M15

Keywords: