论文标题
基于实用的杠杆抽样，用于低级张量分解
Practical Leverage-Based Sampling for Low-Rank Tensor Decomposition
论文作者
论文摘要
低级别的规范聚量张量分解可用于数据分析，可以通过求解一系列过度确定的最小二乘子问题来计算。通过考虑稀疏张量的动机，我们提出使用杠杆评分绘制每个子问题的绘制，以选择行的子集，并在解决方案准确性上保证了概率。我们随机样品行成比例以利用得分上限，可以使用张量分解中固有的特殊Khatri-Rao子问题结构进行有效计算。至关重要的是，对于$（d+1）$ - 方式张量，素描系统中的行数为$ O（r^d/ε）$，用于分解等级$ r $和$ε$ - 准确性在最小二乘求解中，与张紧器中的非透射齐率的数量和非透兼数的数量无关。在此过程中，我们为高杠杆得分行进行过多的通用矩阵草图问题提供了一种实用的解决方案，建议确定性地包括这样的行，并将重复的样品组合在草图的系统中；我们猜想这可以导致改善的理论界限。现实世界中大规模张量的数值结果表明，该方法在几乎相同的准确性上的速度明显快于确定性方法。
The low-rank canonical polyadic tensor decomposition is useful in data analysis and can be computed by solving a sequence of overdetermined least squares subproblems. Motivated by consideration of sparse tensors, we propose sketching each subproblem using leverage scores to select a subset of the rows, with probabilistic guarantees on the solution accuracy. We randomly sample rows proportional to leverage score upper bounds that can be efficiently computed using the special Khatri-Rao subproblem structure inherent in tensor decomposition. Crucially, for a $(d+1)$-way tensor, the number of rows in the sketched system is $O(r^d/ε)$ for a decomposition of rank $r$ and $ε$-accuracy in the least squares solve, independent of both the size and the number of nonzeros in the tensor. Along the way, we provide a practical solution to the generic matrix sketching problem of sampling overabundance for high-leverage-score rows, proposing to include such rows deterministically and combine repeated samples in the sketched system; we conjecture that this can lead to improved theoretical bounds. Numerical results on real-world large-scale tensors show the method is significantly faster than deterministic methods at nearly the same level of accuracy.
