Fast Dimension Reduction

We discussed the Johnson-Lindenstrauss lemma in class, where we mapped n points in d dimensions, to points in a k-dimensional space (with k = O(log n)) while approximately preserving the distances.

However, the mapping which multiplied a point u by a matrix G, is expensive to compute since G is a matrix in which almost all entries are non-zero. There has been a lot of research in coming up with mappings which can be computed much faster. In particular, one way is to come up with a sparse matrix G’, so that the mapping still preserves distances approximately, but the matrix-vector product G’u can be ¬†computed much faster.

Here is an excelled talk summarizing many of the recent developments in this area:


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s