Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

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

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

Freksen, CB & Larsen, KG 2020, 'On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms', *Algorithmica*, vol. 82, no. 2, pp. 338-354. https://doi.org/10.1007/s00453-019-00644-y

Freksen, C. B., & Larsen, K. G. (2020). On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms. *Algorithmica*, *82*(2), 338-354. https://doi.org/10.1007/s00453-019-00644-y

Freksen CB, Larsen KG. 2020. On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms. Algorithmica. 82(2):338-354. https://doi.org/10.1007/s00453-019-00644-y

Freksen, Casper Benjamin and Kasper Green Larsen. "On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms". *Algorithmica*. 2020, 82(2). 338-354. https://doi.org/10.1007/s00453-019-00644-y

Freksen CB, Larsen KG. On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms. Algorithmica. 2020;82(2):338-354. https://doi.org/10.1007/s00453-019-00644-y

Freksen, Casper Benjamin ; Larsen, Kasper Green. / **On Using Toeplitz and Circulant Matrices for Johnson–Lindenstrauss Transforms**. In: Algorithmica. 2020 ; Vol. 82, No. 2. pp. 338-354.

@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",

}

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 -