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, Fast Private Norm Estimation and Heavy Hitters, Unnamed Item, 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, 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, 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, On variants of the Johnson–Lindenstrauss lemma, Random Projection RBF Nets for Multidimensional Density Estimation, Dimension reduction for hyperbolic space
