On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

DOI

The Johnson–Lindenstrauss lemma is one of the cornerstone results in dimensionality reduction. A common formulation of it, is that there exists a random linear mapping f: Rn→ Rm such that for any vector x∈ Rn, f preserves its norm to within (1 ± ε) with probability 1 - δ if m= Θ(ε- 2lg (1 / δ)). 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(ε- 2lg (1 / δ)) dimensions has an embedding time of O(nlg n+ ε- 2lg 3(1 / δ)). 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(nlg m) time. The big question is of course whether m= O(ε- 2lg (1 / δ)) 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(ε- 2lg 2(1 / δ)) dimensions suffice. The main result of this paper, is a proof that this analysis unfortunately cannot be tightened any further, i.e., there exist vectors requiring m= Ω(ε- 2lg 2(1 / δ)) for the Toeplitz approach to work.

OriginalsprogEngelsk
TidsskriftAlgorithmica
Vol/bind82
Nummer2
Sider (fra-til)338-354
Antal sider17
ISSN0178-4617
DOI
StatusUdgivet - 2020

Se relationer på Aarhus Universitet Citationsformater

ID: 181358094