论文标题
平行的随机塔克分解算法
Parallel Randomized Tucker Decomposition Algorithms
论文作者
论文摘要
Tucker Tensor分解是将单数值分解（SVD）自然扩展到多路数据。我们建议通过使用随机化和并行化加速塔克张量分解算法。我们提出了两种算法，这些算法将扩展到大数据和许多处理器，与以前的确定性和随机方法相比，大大降低了计算和通信成本，并获得了几乎相同的近似误差。在我们的算法中，关键思想是用Kronecker结构的随机矩阵执行随机草图，该矩阵与非结构化矩阵相比降低了计算，并且可以使用基本的张量计算内核来实现。我们提供算法的概率误差分析，并为结构化的随机草图实现新的并行算法。我们的实验结果表明，我们的随机化和并行化的组合比替代方法更快地实现了准确的塔克分解速度。我们在3D仿真数据上观察到最快的确定性并行实现，最多可观察到16倍的加速。
The Tucker tensor decomposition is a natural extension of the singular value decomposition (SVD) to multiway data. We propose to accelerate Tucker tensor decomposition algorithms by using randomization and parallelization. We present two algorithms that scale to large data and many processors, significantly reduce both computation and communication cost compared to previous deterministic and randomized approaches, and obtain nearly the same approximation errors. The key idea in our algorithms is to perform randomized sketches with Kronecker-structured random matrices, which reduces computation compared to unstructured matrices and can be implemented using a fundamental tensor computational kernel. We provide probabilistic error analysis of our algorithms and implement a new parallel algorithm for the structured randomized sketch. Our experimental results demonstrate that our combination of randomization and parallelization achieves accurate Tucker decompositions much faster than alternative approaches. We observe up to a 16X speedup over the fastest deterministic parallel implementation on 3D simulation data.
