Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
Johnson and Lindenstrauss (Contemporary Mathematics, 1984) showed that for n > m, a scaled random projection A from ℝn to ℝm is an approximate isometry on any set S of size at most exponential in m. If S is larger, however, its points can contract arbitrarily under A. In particular, the hypergrid ([−B, B] ∩ ℤ)n is expected to contain a point that is contracted by a factor of κstat = Θ(B)−1/α, where α = m/n.
Authors
- Vinod Vaikuntanathan (ORCID: https://orcid.org/0000-0002-2666-0045)
- Neekon Vafa (ORCID: https://orcid.org/0000-0002-0555-4200)
- Alon Rosen (ORCID: https://orcid.org/0000-0002-3021-7150)
- Andrej Bogdanov (ORCID: https://orcid.org/0000-0002-0338-6151)
Institutions
- University of Ottawa (CA)
- Massachusetts Institute of Technology (US)
- Bocconi University (IT)
Publication Details
- Published
- 2026-06-09
- DOI
- https://doi.org/10.1145/3798129.3800741
- Primary Topic
- Distributed and Parallel Computing Systems
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Natural Sciences and Engineering Research Council of Canada
- European Research Council
- Defense Sciences Office, DARPA