Subspace Embeddings Under Nonlinear Transformations
This work addresses a foundational problem in extending compressed sensing and sketching techniques to nonlinear domains, with potential applications in generative neural networks.
The paper tackles the problem of creating low-distortion embeddings for subspaces under entrywise nonlinear transformations, which extends subspace embedding techniques from linear to nonlinear settings. It provides the first such embeddings with additive error for a class of nonlinear functions including Sigmoid and SoftPlus, and relative error for functions like Tanh and ELU, achieving dimensions of O(k log(n/ε)/ε²).
We consider low-distortion embeddings for subspaces under \emph{entrywise nonlinear transformations}. In particular we seek embeddings that preserve the norm of all vectors in a space $S = \{y: y = f(x)\text{ for }x \in Z\}$, where $Z$ is a $k$-dimensional subspace of $\mathbb{R}^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 \in S$ up to $(1\pm ε)$ relative error. Such embeddings are known as \emph{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(\frac{k\log (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.