An elementary proof of a theorem of Johnson and Lindenstrauss
From MaRDI portal
Publication:4798181
DOI10.1002/rsa.10073zbMath1018.51010OpenAlexW2088658556WikidataQ56115767 ScholiaQ56115767MaRDI QIDQ4798181
Publication date: 19 March 2003
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.10073
Related Items
Johnson–Lindenstrauss Embeddings with Kronecker Structure, Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits, Towards Practical Large-Scale Randomized Iterative Least Squares Solvers through Uncertainty Quantification, An Outer-Product-of-Gradient Approach to Dimension Reduction and its Application to Classification in High Dimensional Space, A preconditioned iterative interior point approach to the conic bundle subproblem, Stable probability of reduced matrix obtained by Gaussian random projection, \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\), On fast Johnson-Lindenstrauss embeddings of compact submanifolds of \(\mathbb{R}^N\) with boundary, Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers, The effect of intrinsic dimension on the Bayes-error of projected quadratic discriminant classification, Distributed estimation and inference for spatial autoregression model with large scale networks, On the distance to low-rank matrices in the maximum norm, Visual Categorization with Random Projection, Uniform Error Estimates for the Lanczos Method, Partitioning Well-Clustered Graphs: Spectral Clustering Works!, Random Projections for Linear Programming, Quasi-linear Compressed Sensing, Unnamed Item, Conservative confidence intervals on multiple correlation coefficient for high-dimensional elliptical data using random projection methodology, Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections, Sampling quantum nonlocal correlations with high probability, Deterministic Truncation of Linear Matroids, Exponential random graphs behave like mixtures of stochastic block models, Gaussian random projections for Euclidean membership problems, A unified framework for linear dimensionality reduction in L1, Dimension reduction in vertex-weighted exponential random graphs, Compressive Sensing with Redundant Dictionaries and Structured Measurements, Fast Phase Retrieval from Local Correlation Measurements, Random fusion frames are nearly equiangular and tight, THE COEFFICIENT REGULARIZED REGRESSION WITH RANDOM PROJECTION, Numerical bifurcation analysis of PDEs from lattice Boltzmann model simulations: a parsimonious machine learning approach, A Survey of Compressed Sensing, Overcomplete Order-3 Tensor Decomposition, Blind Deconvolution, and Gaussian Mixture Models, Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering, Sparser Johnson-Lindenstrauss Transforms, Far-field compression for fast kernel summation methods in high dimensions, Rigorous RG algorithms and area laws for low energy eigenstates in 1D, Optimal stable nonlinear approximation, Equality, Revisited, On the distance concentration awareness of certain data reduction techniques, Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument, A simple test for zero multiple correlation coefficient in high-dimensional normal data using random projection, On the structured backward error of inexact Arnoldi methods for (skew)-Hermitian and (skew)-symmetric eigenvalue problems, Randomized algorithms in numerical linear algebra, Distance geometry and data science, Randomized anisotropic transform for nonlinear dimensionality reduction, The geometry of off-the-grid compressed sensing, Data-independent random projections from the feature-map of the homogeneous polynomial kernel of degree two, Algorithmic paradigms for stability-based cluster validity and model selection statistical methods, with applications to microarray data analysis, A variant of the Johnson-Lindenstrauss lemma for circulant matrices, Random projections of linear and semidefinite problems with linear inequalities, Representation and coding of signal geometry, Time for dithering: fast and quantized random embeddings via the restricted isometry property, Literature survey on low rank approximation of matrices, On variants of the Johnson–Lindenstrauss lemma, Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma, Linear regression with sparsely permuted data, A Uniform Lower Error Bound for Half-Space Learning, EVD dualdating based online subspace learning, Structure from Randomness in Halfspace Learning with the Zero-One Loss, An Introduction to Compressed Sensing, Classification Scheme for Binary Data with Extensions, Near-optimal encoding for sigma-delta quantization of finite frame expansions, A central limit theorem for convex sets, Targeted Random Projection for Prediction From High-Dimensional Features, Statistical mechanics of complex neural systems and high dimensional data, Compressive sensing using chaotic sequence based on Chebyshev map, Using projection-based clustering to find distance- and density-based clusters in high-dimensional data, On Geometric Prototype and Applications, Blessing of dimensionality: mathematical foundations of the statistical physics of data, Euclidean distance between Haar orthogonal and Gaussian matrices, On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms, High-dimensional approximate \(r\)-nets, On orthogonal projections for dimension reduction and applications in augmented target loss functions for learning problems, Dimensionality reduction with subgaussian matrices: a unified theory, Frames as Codes, Convergence rates of learning algorithms by random projection, Randomized large distortion dimension reduction, Fast, linear time, \(m\)-adic hierarchical clustering for search and retrieval using the Baire metric, with linkages to generalized ultrametrics, hashing, formal concept analysis, and precision of data measurement, Two-dimensional random projection, Applications of dimensionality reduction and exponential sums to graph automorphism, Fast directional algorithms for the Helmholtz kernel, Swarm intelligence for self-organized clustering, Statistical methods for tissue array images -- algorithmic scoring and co-training, Unnamed Item, Random Projection RBF Nets for Multidimensional Density Estimation, Dimension Reduction for Polynomials over Gaussian Space and Applications, The Bottleneck Degree of Algebraic Varieties, A note on linear function approximation using random projections, On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms, Simple Classification using Binary Data, Optimal Bounds for Johnson-Lindenstrauss Transformations, De-noising by thresholding operator adapted wavelets, Almost Optimal Explicit Johnson-Lindenstrauss Families, Bayesian random projection-based signal detection for Gaussian scale space random fields, A Computationally Efficient Projection-Based Approach for Spatial Generalized Linear Mixed Models, Optimal fast Johnson-Lindenstrauss embeddings for large data sets, Johnson-Lindenstrauss lemma for circulant matrices**, Dimensionality reduction for \(k\)-distance applied to persistent homology, Sparse Learning for Large-Scale and High-Dimensional Data: A Randomized Convex-Concave Optimization Approach, Random projections of smooth manifolds, How Accurately Should I Compute Implicit Matrix-Vector Products When Applying the Hutchinson Trace Estimator?, A Well-Tempered Landscape for Non-convex Robust Subspace Recovery, The complexity of quantum disjointness, High-dimensional model recovery from random sketched data by exploring intrinsic sparsity, Unnamed Item, A Powerful Bayesian Test for Equality of Means in High Dimensions, Fast and memory-optimal dimension reduction using Kac's walk, On the efficiency of Hamiltonian-based quantum computation for low-rank matrices, Unnamed Item, Unnamed Item, Unnamed Item, Variance reduction in feature hashing using MLE and control variate method, Robust Width: A Characterization of Uniformly Stable and Robust Compressed Sensing, Efficient algorithms for privately releasing marginals via convex relaxations, Random projections and Hotelling’s T2 statistics for change detection in high-dimensional data streams, Random projections as regularizers: learning a linear discriminant from fewer observations than dimensions, Two Models of Double Descent for Weak Features, Sparse control of alignment models in high dimension
Cites Work
