When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.32
URN: urn:nbn:de:0030-drops-82540
Go to the corresponding LIPIcs Volume Portal

Freksen, Casper Benjamin ; Larsen, Kasper Green

On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms

LIPIcs-ISAAC-2017-32.pdf (0.5 MB)


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

  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 =		{},
  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
Seminar: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 04.12.2017

DROPS-Home | Fulltext Search | Imprint Published by LZI