Large distortion dimension reduction using random variable

Abstract

Consider a random matrix $H:{\mathbb{R}}^n⟶{\mathbb{R}}^m$. Let $D\ge 2$ 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 $1\le l\le p$ and $x,y\in W_l$, \[ \|x-y\|_2\leq\|Hx-Hy\|_2\leq D\|x-y\|_2. \] We show that for $m=O(k+\frac{\ln p}{\ln D})$ 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$.

18 pages