Randomized large distortion dimension reduction (Q2253922)

The authors prove the following theorem. Let \(\Gamma\) be an \(m\times n\) random matrix whose rows are i.i.d. \(\Psi _2\) random vectors satisfying certain concentration properties. Let \(D\geq 2\) and \(\{W_{\ell}\}_{\ell =1}^p\) be a collection of \(k\)-dimensional subspaces of \(\ell _2^n\). Let \(m\geq C(k+\ln p/\ln D)\). Then there exists \(L>0\) such that for every \(\ell\leq p\) and every \(x, y\in W_{\ell}\) \[ \frac{L}{D}\, \|x-y\|_2\leq \|\Gamma (x) -\Gamma (y)\|_2 \leq L \|x-y\|_2 \] with probability at least \(1-D^{-m/5}\). This theorem is a ``large distortion'' counterpart of a theorem from \textit{A. Dmitriyuk} and \textit{Y. Gordon} [Stud. Math. 195, No. 3, 227--241 (2009; Zbl 1192.46012)].