Optimal fast Johnson-Lindenstrauss embeddings for large data sets

DOI10.1007/S43670-021-00003-5zbMATH Open1479.94054arXiv1712.01774OpenAlexW3138538447MaRDI QIDQ2059797FDOQ2059797

Felix Krahmer, Stefan Bamberger

Publication date: 14 December 2021

Published in: Sampling Theory, Signal Processing, and Data Analysis (Search for Journal in Brave)

Abstract: Johnson-Lindenstrauss embeddings are widely used to reduce the dimension and thus the processing time of data. To reduce the total complexity, also fast algorithms for applying these embeddings are necessary. To date, such fast algorithms are only available either for a non-optimal embedding dimension or up to a certain threshold on the number of data points. We address a variant of this problem where one aims to simultaneously embed larger subsets of the data set. Our method follows an approach by Nelson: A subsampled Hadamard transform maps points into a space of lower, but not optimal dimension. Subsequently, a random matrix with independent entries projects to an optimal embedding dimension. For subsets whose size scales at least polynomially in the ambient dimension, the complexity of this method comes close to the number of operations just to read the data under mild assumptions on the size of the data set that are considerably less restrictive than in previous works. We also prove a lower bound showing that subsampled Hadamard matrices alone cannot reach an optimal embedding dimension. Hence, the second embedding cannot be omitted.

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

Recommendations

• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• The Johnson-Lindenstrauss Transform: An Empirical Study
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• Fast, deterministic and sparse dimensionality reduction
• Sparser Johnson-Lindenstrauss transforms

zbMATH Keywords

restricted isometry propertyfast matrix multiplicationJohnson-Lindenstrauss embeddingsHadamard transforms

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Orthogonal matrices (15B10) Informational aspects of data analysis and big data (94A16)

Cites Work

• Extensions of Lipschitz mappings into a Hilbert space
• An elementary proof of a theorem of Johnson and Lindenstrauss
• A simple proof of the restricted isometry property for random matrices
• Fast dimension reduction using Rademacher series on dual BCH codes
• A mathematical introduction to compressive sensing
• Gaussian elimination is not optimal
• Title not available (Why is that?)
• Title not available (Why is that?)
• On sparse reconstruction from Fourier and Gaussian measurements
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Suprema of chaos processes and the restricted isometry property
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• New constructions of RIP matrices with fast multiplication and fewer rows
• Extremal Combinatorics
• A unified framework for linear dimensionality reduction in L1
• Restricted isometries for partial random circulant matrices
• Fast rectangular matrix multiplication and applications
• Embedding \(l_ p^ m\) into \(l_ 1^ n\)
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Fast rectangular matrix multiplication and some applications
• On the asymptotic complexity of rectangular matrix multiplication
• The Restricted Isometry Property of Subsampled Fourier Matrices

Cited In (3)

• Fast Metric Embedding into the Hamming Cube
• The Hanson-Wright inequality for random tensors
• Johnson–Lindenstrauss Embeddings with Kronecker Structure

This page was built for publication: Optimal fast Johnson-Lindenstrauss embeddings for large data sets

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