A sparse Johnson
From MaRDI portal
Publication:2875159
DOI10.1145/1806689.1806737zbMath1293.68140OpenAlexW2085927849MaRDI QIDQ2875159
Tamás Sarlós, Ravi Kumar, Anirban Dasgupta
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806737
Computational methods for sparse matrices (65F50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (30)
Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering ⋮ Sparser Johnson-Lindenstrauss Transforms ⋮ Binary random projections with controllable sparsity patterns ⋮ Randomized algorithms in numerical linear algebra ⋮ A simple homotopy proximal mapping algorithm for compressive sensing ⋮ Fast Metric Embedding into the Hamming Cube ⋮ Unnamed Item ⋮ Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers ⋮ Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence ⋮ Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. ⋮ Tracking the l_2 Norm with Constant Update Time ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ 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 ⋮ Sparse random matrices have simple spectrum ⋮ On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms ⋮ Stochastic boundary methods of fundamental solutions for solving PDEs ⋮ Optimal Bounds for Johnson-Lindenstrauss Transformations ⋮ Random Projections for Linear Programming ⋮ Frequent Directions: Simple and Deterministic Matrix Sketching ⋮ Compressed and Penalized Linear Regression ⋮ Tail bounds for gaps between eigenvalues of sparse random matrices ⋮ High-dimensional model recovery from random sketched data by exploring intrinsic sparsity ⋮ Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning ⋮ Estimating Leverage Scores via Rank Revealing Methods and Randomization ⋮ Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares ⋮ Unnamed Item ⋮ Variance reduction in feature hashing using MLE and control variate method ⋮ Tensor-Structured Sketching for Constrained Least Squares
This page was built for publication: A sparse Johnson
