Abstract
The JohnsonLindenstrauss 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 JohnsonLindenstrauss
transform of Ailon and Chazelle being one of the most wellknown
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
JohnsonLindenstrauss 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 JohnsonLindenstrauss Transforms}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {32:132:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8254},
URN = {urn:nbn:de:0030drops82540},
doi = {10.4230/LIPIcs.ISAAC.2017.32},
annote = {Keywords: dimensionality reduction, JohnsonLindenstrauss, Toeplitz matrices}
}
Keywords: 

dimensionality reduction, JohnsonLindenstrauss, Toeplitz matrices 
Collection: 

28th International Symposium on Algorithms and Computation (ISAAC 2017) 
Issue Date: 

2017 
Date of publication: 

07.12.2017 