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

http://arXiv.org/abs/1308.2768