Optimal fast Johnson-Lindenstrauss embeddings for large data sets
From MaRDI portal
Publication:2059797
DOI10.1007/s43670-021-00003-5zbMath1479.94054arXiv1712.01774OpenAlexW3138538447MaRDI QIDQ2059797
Felix Krahmer, Stefan Bamberger
Publication date: 14 December 2021
Published in: Sampling Theory, Signal Processing, and Data Analysis (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1712.01774
restricted isometry propertyfast matrix multiplicationJohnson-Lindenstrauss embeddingsHadamard transforms
Analysis of algorithms and problem complexity (68Q25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Randomized algorithms (68W20) Orthogonal matrices (15B10) Informational aspects of data analysis and big data (94A16)
Related Items
Johnson–Lindenstrauss Embeddings with Kronecker Structure, The Hanson-Wright inequality for random tensors, Fast Metric Embedding into the Hamming Cube
Cites Work
- Unnamed Item
- Unnamed Item
- A unified framework for linear dimensionality reduction in L1
- A mathematical introduction to compressive sensing
- Restricted isometries for partial random circulant matrices
- Fast rectangular matrix multiplication and some applications
- A simple proof of the restricted isometry property for random matrices
- Fast dimension reduction using Rademacher series on dual BCH codes
- Embedding \(l_ p^ m\) into \(l_ 1^ n\)
- On the asymptotic complexity of rectangular matrix multiplication
- Fast rectangular matrix multiplication and applications
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Gaussian elimination is not optimal
- Suprema of Chaos Processes and the Restricted Isometry Property
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
- An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
- Extremal Combinatorics
- New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
- Extensions of Lipschitz mappings into a Hilbert space
- On sparse reconstruction from Fourier and Gaussian measurements
- The Restricted Isometry Property of Subsampled Fourier Matrices
- An elementary proof of a theorem of Johnson and Lindenstrauss
- New constructions of RIP matrices with fast multiplication and fewer rows
