Johnson-Lindenstrauss Flattening Lemma for Discrete Lattice Point Sets
A lattice-valued version of the Johnson-Lindenstrauss flattening lemma: instead of embedding a point set of R^d into R^k, it shows that a suitably separated point set living in a scaled integer lattice (lambda/lambda0)Z^d can be mapped into a lower-dimensional integer grid (1/lambda0)Z^k with distortion arbitrarily close to 1. Students learn how rescaling the data by an integer factor lambda, combined with Ziegler's rotation theorem and equidistribution modulo one, keeps both the number of decimals and the magnitude of the flattened data bounded — a more realistic computer-model setting than real-valued JL.
A remark on dimensionality reduction in discrete subgroups Rodolfo Viera January 22, 2025 Abstract
This short note proves a discrete-lattice version of the Johnson-Lindenstrauss (JL) flattening lemma. The classical JL lemma embeds d points of R^d into R^k with k = O(log d / eps^2) and distortion a…