# Subspace Embeddings Under Nonlinear Transformations

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2020.

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

- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Learning Generative Prior with Latent Space Sparsity Constraints](https://mlsanity.com/paper/2105.11956/) (2021)
- [Importance Sampling for Nonlinear Models](https://mlsanity.com/paper/2505.12353/) (2025)

## Abstract (arXiv)

We consider low-distortion embeddings for subspaces under entrywise nonlinear transformations. In particular we seek embeddings that preserve the norm of all vectors in a space S = y: y = f(x) for x ∈ Z, where Z is a k-dimensional subspace of ℝn and f(x) is a nonlinear activation function applied entrywise to x. When f is the identity, and so S is just a k-dimensional subspace, it is known that, with high probability, a random embedding into O(k/ε2) dimensions preserves the norm of all y ∈ S up to (1± ε) relative error. Such embeddings are known as subspace embeddings, and have found widespread use in compressed sensing and approximation algorithms. We give the first low-distortion embeddings for a wide class of nonlinear functions f. In particular, we give additive ε error embeddings into O(fracklog (n/ε)ε2) dimensions for a class of nonlinearities that includes the popular Sigmoid SoftPlus, and Gaussian functions. We strengthen this result to give relative error embeddings under some further restrictions, which are satisfied e.g., by the Tanh, SoftSign, Exponential Linear Unit, and many other `soft' step functions and rectifying units. Understanding embeddings for subspaces under nonlinear transformations is a key step towards extending random sketching and compressing sensing techniques for linear problems to nonlinear ones. We discuss example applications of our results to improved bounds for compressed sensing via generative neural networks.