License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.32
URN: urn:nbn:de:0030-drops-82540
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8254/
Freksen, Casper Benjamin ;
Larsen, Kasper Green
On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms
Abstract
The Johnson-Lindenstrauss lemma is one of the corner stone results in dimensionality reduction. It says that given N, for any set of N,
vectors X \subset R^n, there exists a mapping f : X --> R^m such that f(X) preserves all pairwise distances between vectors in X to within(1 ± \eps) if m = O(\eps^{-2} lg N). Much effort has gone into developing
fast embedding algorithms, with the Fast Johnson-Lindenstrauss
transform of Ailon and Chazelle being one of the most well-known
techniques. The current fastest algorithm that yields the optimal m =
O(\eps{-2}lg N) dimensions has an embedding time of O(n lg n + \eps^{-2} lg^3 N). An exciting approach towards improving this, due to Hinrichs and Vybíral, is to use a random m times n Toeplitz matrix for the
embedding. Using Fast Fourier Transform, the embedding of a vector can
then be computed in O(n lg m) time. The big question is of course
whether m = O(\eps^{-2} lg N) dimensions suffice for this technique. If
so, this would end a decades long quest to obtain faster and faster
Johnson-Lindenstrauss transforms. The current best analysis of the
embedding of Hinrichs and Vybíral shows that m = O(\eps^{-2} lg^2 N)
dimensions suffice. The main result of this paper, is a proof that
this analysis unfortunately cannot be tightened any further, i.e.,
there exists a set of N vectors requiring m = \Omega(\eps^{-2} lg^2 N)
for the Toeplitz approach to work.
BibTeX - Entry
@InProceedings{freksen_et_al:LIPIcs:2017:8254,
author = {Casper Benjamin Freksen and Kasper Green Larsen},
title = {{On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {32:1--32:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-054-5},
ISSN = {1868-8969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8254},
URN = {urn:nbn:de:0030-drops-82540},
doi = {10.4230/LIPIcs.ISAAC.2017.32},
annote = {Keywords: dimensionality reduction, Johnson-Lindenstrauss, Toeplitz matrices}
}
|
Keywords: |
|
dimensionality reduction, Johnson-Lindenstrauss, Toeplitz matrices |
|
Collection: |
|
28th International Symposium on Algorithms and Computation (ISAAC 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.12.2017 |
