Aarhus University Seal

On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review



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 Rn, there exists a mapping f : X ! Rm such that f(X) preserves all pairwise distances between vectors in X to within (1 ± ϵ) if m = O(ϵ -2 lgN). 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(ϵ -2 lgN) dimensions has an embedding time of O(n lg n + ϵ -2 lg 3 N). An exciting approach towards improving this, due to Hinrichs and Vybíral, is to use a random m×n Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in O(n lgm) time. The big question is of course whether m = O(ϵ -2 lgN) 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(ϵ -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 =(ϵ -2 lg 2 N) for the Toeplitz approach to work.

Translated title of the contributionOm Brugen af Toeplitz og Cirkulære Matricer ved Johnson-Lindenstrauss Transformationer
Original languageEnglish
Title of host publication28th International Symposium on Algorithms and Computation (ISAAC 2017)
EditorsOkamoto Yoshio, Takeshi Tokuyama
Number of pages12
Place of publicationDagstuhl, Germany
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Publication yearDec 2017
Article number32
ISBN (Electronic)978-3-95977-054-5
Publication statusPublished - Dec 2017
Event28th International Symposium on Algorithms and Computation - Cape Panwa Hotel, Phuket, Thailand
Duration: 9 Dec 201712 Dec 2017
Conference number: 28


Conference28th International Symposium on Algorithms and Computation
LocationCape Panwa Hotel
SeriesLeibniz International Proceedings in Informatics

    Research areas

  • Dimensionality reduction, Johnson-lindenstrauss, Toeplitz matrices

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 119594597