On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms

DOI10.4230/LIPICS.ISAAC.2017.32MaRDI QIDQ5136251zbMATH OpenFDO

Authors Casper Benjamin Freksen, Kasper Green Larsen

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1706.10110

zbMATH Keywords

dimensionality reductionToeplitz matricesJohnson-Lindenstrauss transform

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Toeplitz, Cauchy, and related matrices (15B05) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Metric embeddings as related to computational problems and algorithms (68R12)

Abstract: 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 $Xsubsetmathbb{R}^n$, there exists a mapping $f:Xomathbb{R}^m$ such that $f(X)$ preserves all pairwise distances between vectors in $X$ to within $(1pmvarepsilon)$ if $m=O(varepsilo{n}^{-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(varepsilo{n}^{-2}lgN)$ dimensions has an embedding time of $O(nlgn+varepsilo{n}^{-2}l{g}^{3}N)$. An exciting approach towards improving this, due to Hinrichs and Vyb'iral, is to use a random $mimesn$ Toeplitz matrix for the embedding. Using Fast Fourier Transform, the embedding of a vector can then be computed in $O(nlgm)$ time. The big question is of course whether $m=O(varepsilo{n}^{-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'iral shows that $m=O(varepsilo{n}^{-2}l{g}^{2}N)$ dimensions suffices. 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(varepsilo{n}^{-2}l{g}^{2}N)$ for the Toeplitz approach to work.

Recommendations

• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• On variants of the Johnson–Lindenstrauss lemma
• Johnson-Lindenstrauss lemma for circulant matrices
• Fast, deterministic and sparse dimensionality reduction
• The Johnson-Lindenstrauss Transform: An Empirical Study

Cites work

• scientific article; zbMATH DE number 2109363 (Why is no real title available?)
• A sparse Johnson-Lindenstrauss transform
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Approximate nearest neighbor: towards removing the curse of dimensionality
• Compressed sensing
• Data streams: algorithms and applications.
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Dimensionality reduction for \(k\)-means clustering and low rank approximation
• Extensions of Lipschitz mappings into a Hilbert space
• Fast dimension reduction using Rademacher series on dual BCH codes
• Graph sparsification by effective resistances
• Johnson-Lindenstrauss lemma for circulant matrices
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sparser Johnson-Lindenstrauss transforms
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors

Cited in

(9)

• Optimal fast Johnson-Lindenstrauss embeddings for large data sets
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• Johnson-Lindenstrauss lemma for circulant matrices
• On binary embedding using circulant matrices
• The Johnson-Lindenstrauss Transform: An Empirical Study
• Faster Johnson-Lindenstrauss transforms via Kronecker products
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Fast and memory-optimal dimension reduction using Kac's walk

This page was built for publication: On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136251)