Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
From MaRDI portal
Publication:2931418
DOI10.1145/1132516.1132597zbMath1301.68232WikidataQ57254826 ScholiaQ57254826MaRDI QIDQ2931418
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1132516.1132597
Fourier transform; high-dimensional geometry; approximate nearest neighbor searching; Johnson-Lindenstrauss dimension reduction
68U10: Computing methodologies for image processing
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
94A11: Application of orthogonal and other special functions
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Practical Sketching Algorithms for Low-Rank Matrix Approximation, A Practical Randomized CP Tensor Decomposition, Simple Classification using Binary Data, Optimal Bounds for Johnson-Lindenstrauss Transformations, Estimating Leverage Scores via Rank Revealing Methods and Randomization, Tensor-Structured Sketching for Constrained Least Squares, Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering, Sharper Bounds for Regularized Data Fitting, Fast Private Norm Estimation and Heavy Hitters, Unnamed Item, Johnson–Lindenstrauss Embeddings with Kronecker Structure, Randomized numerical linear algebra: Foundations and algorithms, Principled interpolation of Green's functions learned from data, On fast Johnson-Lindenstrauss embeddings of compact submanifolds of \(\mathbb{R}^N\) with boundary, Sparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation, Algorithmic paradigms for stability-based cluster validity and model selection statistical methods, with applications to microarray data analysis, Detecting low-rank clusters via random sampling, Solving LP using random projections, Faster least squares approximation, A variant of the Johnson-Lindenstrauss lemma for circulant matrices, Dense fast random projections and Lean Walsh transforms, Randomized interpolative decomposition of separated representations, High-dimensional model recovery from random sketched data by exploring intrinsic sparsity, A fast randomized algorithm for the approximation of matrices, The Mailman algorithm: a note on matrix-vector multiplication, Random projections for the nonnegative least-squares problem, Fast dimension reduction using Rademacher series on dual BCH codes, On principal components regression, random projections, and column subsampling, On the mixing time of Kac's walk and other high-dimensional Gibbs samplers with constraints, Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings, Geometric component analysis and its applications to data analysis, Optimal fast Johnson-Lindenstrauss embeddings for large data sets, Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections, Distance geometry and data science, Random projections for quadratic programs, Random projections as regularizers: learning a linear discriminant from fewer observations than dimensions, The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite, Interpolation of Inverse Operators for Preconditioning Parameter-Dependent Equations, Random projections and Hotelling’s T2 statistics for change detection in high-dimensional data streams, Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence, Johnson-Lindenstrauss lemma for circulant matrices**, Randomized Local Model Order Reduction, Classification Scheme for Binary Data with Extensions, Compressed and Penalized Linear Regression, On variants of the Johnson–Lindenstrauss lemma, Random Projection RBF Nets for Multidimensional Density Estimation, Dimension reduction for hyperbolic space