Sparser Johnson-Lindenstrauss Transforms
From MaRDI portal
Publication:3189639
DOI10.1145/2559902zbMath1295.68134arXiv1012.1577OpenAlexW1945899805WikidataQ57253307 ScholiaQ57253307MaRDI QIDQ3189639
Publication date: 12 September 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1012.1577
Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25) Random matrices (probabilistic aspects) (60B20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (47)
Unnamed Item ⋮ Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering ⋮ Sparser Johnson-Lindenstrauss Transforms ⋮ Towards Optimal Moment Estimation in Streaming and Distributed Models ⋮ Upper and Lower Bounds for Dynamic Data Structures on Strings ⋮ Scalable subspace methods for derivative-free nonlinear least-squares optimization ⋮ PLSS: A Projected Linear Systems Solver ⋮ Binary random projections with controllable sparsity patterns ⋮ 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 ⋮ Randomized algorithms in numerical linear algebra ⋮ Distance geometry and data science ⋮ A simple homotopy proximal mapping algorithm for compressive sensing ⋮ \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\) ⋮ Random projections for quadratic programs ⋮ 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 ⋮ Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence ⋮ Dimensionality reduction of SDPs through sketching ⋮ Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. ⋮ Indefinite Proximity Learning: A Review ⋮ Tracking the l_2 Norm with Constant Update Time ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ Deterministic Heavy Hitters with Sublinear Query Time ⋮ 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 ⋮ Randomized LU decomposition using sparse projections ⋮ Random projections for conic programs ⋮ On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms ⋮ The Fast Cauchy Transform and Faster Robust Linear Regression ⋮ Optimal Bounds for Johnson-Lindenstrauss Transformations ⋮ Random Projections for Linear Programming ⋮ Testing and estimating change-points in the covariance matrix of a high-dimensional time series ⋮ Frequent Directions: Simple and Deterministic Matrix Sketching ⋮ Compressed and Penalized Linear Regression ⋮ Dimensionality reduction for \(k\)-distance applied to persistent homology ⋮ High-dimensional model recovery from random sketched data by exploring intrinsic sparsity ⋮ Fast and memory-optimal dimension reduction using Kac's walk ⋮ Estimating Leverage Scores via Rank Revealing Methods and Randomization ⋮ Unnamed Item ⋮ Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares ⋮ Unnamed Item ⋮ ISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A variant of the Johnson-Lindenstrauss lemma for circulant matrices
- Characteristic vectors of bordered matrices with infinite dimensions
- Fast dimension reduction using Rademacher series on dual BCH codes
- The Johnson-Lindenstrauss lemma and the sphericity of some graphs
- Universal classes of hash functions
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Problems and results in extremal combinatorics. I.
- Finding frequent items in data streams
- Derandomized constructions of \(k\)-wise (almost) independent permutations
- An algorithmic theory of learning: Robust concepts and random projection
- A sparse Johnson
- Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
- An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
- Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
- Almost Optimal Explicit Johnson-Lindenstrauss Families
- Johnson-Lindenstrauss lemma for circulant matrices**
- New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
- Low-Rank Approximation and Regression in Input Sparsity Time
- Sparser Johnson-Lindenstrauss Transforms
- Extensions of Lipschitz mappings into a Hilbert space
- An elementary proof of a theorem of Johnson and Lindenstrauss
- Numerical linear algebra in the streaming model
- The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
- Fast moment estimation in data streams in optimal space
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Sparsity lower bounds for dimensionality reducing maps
- A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
This page was built for publication: Sparser Johnson-Lindenstrauss Transforms
