The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
From MaRDI portal
Publication:5189547
DOI10.1137/060673096zbMath1185.68327OpenAlexW2093813380WikidataQ57258817 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
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, 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\)
