Johnson-Lindenstrauss over torus? The Johnson-Lindenstrauss lemma is a famous result in dimensionality reduction — Given $m$ points in $\mathbb{R}^N$, and $\varepsilon >0$, there exists a quasi-isometry $f : \mathbb{R}^N\to\mathbb{R}^n$ for $n =\Omega((\ln m)/\varepsilon^2)$, i.e. for any of the initial $m$ points $x, y$:
$$\lVert f(x) - f(y)\rVert_2 \in (1\pm \varepsilon) \lVert x-y\rVert_2.$$
This is to say that $f$ approximately (up to the $(1\pm \epsilon)$ factor) preserves pairwise distances of the $m$ points, while drastically decreasing the dimensionality of the data.
I'm interested if there is a "JL-type" result for torus $\mathbb{T}:= \mathbb{R}/\mathbb{Z}$.
One can try to take the $f$ that exists from normal JL, and post-process it with reduction modulo 1.
This has the issue that reduction modulo 1 seems far from a quasi-isometry, i.e. if $x\mapsto x\bmod 1$ returns a representative in the equivalence class $[0,1)$, then the points $1-\eta, 1+\eta$ are heavily distorted by reduction modulo 1.
That being said, it seems plausible that these "problematic" points can be ignored somehow.
JL transforms are often randomized mappings, and most points are likely not randomly mapped to a point extremely close to the boundary, which is the region of "heavily distorted" points.
So is there some JL-type transform over the torus known? In particular, I would be interested in the existence of a quasi-isometry
$$f:\mathbb{T}^N\to\mathbb{T}^n$$
or
$$f:\mathbb{R}^N\to\mathbb{T}^n$$
i.e. the codomain must be the torus, the domain can either be euclidean space or the torus.
 A: I don't think there's a good analog. The problem is that for certain sets of size linear in $N$, mapping to even one dimension lower necessarily involves significant distortion of distances.
To see this, start with the observation that for any point $x$ in $\mathbb{T}^N$, there are exactly $N$ distinct length-1 geodesic loops that pass through it. It's impossible to find a very low distortion quasi-isometry $f: \mathbb{T}^N \to \mathbb{T}^{N-1}$ on the union of these loops. The image of each of the $N$ loops would have to be very close to one of the $N-1$ geodesic loops through $f(x)$. By the pigeon-hole principle, it follows that two loops, which diverge significantly from each other in $\mathbb{T}^N$, would map very near each other, meaning $f$ significantly distorts distances.
Of course, the JL lemma involves a finite set of points, but the issue remains. Replace each of the loops described above with a few evenly spaced points on the loop (giving you a set whose cardinality $m$ is linear in $N$). The same problem comes up—there's no possible low-distortion quasi-isometry of the set to one dimension lower.
