This is an announcement for the paper "Large distortion dimension reduction using random variable" by Alon Dmitriyuk and Yehoram Gordon.
Abstract: Consider a random matrix $H:\mathbb{R}^n\longrightarrow\mathbb{R}^m$. Let $D\geq2$ 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\leq l\leq 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\big(k+\frac{\ln{p}}{\ln{D}}\big)$ 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$.
Archive classification: math.FA
Remarks: 18 pages
Submitted from: gordon@techunix.technion.ac.il
The paper may be downloaded from the archive by web browser from URL
http://front.math.ucdavis.edu/1308.2768
or