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
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
