A remark on dimensionality reduction in discrete subgroups

Abstract

In this short note, we prove a version of the Johnson-Lindenstrauss flattening Lemma for point sets taking values in discrete subgroups. More precisely, given $d,\hat{I}{»}_0,N_0\in \mathbb{N}$ and $\hat{I}\mu \in \left(0,\frac{1}{2}\right)$ suitably chosen, we show there exists a natural number $k=k(d,\hat{I}\mu )=O\left(\frac{1}{\hat{I}{\mu }^2}\log d\right)$, such that for every sufficiently large scaling factor $\hat{I}»\in \mathbb{N}$ and any point set $\mathcal{D}\subset \frac{\hat{I}}{»}\hat{I}{»}_0{\mathbb{Z}}^d\cap B(0,\hat{I}»N_0)$ with cardinality $d$, there exists an embedding $F:\mathcal{D}\to \frac{1}{\hat{I}{»}_0}{\mathbb{Z}}^k$, with distortion at most $\left(1+\hat{I}\mu +\frac{\hat{I}}{\mu }\hat{I}»\hat{I}{»}_0\right)$.

A short note, 4 pages. Comments are welcome. Comments to V3: Some improvements were made to the dependence of the parameter lambda, and some changes were made in the exposition