Johnson-Lindenstrauss lemma for circulant matrices**

DOI10.1002/rsa.20360zbMath1230.46019arXiv1001.4919OpenAlexW1535629693WikidataQ125055450 ScholiaQ125055450MaRDI QIDQ3094609

Aicke Hinrichs, Jan Vybíral

Publication date: 25 October 2011

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Johnson-Lindenstrauss lemmaCirculant matrixDimension reduction

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Random matrices (algebraic aspects) (15B52) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85)

Related Items (13)

Compressive Sensing with Redundant Dictionaries and Structured Measurements ⋮ The Quest for Optimal Sampling: Computationally Efficient, Structure-Exploiting Measurements for Compressed Sensing ⋮ Sparser Johnson-Lindenstrauss Transforms ⋮ Suprema of Chaos Processes and the Restricted Isometry Property ⋮ Fast Metric Embedding into the Hamming Cube ⋮ A variant of the Johnson-Lindenstrauss lemma for circulant matrices ⋮ Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma ⋮ On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Compressed sensing with coherent and redundant dictionaries ⋮ Unnamed Item ⋮ On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Estimates of moments and tails of Gaussian chaoses
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Adaptive estimation of a quadratic functional by model selection.
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Extensions of Lipschitz mappings into a Hilbert space
• On variants of the Johnson–Lindenstrauss lemma
• Nearest-neighbor-preserving embeddings
• The best constants in the Khintchine inequality
• An elementary proof of a theorem of Johnson and Lindenstrauss
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables

This page was built for publication: Johnson-Lindenstrauss lemma for circulant matrices**