Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions-猫眼课题宝

DOI：

发表时间：

2021-04

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Linjian Ma;Edgar Solomonik

低秩Tucker和CP张量分解是数据分析中的强大工具。广泛使用的交替最小二乘（ALS）方法，它解决了一系列超定最小二乘子问题，是昂贵的大型和稀疏张量。我们提出了一个快速，准确的草图ALS算法的塔克分解，解决了一系列的草图秩约束线性最小二乘法子问题。理论草图大小上限提供了实现$O（\N）$相对误差为每个子问题的两个草图技术，TensorSketch和杠杆得分抽样。实验结果表明，这种新的ALS算法，结合一个新的初始化方案的基础上随机测距仪，产生高达$22.0\%$的相对分解残留改进相比，国家的最先进的草图随机算法的各种合成和真实的数据集的塔克分解。该Tucker-ALS算法进一步用于加速CP分解，通过使用随机化Tucker压缩，然后对Tucker核心张量进行CP分解。实验结果表明，该算法不仅收敛速度快，而且CP分解精度高。

Low-rank Tucker and CP tensor decompositions are powerful tools in data analytics. The widely used alternating least squares (ALS) method, which solves a sequence of over-determined least squares subproblems, is costly for large and sparse tensors. We propose a fast and accurate sketched ALS algorithm for Tucker decomposition, which solves a sequence of sketched rank-constrained linear least squares subproblems. Theoretical sketch size upper bounds are provided to achieve $O(\epsilon)$ relative error for each subproblem with two sketching techniques, TensorSketch and leverage score sampling. Experimental results show that this new ALS algorithm, combined with a new initialization scheme based on randomized range finder, yields up to $22.0\%$ relative decomposition residual improvement compared to the state-of-the-art sketched randomized algorithm for Tucker decomposition of various synthetic and real datasets. This Tucker-ALS algorithm is further used to accelerate CP decomposition, by using randomized Tucker compression followed by CP decomposition of the Tucker core tensor. Experimental results show that this algorithm not only converges faster, but also yields more accurate CP decompositions.

Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions

文献摘要

相似文献