A Sparse Johnson--Lindenstrauss Transform

論文紹介

Anirban Dasgupta, Ravi Kumar, Tamás Sarlós
http://arxiv.org/abs/1004.4240

今度のSTOCに出てくる論文．Johnson-Lindenstraussの補題に出てくる射影行列をどれだけ疎にできるのか議論している．ハッシュ関数を使ったシンプルなアルゴリズムだけど，解析が大変だ，という例．