Fast Metric Embedding into the Hamming Cube

DOI10.1137/22M1520220MaRDI QIDQ6154196zbMATH OpenOpenAlexFDO

Authors 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

circulant matricesdimension reductionGaussian widthHamming cubeJohnson-Lindenstrauss embeddings

Mathematics Subject Classification ID

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

Abstract: We consider the problem of embedding a subset of $mathbb{R}^n$ into a low-dimensional Hamming cube in an almost isometric way. We construct a simple, data-oblivious, and computationally efficient map that achieves this task with high probability: we first apply a specific structured random matrix, which we call the double circulant matrix; using that matrix requires linear storage and matrix-vector multiplication can be performed in near-linear time. We then binarize each vector by comparing each of its entries to a random threshold, selected uniformly at random from a well-chosen interval. We estimate the number of bits required for this encoding scheme in terms of two natural geometric complexity parameters of the set - its Euclidean covering numbers and its localized Gaussian complexity. The estimate we derive turns out to be the best that one can hope for - up to logarithmic terms. The key to the proof is a phenomenon of independent interest: we show that the double circulant matrix mimics the behavior of a Gaussian matrix in two important ways. First, it maps an arbitrary set in $mathbb{R}^n$ into a set of well-spread vectors. Second, it yields a fast near-isometric embedding of any finite subset of $el{l}_2^n$ into $el{l}_1^m$. This embedding achieves the same dimension reduction as a Gaussian matrix in near-linear time, under an optimal condition - up to logarithmic factors - on the number of points to be embedded. This improves a well-known construction due to Ailon and Chazelle.

Cites work

• A Quantized Johnson–Lindenstrauss Lemma: The Finding of Buffon’s Needle
• A sparse Johnson-Lindenstrauss transform
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Approximate nearest neighbor: towards removing the curse of dimensionality
• Column randomization and almost-isometric embeddings
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Dimension reduction by random hyperplane tessellations
• Extensions of Lipschitz mappings into a Hilbert space
• Fast and memory-optimal dimension reduction using Kac's walk
• Fast binary embeddings and quantized compressed sensing with structured matrices
• Fast binary embeddings with Gaussian circulant matrices: improved bounds
• Fast dimension reduction using Rademacher series on dual BCH codes
• scientific article; zbMATH DE number 5485498 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
• Isometric sketching of any set via the restricted isometry property
• Johnson-Lindenstrauss lemma for circulant matrices
• Near-optimal (Euclidean) metric compression
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Numerical linear algebra in the streaming model
• On binary embedding using circulant matrices
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• One-bit compressed sensing with partial Gaussian circulant matrices
• Optimal (Euclidean) Metric Compression
• Optimal fast Johnson-Lindenstrauss embeddings for large data sets
• Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering
• Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
• Robust one-bit compressed sensing with partial circulant matrices
• Sharp Estimates on Random Hyperplane Tessellations
• Sketching as a tool for numerical linear algebra
• Small Width, Low Distortions: Quantized Random Embeddings of Low-complexity Sets
• Sparser Johnson-Lindenstrauss transforms
• Streaming low-rank matrix approximation with an application to scientific simulation
• Suprema of chaos processes and the restricted isometry property
• Tail bounds via generic chaining
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• Time for dithering: fast and quantized random embeddings via the restricted isometry property
• Upper and lower bounds for stochastic processes. Modern methods and classical problems

This page was built for publication: Fast Metric Embedding into the Hamming Cube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154196)