论文标题
输入稀疏时间的张量产品矩阵的利用分数抽样
Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time
论文作者
论文摘要
我们提出了一种输入稀疏时间抽样算法，该算法可以近似于使用几乎最佳的样品$ q $矩阵的$ q $ fold列张量产品对应的克矩阵，从而改善了Poly $（Q）$ actional先前已知的方法。此外，对于数据集的$ q $倍自量量的重要特殊情况，该数据集是该学位的功能矩阵-Y $ q $ polyenmial kernel，我们方法运行时的领先术语与输入数据集的大小成正比，并且对$ q $不依赖。以前的技术要么在其运行时产生Poly Poly $（Q）$降低，要么以$ Q $的依赖为代价，以具有亚最佳目标维度为代价，并且在其运行时四处依赖于数据点的数量。我们的抽样技术取决于$ q $部分相关的随机预测的集合，这些预测可以同时应用于数据集$ x $的总时间，仅取决于$ x $的大小，同时$ q $ fold Kronecker产品在$ x^^^^^^$ x^^$ x^^$ x^^^$ x^^$ x^^^$ x^Q \ ot中的任何固定量均可用作近乎等等的Vime。我们还表明，我们的采样方法推广到除多项式之外的其他类别的核，例如高斯和神经切线核。
We propose an input sparsity time sampling algorithm that can spectrally approximate the Gram matrix corresponding to the $q$-fold column-wise tensor product of $q$ matrices using a nearly optimal number of samples, improving upon all previously known methods by poly$(q)$ factors. Furthermore, for the important special case of the $q$-fold self-tensoring of a dataset, which is the feature matrix of the degree-$q$ polynomial kernel, the leading term of our method's runtime is proportional to the size of the input dataset and has no dependence on $q$. Previous techniques either incur poly$(q)$ slowdowns in their runtime or remove the dependence on $q$ at the expense of having sub-optimal target dimension, and depend quadratically on the number of data-points in their runtime. Our sampling technique relies on a collection of $q$ partially correlated random projections which can be simultaneously applied to a dataset $X$ in total time that only depends on the size of $X$, and at the same time their $q$-fold Kronecker product acts as a near-isometry for any fixed vector in the column span of $X^{\otimes q}$. We also show that our sampling methods generalize to other classes of kernels beyond polynomial, such as Gaussian and Neural Tangent kernels.
