A random $m\times n$ matrix $S$ is an oblivious subspace embedding (OSE) with
parameters $\epsilon>0$, $\delta\in(0,1/3)$ and $d\leq m\leq n$, if for any
$d$-dimensional subspace $W\subseteq R^n$,
$P\big(\,\forall_{x\in W}\ (1+\epsilon)^{-1}\|x\|\leq\|Sx\|\leq
(1+\epsilon)\|x\|\,\big)\geq 1-\delta.$
It is known that the embedding dimension of an OSE must satisfy $m\geq d$,
and for any $\theta > 0$, a Gaussian embedding matrix with $m\geq (1+\theta) d$
is an OSE with $\epsilon = O_\theta(1)$. However, such optimal embedding
dimension is not known for other embeddings. Of particular interest are sparse
OSEs, having $s\ll m$ non-zeros per column, with applications to problems such
as least squares regression and low-rank approximation.
We show that, given any $\theta > 0$, an $m\times n$ random matrix $S$ with
$m\geq (1+\theta)d$ consisting of randomly sparsified $\pm1/\sqrt s$ entries
and having $s= O(\log^4(d))$ non-zeros per column, is an oblivious subspace
embedding with $\epsilon = O_{\theta}(1)$. Our result addresses the main open
question posed by Nelson and Nguyen (FOCS 2013), who conjectured that sparse
OSEs can achieve $m=O(d)$ embedding dimension, and it improves on
$m=O(d\log(d))$ shown by Cohen (SODA 2016). We use this to construct the first
oblivious subspace embedding with $O(d)$ embedding dimension that can be
applied faster than current matrix multiplication time, and to obtain an
optimal single-pass algorithm for least squares regression. We further extend
our results to construct even sparser non-oblivious embeddings, leading to the
first subspace embedding with low distortion $\epsilon=o(1)$ and optimal
embedding dimension $m=O(d/\epsilon^2)$ that can be applied in current matrix
multiplication time.

给定任意正实数 θ，我们证明对于 m≥(1+θ) d 且具有每列 O (log^4 (d)) 非零元素的 m×n 随机矩阵 S，它是一个 ε=O_θ(1) 的忽略子空间嵌入。这个结果解答了 Nelson 和 Nguyen（FOCS 2013）提出的问题，并改进了 Cohen（SODA 2016）的结果，我们将其应用于比当前矩阵乘法更快的 O (d) 嵌入维度的嵌入以及最佳单次通过最小二乘回归的算法。此外，我们还将结果扩展到构造非忽略嵌入，产生具有低失真 ε=o (1) 和最佳嵌入维度 m=O (d/ε^2) 的子空间嵌入。

稀疏子空间嵌入的最佳嵌入维度

Optimal Embedding Dimension for Sparse Subspace Embeddings

An oblivious subspace embedding (OSE) for some eps, delta in (0,1/3) and d <=
m <= n is a distribution D over R^{m x n} such that for any linear subspace W
of R^n of dimension d,
Pr_{Pi ~ D}(for all x in W, (1-eps) |x|_2 <= |Pi x|_2 <= (1+eps)|x|_2) >= 1 -
delta.
We prove that any OSE with delta < 1/3 must have m = Omega((d +
log(1/delta))/eps^2), which is optimal. Furthermore, if every Pi in the support
of D is sparse, having at most s non-zero entries per column, then we show
tradeoff lower bounds between m and s.

介绍了一种针对线性子空间的随机映射方法 ——Oblivious Subspace Embedding (OSE)，通过稀疏性限制，证明了 m 与 s 之间存在权衡下限。

关于忽略子空间嵌入的下界

Lower bounds for oblivious subspace embeddings

An "oblivious subspace embedding (OSE)" given some parameters eps,d is a
distribution D over matrices B in R^{m x n} such that for any linear subspace W
in R^n with dim(W) = d it holds that Pr_{B ~ D}(forall x in W ||B x||_2 in (1
+/- eps)||x||_2) > 2/3 We show an OSE exists with m = O(d^2/eps^2) and where
every B in the support of D has exactly s=1 non-zero entries per column. This
improves previously best known bound in [Clarkson-Woodruff, arXiv:1207.6365].
Our quadratic dependence on d is optimal for any OSE with s=1 [Nelson-Nguyen,
2012]. We also give two OSE's, which we call Oblivious Sparse
Norm-Approximating Projections (OSNAPs), that both allow the parameter settings
m = \~O(d/eps^2) and s = polylog(d)/eps, or m = O(d^{1+gamma}/eps^2) and
s=O(1/eps) for any constant gamma>0. This m is nearly optimal since m >= d is
required simply to no non-zero vector of W lands in the kernel of B. These are
the first constructions with m=o(d^2) to have s=o(d). In fact, our OSNAPs are
nothing more than the sparse Johnson-Lindenstrauss matrices of [Kane-Nelson,
SODA 2012]. Our analyses all yield OSE's that are sampled using either
O(1)-wise or O(log d)-wise independent hash functions, which provides some
efficiency advantages over previous work for turnstile streaming applications.
Our main result is essentially a Bai-Yin type theorem in random matrix theory
and is likely to be of independent interest: i.e. we show that for any U in
R^{n x d} with orthonormal columns and random sparse B, all singular values of
BU lie in [1-eps, 1+eps] with good probability.
Plugging OSNAPs into known algorithms for numerical linear algebra problems
such as approximate least squares regression, low rank approximation, and
approximating leverage scores implies faster algorithms for all these problems.

本研究提出了一种 Oblivious Subspace Embedding (OSE) 技术以及两种 Oblivious Sparse Norm-Approximating Projections (OSNAPs) 技术，基于随机矩阵理论，用于加速数值线性代数问题解决，诸如近似最小二乘回归，低秩逼近和逼近杠杆分数。