An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform

DOI10.1145/2483699.2483701MaRDI QIDQ2933651zbMATH OpenOpenAlexFDO

Authors Nir Ailon, Edo Liberty

Publication date 5 December 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

compressed sensingJohnson-Lindenstraussrestricted isometry

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies for image processing (68U10) Application of orthogonal and other special functions (94A11)

Abstract: The problems of random projections and sparse reconstruction have much in common and individually received much attention. Surprisingly, until now they progressed in parallel and remained mostly separate. Here, we employ new tools from probability in Banach spaces that were successfully used in the context of sparse reconstruction to advance on an open problem in random pojection. In particular, we generalize and use an intricate result by Rudelson and Vershynin for sparse reconstruction which uses Dudley's theorem for bounding Gaussian processes. Our main result states that any set of $N=exp(ildeO(n))$ real vectors in $n$ dimensional space can be linearly mapped to a space of dimension $k=O(logNpolylog(n))$, while (1) preserving the pairwise distances among the vectors to within any constant distortion and (2) being able to apply the transformation in time $O(nlogn)$ on each vector. This improves on the best known $N=exp(ildeO(n^{1/2}))$ achieved by Ailon and Liberty and $N=exp(ildeO(n^{1/3}))$ by Ailon and Chazelle. The dependence in the distortion constant however is believed to be suboptimal and subject to further investigation. For constant distortion, this settles the open question posed by these authors up to a $polylog(n)$ factor while considerably simplifying their constructions.

Recommendations

• An almost optimal unrestricted fast Johnson-Lindenstrauss transform
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• Faster Johnson-Lindenstrauss transforms via Kronecker products
• Optimal bounds for Johnson-Lindenstrauss transformations
• The Johnson-Lindenstrauss Transform: An Empirical Study
• A sparse Johnson-Lindenstrauss transform
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Sparser Johnson-Lindenstrauss transforms
• Sparser Johnson-Lindenstrauss transforms
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument

Cited in

(29)

• 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
• A sparse Johnson-Lindenstrauss transform
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
• Dimension reduction and construction of feature space for image pattern recognition
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• Sparser Johnson-Lindenstrauss transforms
• Tighter Fourier transform lower bounds
• Dense Fast Random Projections and Lean Walsh Transforms
• Dimensionality-reduced subspace clustering
• Fast, deterministic and sparse dimensionality reduction
• Optimal bounds for Johnson-Lindenstrauss transformations
• Robust frequent directions with application in online learning
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• Real-valued embeddings and sketches for fast distance and similarity estimation
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• The Johnson-Lindenstrauss Transform: An Empirical Study
• Simple analyses of the sparse Johnson-Lindenstrauss transform
• An almost optimal unrestricted fast Johnson-Lindenstrauss transform
• \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\)
• Dense fast random projections and Lean Walsh transforms
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
• Dynamics-preserving compression for modal flow analysis
• Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024
• Randomly projected convex clustering model: motivation, realization, and cluster recovery guarantees

This page was built for publication: An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform

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