On variants of the Johnson–Lindenstrauss lemma
From MaRDI portal
Publication:3522833
DOI10.1002/rsa.20218zbMath1154.51002OpenAlexW3147249397WikidataQ124888350 ScholiaQ124888350MaRDI QIDQ3522833
Publication date: 4 September 2008
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20218
dimension reductionmoment generating functionlow-distortion embeddingsJohnson-Lindenstrauss Lemmasubgaussian tail
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) General theory of distance geometry (51K05) Euclidean geometries (general) and generalizations (51M05)
Related Items (max. 100)
On principal components regression, random projections, and column subsampling ⋮ Binary vectors for fast distance and similarity estimation ⋮ Dimension reduction and construction of feature space for image pattern recognition ⋮ Gaussian random projections for Euclidean membership problems ⋮ A Survey of Compressed Sensing ⋮ Neural network approximation of continuous functions in high dimensions with applications to inverse problems ⋮ Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification ⋮ Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations ⋮ Distance geometry and data science ⋮ Faster least squares approximation ⋮ \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\) ⋮ A variant of the Johnson-Lindenstrauss lemma for circulant matrices ⋮ Modewise operators, the tensor restricted isometry property, and low-rank tensor recovery ⋮ Dense fast random projections and Lean Walsh transforms ⋮ Random projections of linear and semidefinite problems with linear inequalities ⋮ Hypercontractivity via tensor calculus ⋮ Indexability, concentration, and VC theory ⋮ Linear dimension reduction approximately preserving a function of the $1$-norm ⋮ Convexity of the image of a quadratic map via the relative entropy distance ⋮ Structure from Randomness in Halfspace Learning with the Zero-One Loss ⋮ A partitioned quasi-likelihood for distributed statistical inference ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ On orthogonal projections for dimension reduction and applications in augmented target loss functions for learning problems ⋮ Dimensionality reduction with subgaussian matrices: a unified theory ⋮ Unnamed Item ⋮ Fast Parallel Estimation of High Dimensional Information Theoretical Quantities with Low Dimensional Random Projection Ensembles ⋮ Unnamed Item ⋮ Optimal Bounds for Johnson-Lindenstrauss Transformations ⋮ A survey on unsupervised outlier detection in high‐dimensional numerical data ⋮ Random Projections for Linear Programming ⋮ Almost Optimal Explicit Johnson-Lindenstrauss Families ⋮ Sampled Tikhonov regularization for large linear inverse problems ⋮ Johnson-Lindenstrauss lemma for circulant matrices** ⋮ Dimensionality reduction for \(k\)-distance applied to persistent homology ⋮ Fast dimension reduction using Rademacher series on dual BCH codes ⋮ Unnamed Item ⋮ On the perceptron's compression ⋮ Random projections and Hotelling’s T2 statistics for change detection in high-dimensional data streams ⋮ Why Are Big Data Matrices Approximately Low Rank? ⋮ Random projections as regularizers: learning a linear discriminant from fewer observations than dimensions
Cites Work
- Unnamed Item
- The Johnson-Lindenstrauss lemma and the sphericity of some graphs
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Problems and results in extremal combinatorics. I.
- Empirical processes and random projections
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
- Extensions of Lipschitz mappings into a Hilbert space
- On the impossibility of dimension reduction in l 1
- Projection constants of symmetric spaces and variants of Khintchine's inequality
- An elementary proof of a theorem of Johnson and Lindenstrauss
This page was built for publication: On variants of the Johnson–Lindenstrauss lemma
