Randomized large distortion dimension reduction

Consider a random matrix \(H:{\mathbb {R}}^{n}\longrightarrow {\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\) , $$\begin{aligned} \Vert x-y\Vert _2\le \Vert Hx-Hy\Vert _2\le D\Vert x-y\Vert _2. \end{aligned}$$ 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\) .