Randomized large distortion dimension reduction

Consider a random matrix (H:{mathbb {R}}^{n}longrightarrow {mathbb {R}}^{m}) . Let (Dge 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 (1le lle p) and (x,yin W_l) , $$begin{aligned} Vert x-yVert _2le Vert Hx-HyVert _2le DVert x-yVert _2. end{aligned}$$ We show that for (m=Obig (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) .