论文标题
张量产品的复杂绘制草图，并应用于多项式内核
Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel
论文作者
论文摘要
$ p $向量的张量产品的随机草图遵循统计效率和计算加速度之间的权衡。常用的方法避免明确地计算高维张量产品，从而在嵌入尺寸中产生$ \ Mathcal {O}（3^p）$的次优依赖性。我们提出了对众所周知的草图进行简单的复杂到实现（CTR）的修改，该草图用复杂的绘制代替了真实的随机投影，从而在嵌入尺寸中产生了较低的$ \ Mathcal {O}（2^p）$ factor。我们的草图的输出是真实价值的，这使他们的下游使用直接使用。特别是，我们将草图应用于与多项式内核特征地图相对应的$ p $折叠的自我评估输入。我们表明，与文献中的其他随机近似相比，我们的方法在准确性和速度方面实现了最先进的性能。
Randomized sketches of a tensor product of $p$ vectors follow a tradeoff between statistical efficiency and computational acceleration. Commonly used approaches avoid computing the high-dimensional tensor product explicitly, resulting in a suboptimal dependence of $\mathcal{O}(3^p)$ in the embedding dimension. We propose a simple Complex-to-Real (CtR) modification of well-known sketches that replaces real random projections by complex ones, incurring a lower $\mathcal{O}(2^p)$ factor in the embedding dimension. The output of our sketches is real-valued, which renders their downstream use straightforward. In particular, we apply our sketches to $p$-fold self-tensored inputs corresponding to the feature maps of the polynomial kernel. We show that our method achieves state-of-the-art performance in terms of accuracy and speed compared to other randomized approximations from the literature.
