Sparser Johnson-Lindenstrauss transforms
From MaRDI portal
Abstract: We give two different and simple constructions for dimensionality reduction in via linear mappings that are sparse: only an -fraction of entries in each column of our embedding matrices are non-zero to achieve distortion with high probability, while still achieving the asymptotically optimal number of rows. These are the first constructions to provide subconstant sparsity for all values of parameters, improving upon previous works of Achlioptas (JCSS 2003) and Dasgupta, Kumar, and Sarl'{o}s (STOC 2010). Such distributions can be used to speed up applications where dimensionality reduction is used.
Recommendations
Cites work
- A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
- A sparse Johnson-Lindenstrauss transform
- A variant of the Johnson-Lindenstrauss lemma for circulant matrices
- Almost Optimal Explicit Johnson-Lindenstrauss Families
- An algorithmic theory of learning: Robust concepts and random projection
- An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
- An elementary proof of a theorem of Johnson and Lindenstrauss
- Approximate nearest neighbor: towards removing the curse of dimensionality
- Characteristic vectors of bordered matrices with infinite dimensions
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Derandomized constructions of \(k\)-wise (almost) independent permutations
- Extensions of Lipschitz mappings into a Hilbert space
- Fast dimension reduction using Rademacher series on dual BCH codes
- Fast moment estimation in data streams in optimal space
- Finding frequent items in data streams
- scientific article; zbMATH DE number 6876120 (Why is no real title available?)
- scientific article; zbMATH DE number 2109363 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- Johnson-Lindenstrauss lemma for circulant matrices
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Modern computer algebra
- New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
- Numerical linear algebra in the streaming model
- Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
- Problems and results in extremal combinatorics. I.
- Sparser Johnson-Lindenstrauss transforms
- Sparsity lower bounds for dimensionality reducing maps
- Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
- The Johnson-Lindenstrauss lemma and the sphericity of some graphs
- Universal classes of hash functions
Cited in
(76)- Dimensionality reduction of SDPs through sketching
- On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
- Fast binary embeddings with Gaussian circulant matrices: improved bounds
- Randomized LU decomposition using sparse projections
- Random projections for conic programs
- Dimensionality reduction for \(k\)-distance applied to persistent homology
- Fast and memory-optimal dimension reduction using Kac's walk
- Distance geometry and data science
- Random projections for quadratic programs
- Testing and estimating change-points in the covariance matrix of a high-dimensional time series
- A simple homotopy proximal mapping algorithm for compressive sensing
- Binary random projections with controllable sparsity patterns
- Frequent directions: simple and deterministic matrix sketching
- A sparse Johnson-Lindenstrauss transform
- Explicit dimension reduction and its applications
- An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- A unified framework for linear dimensionality reduction in L1
- Sparser Johnson-Lindenstrauss transforms
- Upper and lower bounds for dynamic data structures on strings
- Fast sketch-based recovery of correlation outliers
- Compressed and Penalized Linear Regression
- Sparsity and non-Euclidean embeddings
- Randomized algorithms in numerical linear algebra
- Time for dithering: fast and quantized random embeddings via the restricted isometry property
- Fast, deterministic and sparse dimensionality reduction
- Optimal bounds for Johnson-Lindenstrauss transformations
- Robust frequent directions with application in online learning
- Fast cross-polytope locality-sensitive hashing
- Sparse quadratic forms and their geometric applications [following Batson, Spielman, and Srivastava].
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Deterministic heavy hitters with sublinear query time
- ISLET: fast and optimal low-rank tensor regression via importance sketching
- Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
- Real-valued embeddings and sketches for fast distance and similarity estimation
- On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
- Random projections for linear programming
- The Johnson-Lindenstrauss Transform: An Empirical Study
- Simple analyses of the sparse Johnson-Lindenstrauss transform
- Isometric sketching of any set via the restricted isometry property
- An almost optimal unrestricted fast Johnson-Lindenstrauss transform
- Indefinite proximity learning: a review
- Sparsity lower bounds for dimensionality reducing maps
- Sparser Johnson-Lindenstrauss transforms
- Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
- Tracking the l₂ Norm with Constant Update Time
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Johnson–Lindenstrauss Embeddings with Kronecker Structure
- Scalable subspace methods for derivative-free nonlinear least-squares optimization
- PLSS: A Projected Linear Systems Solver
- Tighter guarantees for the compressive multi-layer perceptron
- Towards Optimal Moment Estimation in Streaming and Distributed Models
- Direct Search Based on Probabilistic Descent in Reduced Spaces
- M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
- \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\)
- Fast Metric Embedding into the Hamming Cube
- Fast randomized numerical rank estimation for numerically low-rank matrices
- Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers
- Unsupervised robust discriminative subspace representation based on discriminative approximate isometric embedding
- Random projections for linear programming: an improved retrieval phase
- Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses
- \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
- Random projections for semidefinite programming
- Derandomizing logspace with a small shared hard drive
- Randomly projected convex clustering model: motivation, realization, and cluster recovery guarantees
- Derandomizing logspace with a small shared hard drive
- Random matrices acting on sets: independent columns
- Random projections for curves in high dimensions
- Construction of hierarchically semiseparable matrix representation using adaptive Johnson-Lindenstrauss sketching
- Low-rank approximation algorithm using sparse projection and its applications
- Satisfying the restricted isometry property with the optimal number of rows and slightly less randomness
- A class of sparse Johnson-Lindenstrauss transforms and analysis of their extreme singular values
- Jacobian sparsity detection using Bloom filters
- Capacity analysis of vector symbolic architectures
- Optimal oblivious subspace embeddings with near-optimal sparsity
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
This page was built for publication: Sparser Johnson-Lindenstrauss transforms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189639)
