On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms

DOI10.1007/s00453-019-00644-yzbMath1434.68603OpenAlexW2963884121WikidataQ126842206 ScholiaQ126842206MaRDI QIDQ1986965

Casper Benjamin Freksen, Kasper Green Larsen

Publication date: 9 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00644-y

zbMATH Keywords

Toeplitz matricesdimensionality reductionJohnson-Lindenstrauss transform

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Random matrices (probabilistic aspects) (60B20) 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)

Related Items (1)

Fast Metric Embedding into the Hamming Cube

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Fast dimension reduction using Rademacher series on dual BCH codes
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• A sparse Johnson
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• Computational Advertising: Techniques for Targeting Relevant Ads
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Johnson-Lindenstrauss lemma for circulant matrices**
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Sparser Johnson-Lindenstrauss Transforms
• Extensions of Lipschitz mappings into a Hilbert space
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• An elementary proof of a theorem of Johnson and Lindenstrauss
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Compressed sensing
• Graph Sparsification by Effective Resistances

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