Sparser Johnson-Lindenstrauss transforms

zbMATH Open1423.68213MaRDI QIDQ5743469FDOQ5743469

Authors: Daniel M. Kane, Jelani Nelson 

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095210

Recommendations

• Sparser Johnson-Lindenstrauss transforms
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• A sparse Johnson-Lindenstrauss transform
• Sparsity lower bounds for dimensionality reducing maps
• Fast, deterministic and sparse dimensionality reduction

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Random matrices (probabilistic aspects) (60B20) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Extensions of Lipschitz mappings into a Hilbert space
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Fast dimension reduction using Rademacher series on dual BCH codes
• Numerical linear algebra in the streaming model
• Title not available (Why is that?)
• Universal classes of hash functions
• Finding frequent items in data streams
• Title not available (Why is that?)
• Fast moment estimation in data streams in optimal space
• A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
• Title not available (Why is that?)
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• On variants of the Johnson–Lindenstrauss lemma
• Modern computer algebra
• Tabulation based 4-universal hashing with applications to second moment estimation
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• Johnson-Lindenstrauss lemma for circulant matrices
• A sparse Johnson-Lindenstrauss transform
• An algorithmic theory of learning: Robust concepts and random projection
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• An almost optimal unrestricted fast Johnson-Lindenstrauss transform
• Title not available (Why is that?)
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error

Cited In (20)

• Sparser Johnson-Lindenstrauss transforms
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Nearly tight oblivious subspace embeddings by trace inequalities
• A sparse Johnson-Lindenstrauss transform
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
• An almost optimal unrestricted fast Johnson-Lindenstrauss transform
• New bounds for circulant Johnson-Lindenstrauss embeddings
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Optimal fast Johnson-Lindenstrauss embeddings for large data sets
• Simple analyses of the sparse Johnson-Lindenstrauss transform
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• The Johnson-Lindenstrauss Transform: An Empirical Study
• Fast, deterministic and sparse dimensionality reduction
• Sparsity lower bounds for dimensionality reducing maps
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Johnson-Lindenstrauss lemma for circulant matrices
• Title not available (Why is that?)

This page was built for publication: Sparser Johnson-Lindenstrauss transforms

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