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

convexityempirical processesGaussian operatorsGaussian processeshigh-dimensional geometryJohnson-Lindenstrauss lemmaslocal theory

Mathematics Subject Classification ID

Asymptotic theory of Banach spaces (46B06) Local theory of Banach spaces (46B07) 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$.

Review text

The authors prove the following theorem. Let \(\Gamma\) be an \(m\times n\) random matrix whose rows are i.i.d. \(\Psi _2\) random vectors satisfying certain concentration properties. Let \(D\geq 2\) and \(\{W_{\ell}\}_{\ell =1}^p\) be a collection of \(k\)-dimensional subspaces of \(\ell _2^n\). Let \(m\geq C(k+\ln p/\ln D)\). Then there exists \(L>0\) such that for every \(\ell\leq p\) and every \(x, y\in W_{\ell}\) \[ \frac{L}{D}\, \|x-y\|_2\leq \|\Gamma (x) -\Gamma (y)\|_2 \leq L \|x-y\|_2 \] with probability at least \(1-D^{-m/5}\). This theorem is a ``large distortion counterpart of a theorem from \textit{A. Dmitriyuk} and \textit{Y. Gordon} [Stud. Math. 195, No. 3, 227--241 (2009; Zbl 1192.46012)].

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

• 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
• scientific article; zbMATH DE number 2019638 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• 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)

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

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)