On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Standard

On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms. / Freksen, Casper Benjamin; Larsen, Kasper Green.

In: Algorithmica, Vol. 82, No. 2, 2020, p. 338-354.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Harvard

APA

CBE

MLA

Vancouver

Author

Bibtex

@article{38bdd96974ef4ff08fd2e4b6f230e223,
title = "On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms",
abstract = "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{\'i}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{\'i}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.",
keywords = "Dimensionality reduction, Johnson–Lindenstrauss, Toeplitz matrices",
author = "Freksen, {Casper Benjamin} and Larsen, {Kasper Green}",
year = "2020",
doi = "10.1007/s00453-019-00644-y",
language = "English",
volume = "82",
pages = "338--354",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York LLC",
number = "2",

}

RIS

TY - JOUR

T1 - On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms

AU - Freksen, Casper Benjamin

AU - Larsen, Kasper Green

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Dimensionality reduction

KW - Johnson–Lindenstrauss

KW - Toeplitz matrices

UR - http://www.scopus.com/inward/record.url?scp=85074731709&partnerID=8YFLogxK

U2 - 10.1007/s00453-019-00644-y

DO - 10.1007/s00453-019-00644-y

M3 - Journal article

AN - SCOPUS:85074731709

VL - 82

SP - 338

EP - 354

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 2

ER -