Database-friendly random projections: Johnson-Lindenstrauss with binary coins

2003/06/01 by Dimitris Achlioptas · 67 citations
Computer Science · #Data Management and Algorithms #Computational Geometry and Mesh Generation #Advanced Image and Video Retrieval Techniques

paper · doi:10.1016/s0022-0000(03)00025-4

Cited by

• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace\n embeddings
• Sparse, Dense, and Attentional Representations for Text Retrieval
• Efficient Planning under Partial Observability with Unnormalized Q Functions and Spectral Learning
• A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations
• Efficient Second Order Online Learning by Sketching
• Deep Fried Convnets
• Statistical optimality conditions for compressive ensembles
• Tensor Random Projection for Low Memory Dimension Reduction
• Analysis of SparseHash: an efficient embedding of set-similarity via\n sparse projections
• Compressive Sensing with Redundant Dictionaries and Structured\n Measurements
• Effective and Sparse Count-Sketch via k-means clustering
• Role Similarity Metric Based on Spanning Rooted Forest
• Johnson-Lindenstrauss lemma for circulant matrices
• Randomized Gram--Schmidt Process with Application to GMRES
• Binarized Johnson-Lindenstrauss embeddings
• Random projections for linear programming
• Fast approximation of matrix coherence and statistical leverage
• Chernoff-Hoeffding Inequality and Applications
• Beyond Attributes: Adversarial Erasing Embedding Network for Zero-shot Learning
• Algorithms and Hardness for Linear Algebra on Geometric Graphs
• Near-Optimal Compression for the Planar Graph Metric
• Blazed oblique plane microscopy reveals scale-invariant inference of brain-wide population activity
• A Sparse Johnson--Lindenstrauss Transform
• Randomized algorithms for matrices and data
• Acceleration of Randomized Kaczmarz Method via the Johnson-Lindenstrauss\n Lemma
• Neural Random Projections for Language Modelling
• The GaussianSketch for Almost Relative Error Kernel Distance
• Scalable Initialization Methods for Large-Scale Clustering
• Feature Hashing for Large Scale Multitask Learning
• Semi-supervised Embedding Learning for High-dimensional Bayesian Optimization
• Predicting Training Time Without Training
• Application of Compressive Sensing Techniques in Distributed Sensor Networks: A Survey
• Winner-Take-All Computation in Spiking Neural Networks
• Notes on Randomized Algorithms
• Very Sparse Stable Random Projections, Estimators and Tail Bounds for Stable Random Projections
• Scaling Up Collaborative Filtering Data Sets through Randomized Fractal Expansions
• Structure-aware error bounds for linear classification with the zero-one loss
• Sparsity Lower Bounds for Dimensionality Reducing Maps
• Quantization Algorithms for Random Fourier Features
• Random Sampling for Distributed Coded Matrix Multiplication
• Hashing Algorithms for Large-Scale Learning
• Similarity preserving compressions of high dimensional sparse data
• Improved Practical Matrix Sketching with Guarantees
• Learning Latent Factors From Diversified Projections and Its Applications to Over-Estimated and Weak Factors
• Sub-linear Memory Sketches for Near Neighbor Search on Streaming Data
• Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
• Recipes for stable linear embeddings from Hilbert spaces to R^m
• On Learning from Ghost Imaging without Imaging
• Exploring Embedding Methods in Binary Hyperdimensional Computing: A Case Study for Motor-Imagery based Brain-Computer Interfaces
• Near neighbor preserving dimension reduction for doubling subsets of ℓ₁
• Stable Takens' Embeddings for Linear Dynamical Systems
• Optimized Kernel-based Projection Space of Riemannian Manifolds
• Sketching Datasets for Large-Scale Learning (long version)
• Random Projections for Linear Support Vector Machines
• ADAGIO: Fast Data-aware Near-Isometric Linear Embeddings
• Almost Optimal Explicit Johnson-Lindenstrauss Transformations
• Mixed Compressed Sensing Based on Random Graphs
• (2+ε)-ANN for time series under the Fréchet distance
• Particle systems and kinetic equations modeling interacting agents in\n high dimension
• Greedy type algorithms for RIP matrices. A study of two selection rules
• Incomplete Pivoted QR-based Dimensionality Reduction
• List-Decodable Mean Estimation in Nearly-PCA Time
• An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration
• Johnson–Lindenstrauss lemma [wikipedia]