Fast Metric Embedding into the Hamming Cube

DOI10.1137/22m1520220arXiv2204.04109OpenAlexW4392812998MaRDI QIDQ6154196

Sjoerd Dirksen, Shahar Mendelson, Alexander Stollenwerk

Publication date: 19 March 2024

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

dimension reductioncirculant matricesHamming cubeJohnson-Lindenstrauss embeddingsGaussian width

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Metric embeddings as related to computational problems and algorithms (68R12)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Fast dimension reduction using Rademacher series on dual BCH codes
• Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• Fast binary embeddings with Gaussian circulant matrices: improved bounds
• Optimal fast Johnson-Lindenstrauss embeddings for large data sets
• Fast and memory-optimal dimension reduction using Kac's walk
• Dimension reduction by random hyperplane tessellations
• Tail bounds via generic chaining
• A sparse Johnson
• Suprema of Chaos Processes and the Restricted Isometry Property
• Computational Advertising: Techniques for Targeting Relevant Ads
• A Quantized Johnson–Lindenstrauss Lemma: The Finding of Buffon’s Needle
• Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
• 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
• Near-Optimal (Euclidean) Metric Compression
• Small Width, Low Distortions: Quantized Random Embeddings of Low-complexity Sets
• Time for dithering: fast and quantized random embeddings via the restricted isometry property
• One-bit compressed sensing with partial Gaussian circulant matrices
• Optimal (Euclidean) Metric Compression
• Numerical linear algebra in the streaming model
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering
• Fast Binary Embeddings and Quantized Compressed Sensing with Structured Matrices
• Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation
• Isometric sketching of any set via the Restricted Isometry Property
• Upper and Lower Bounds for Stochastic Processes
• Column randomization and almost-isometric embeddings
• Sharp Estimates on Random Hyperplane Tessellations
• Robust one-bit compressed sensing with partial circulant matrices