TensorSketch is an oblivious linear sketch introduced in Pagh'13 and later
used in Pham, Pagh'13 in the context of SVMs for polynomial kernels. It was
shown in Avron, Nguyen, Woodruff'14 that TensorSketch provides a subspace
embedding, and therefore can be used for canonical correlation analysis, low
rank approximation, and principal component regression for the polynomial
kernel. We take TensorSketch outside of the context of polynomials kernels, and
show its utility in applications in which the underlying design matrix is a
Kronecker product of smaller matrices. This allows us to solve Kronecker
product regression and non-negative Kronecker product regression, as well as
regularized spline regression. Our main technical result is then in extending
TensorSketch to other norms. That is, TensorSketch only provides input sparsity
time for Kronecker product regression with respect to the $2$-norm. We show how
to solve Kronecker product regression with respect to the $1$-norm in time
sublinear in the time required for computing the Kronecker product, as well as
for more general $p$-norms.

本文提出一种名为 TensorSketch 的算法，它可以用于 Kronecker 乘积回归、正规化样条回归等问题，并且还可以用于基本相关性分析和低秩逼近。此外，该算法还被扩展到用于其他范数的计算。