Oblivious squared-norm subspace embeddings

Let $\mathbb{K}\in \{\mathbb{R},\mathbb{C}\}$, let $n,m\ge 1$, and use $\mathrm{\parallel }x{\mathrm{\parallel }}_2^2={\sum }_i\mathrm{\mid }{x}_i{\mathrm{\mid }}^2$ on ${\mathbb{K}}^n$. For a fixed subspace $U\subseteq {\mathbb{K}}^n$ and $0<\epsilon <1$, a matrix $S\in {\mathbb{K}}^{m\times n}$ is an $\epsilon$-subspace embedding for $U$ when

$$(1-\epsilon )\mathrm{\parallel }x{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }Sx{\mathrm{\parallel }}_2^2\le (1+\epsilon )\mathrm{\parallel }x{\mathrm{\parallel }}_2^2\text{for every }x\in U\mathrm{.}$$

For an integer $d$ with $0\le d\le n$ and $0<\delta <1$, a distribution $\mathcal{D}$ on $m\times n$ matrices is an $(\epsilon ,\delta )$ oblivious ${\mathrm{\ell }}_2$ subspace embedding for dimension $d$ if, for every fixed $d$-dimensional subspace $U\subseteq {\mathbb{K}}^n$ chosen independently of the draw,

$$\underset{S\sim \mathcal{D}}{\mathrm{Pr}}\{S\text{ is an }\epsilon \text{-subspace embedding for }U\}\ge 1-\delta \mathrm{.}$$

The subspace is fixed before sampling, but the guarantee is stated separately for each such $U$; it does not assert that one draw preserves all $d$-dimensional subspaces simultaneously. For a matrix $A$, an embedding of $\mathrm{Ran}(A)$ means the property on its column space. For least-squares residuals $Ax-b$, the relevant subspace is $\mathrm{span}(\mathrm{Ran}(A),b)$.