Randomized large distortion dimension reduction

DOI10.1007/S11117-014-0275-7MaRDI QIDQ2253922zbMATH OpenOpenAlexFDO

Authors Alon Dmitriyuk, Yehoram Gordon

Publication date 13 February 2015

Published in Positivity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.2768

zbMATH Keywords

Gaussian processesempirical processesconvexityhigh-dimensional geometrylocal theoryGaussian operatorsJohnson-Lindenstrauss lemmas

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07) Asymptotic theory of Banach spaces (46B06) Probabilistic methods in Banach space theory (46B09)

Abstract: Consider a random matrix $H:mathbb{R}^{n}longrightarrowmathbb{R}^m$. Let $Dgeq2$ and let ${W_l}_{l=1}^p$ be a set of $k$-dimensional affine subspaces of $mathbb{R}^n$. We ask what is the probability that for all $1leqlleqp$ and $x,yin{W}_l$, [ |x-y|_2leq|Hx-Hy|_2leq D|x-y|_2. ] We show that for $$ and a variety of different classes of random matrices $H$, which include the class of Gaussian matrices, existence is assured and the probability is very high. The estimate on $m$ is tight in terms of $k,p,D$.

Recommendations

• Random embeddings with an almost Gaussian distortion
• On Dvoretzky's theorem for subspaces of \(L_p\)
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Generalizing the Johnson--Lindenstrauss lemma to \(k\)-dimensional affine subspaces

Cites work

• scientific article; zbMATH DE number 2019638 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• An algorithmic theory of learning: Robust concepts and random projection
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Compressed sensing
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Elliptically contoured distributions
• Extensions of Lipschitz mappings into a Hilbert space
• Generalizing the Johnson--Lindenstrauss lemma to \(k\)-dimensional affine subspaces
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On the minimum of several random variables
• Random Euclidean sections of some classical Banach spaces
• Reconstruction and subgaussian operators in asymptotic geometric analysis
• Regularity of Gaussian processes
• Some inequalities for Gaussian processes and applications

Cited in

(15)

• scientific article; zbMATH DE number 6860845 (Why is no real title available?)
• Sharp Estimates on Random Hyperplane Tessellations
• Random embeddings with an almost Gaussian distortion
• Universality laws for randomized dimension reduction, with applications
• Using Randomization to Break the Curse of Dimensionality
• Isometric sketching of any set via the restricted isometry property
• Improved analysis of the subsampled randomized Hadamard transform
• A measure concentration effect for matrices of high, higher, and even higher dimension
• scientific article; zbMATH DE number 2119731 (Why is no real title available?)
• Generalizing the Johnson--Lindenstrauss lemma to \(k\)-dimensional affine subspaces
• Robustness properties of dimensionality reduction with Gaussian random matrices
• Rigorous restricted isometry property of low-dimensional subspaces
• Dimension reduction by random hyperplane tessellations
• Almost-Euclidean subspaces of \(\ell_1^N\) via tensor products: a simple approach to randomness reduction
• Small ball probabilities for linear images of high-dimensional distributions

This page was built for publication: Randomized large distortion dimension reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2253922)