The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
From MaRDI portal
Publication:5189547
DOI10.1137/060673096zbMath1185.68327DBLPjournals/siamcomp/AilonC09OpenAlexW2093813380WikidataQ57258817 ScholiaQ57258817MaRDI QIDQ5189547
Publication date: 17 March 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/060673096
Related Items (76)
Binary vectors for fast distance and similarity estimation ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Matrix sketching for supervised classification with imbalanced classes ⋮ Spectral estimation from simulations via sketching ⋮ Tighter Fourier Transform Lower Bounds ⋮ Compressive Sensing with Redundant Dictionaries and Structured Measurements ⋮ Sparser Johnson-Lindenstrauss Transforms ⋮ On the convergence to equilibrium of Kac's random walk on matrices ⋮ Filament plots for data visualization ⋮ An efficient algorithm for computing the approximate t-URV and its applications ⋮ Optimal (Euclidean) Metric Compression ⋮ Sketched Newton--Raphson ⋮ Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument ⋮ RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression ⋮ PLSS: A Projected Linear Systems Solver ⋮ Binary random projections with controllable sparsity patterns ⋮ Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification ⋮ Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations ⋮ Random design analysis of ridge regression ⋮ Randomized LU decomposition ⋮ Principled interpolation of Green's functions learned from data ⋮ Generalized linear models for massive data via doubly-sketching ⋮ Norms of structured random matrices ⋮ Practical Sketching Algorithms for Low-Rank Matrix Approximation ⋮ Lipschitz geometry of operator spaces and Lipschitz-free operator spaces ⋮ \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\) ⋮ An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs ⋮ Fast Metric Embedding into the Hamming Cube ⋮ On randomized sketching algorithms and the Tracy-Widom law ⋮ A variant of the Johnson-Lindenstrauss lemma for circulant matrices ⋮ Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers ⋮ Compressed sensing of low-rank plus sparse matrices ⋮ Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition ⋮ Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma ⋮ On deterministic sketching and streaming for sparse recovery and norm estimation ⋮ Paved with good intentions: analysis of a randomized block Kaczmarz method ⋮ Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces ⋮ Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. ⋮ Linear dimension reduction approximately preserving a function of the $1$-norm ⋮ On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ Constructing a High-Dimensional k NN-Graph Using a Z-Order Curve ⋮ Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1 ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ Forecasting using random subspace methods ⋮ On Geometric Prototype and Applications ⋮ On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Fast binary embeddings with Gaussian circulant matrices: improved bounds ⋮ Dimension reduction by random hyperplane tessellations ⋮ User-friendly tail bounds for sums of random matrices ⋮ Compressed sensing with coherent and redundant dictionaries ⋮ Randomized LU decomposition using sparse projections ⋮ Constructing low-rank Tucker tensor approximations using generalized completion ⋮ Fast randomized matrix and tensor interpolative decomposition using countsketch ⋮ Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten \(p\)-norms ⋮ Stochastic iterative projection methods for large linear systems ⋮ Correlations between random projections and the bivariate normal ⋮ Stochastic quasi-gradient methods: variance reduction via Jacobian sketching ⋮ Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme ⋮ On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms ⋮ The Fast Cauchy Transform and Faster Robust Linear Regression ⋮ An efficient randomized algorithm for computing the approximate Tucker decomposition ⋮ Paraunitary matrices, entropy, algebraic condition number and Fourier computation ⋮ Almost Optimal Explicit Johnson-Lindenstrauss Families ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ Johnson-Lindenstrauss lemma for circulant matrices** ⋮ Compressed dictionary learning ⋮ Dimensionality reduction for \(k\)-distance applied to persistent homology ⋮ Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation ⋮ High-dimensional model recovery from random sketched data by exploring intrinsic sparsity ⋮ Fast and memory-optimal dimension reduction using Kac's walk ⋮ The Restricted Isometry Property of Subsampled Fourier Matrices ⋮ Unnamed Item ⋮ Randomized partition trees for nearest neighbor search ⋮ Dominance Product and High-Dimensional Closest Pair under L_infty ⋮ Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\)
This page was built for publication: The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
