An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform

DOI10.1145/2483699.2483701zbMath1301.68233arXiv1005.5513OpenAlexW2116019049MaRDI QIDQ2933651

Edo Liberty, Nir Ailon

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 sensingrestricted isometryJohnson-Lindenstrauss

Mathematics Subject Classification ID

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

Related Items (16)

Dimension reduction and construction of feature space for image pattern recognition ⋮ Tighter Fourier Transform Lower Bounds ⋮ Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering ⋮ Sparser Johnson-Lindenstrauss Transforms ⋮ \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\) ⋮ Dimensionality-reduced subspace clustering ⋮ Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma ⋮ Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Fast binary embeddings with Gaussian circulant matrices: improved bounds ⋮ On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms ⋮ Optimal fast Johnson-Lindenstrauss embeddings for large data sets ⋮ Unnamed Item ⋮ The Restricted Isometry Property of Subsampled Fourier Matrices

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