On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms

DOI10.4230/LIPICS.ISAAC.2017.32zbMATH Open1457.68288arXiv1706.10110MaRDI QIDQ5136251FDOQ5136251

Authors: Casper Benjamin Freksen, Kasper Green Larsen 

Publication date: 25 November 2020

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.

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

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

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)

Cites Work

• Extensions of Lipschitz mappings into a Hilbert space
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Fast dimension reduction using Rademacher series on dual BCH codes
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Title not available (Why is that?)
• Graph Sparsification by Effective Resistances
• Data streams: algorithms and applications.
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Approximate nearest neighbor: towards removing the curse of dimensionality
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Johnson-Lindenstrauss lemma for circulant matrices
• A sparse Johnson-Lindenstrauss transform
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Sparser Johnson-Lindenstrauss Transforms
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

Cited In (4)

• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• The Johnson-Lindenstrauss Transform: An Empirical Study
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• Johnson-Lindenstrauss lemma for circulant matrices

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)