Dense fast random projections and Lean Walsh transforms

DOI10.1007/s00454-010-9309-5zbMath1213.60024OpenAlexW2033143885MaRDI QIDQ629831

Amit Singer, Nir Ailon, Edo Liberty

Publication date: 10 March 2011

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-010-9309-5

zbMATH Keywords

dimension reductionfast random projectionsJohnson-LindenstraussLean Walsh matrices

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Random operators and equations (aspects of stochastic analysis) (60H25) Probability theory on linear topological spaces (60B11)

Related Items (1)

Real-valued embeddings and sketches for fast distance and similarity estimation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A randomized algorithm for the decomposition of matrices
• Faster least squares approximation
• The Mailman algorithm: a note on matrix-vector multiplication
• Fast dimension reduction using Rademacher series on dual BCH codes
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Randomized algorithms for the low-rank approximation of matrices
• Extensions of Lipschitz mappings into a Hilbert space
• On variants of the Johnson–Lindenstrauss lemma
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Sampling algorithms for l₂ regression and applications
• Relative-Error $CUR$ Matrix Decompositions
• Optimized Projections for Compressed Sensing
• Fast computation of low rank matrix approximations
• Compressed sensing

This page was built for publication: Dense fast random projections and Lean Walsh transforms