# On Fast Johnson-Lindenstrauss Embeddings of Compact Submanifolds of ℝN with Boundary

arXiv: https://arxiv.org/abs/2110.04193 · HTML: https://mlsanity.com/paper/2110.04193/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 51 references that are in the map.
- First posted on arXiv 8 Oct 2021.

## Builds on (most cited first, 6 of 6)

- [Deep Learning-Based Solvability of Underdetermined Inverse Problems in Medical Imaging](https://mlsanity.com/paper/2001.01432/) (2020)
- [Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares](https://mlsanity.com/paper/1912.08294/) (2019)
- [Dimensionality reduction with subgaussian matrices: a unified theory](https://mlsanity.com/paper/1402.3973/) (2014)
- [Isometric sketching of any set via the Restricted Isometry Property](https://mlsanity.com/paper/1506.03521/) (2015)
- [Johnson-Lindenstrauss Embeddings with Kronecker Structure](https://mlsanity.com/paper/2106.13349/) (2021)
- [Random projections of random manifolds](https://mlsanity.com/paper/1607.04331/) (2016)

## Built on by (most cited first, 3 of 3)

- [Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications](https://mlsanity.com/paper/2311.05116/) (2023)
- [On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of ℝN](https://mlsanity.com/paper/2206.03376/) (2022)
- [Neural Network Approximation of Continuous Functions in High Dimensions with Applications to Inverse Problems](https://mlsanity.com/paper/2208.13305/) (2022)

## Abstract (arXiv)

Let M be a smooth d-dimensional submanifold of ℝN with boundary that's equipped with the Euclidean (chordal) metric, and choose m ≤ N. In this paper we consider the probability that a random matrix A ∈ ℝm × N will serve as a bi-Lipschitz function A: M rightarrow ℝm with bi-Lipschitz constants close to one for three different types of distributions on the m × N matrices A, including two whose realizations are guaranteed to have fast matrix-vector multiplies. In doing so we generalize prior randomized metric space embedding results of this type for submanifolds of ℝN by allowing for the presence of boundary while also retaining, and in some cases improving, prior lower bounds on the achievable embedding dimensions m for which one can expect small distortion with high probability. In particular, motivated by recent modewise embedding constructions for tensor data, herein we present a new class of highly structured distributions on matrices which outperform prior structured matrix distributions for embedding sufficiently low-dimensional submanifolds of ℝN (with d lesssim √N) with respect to both achievable embedding dimension, and computationally efficient realizations. As a consequence we are able to present, for example, a general new class of Johnson-Lindenstrauss embedding matrices for O(logc N)-dimensional submanifolds of ℝN which enjoy O(N log (log N))-time matrix vector multiplications.