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) 技术，基于随机矩阵理论，用于加速数值线性代数问题解决，诸如近似最小二乘回归，低秩逼近和逼近杠杆分数。