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

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