Accelerating alternating least squares for tensor decomposition by pairwise perturbation
Accelerating alternating least squares for tensor decomposition by pairwise perturbation
复制标题
DOI：
10.1002/nla.2431
复制
发表时间：
2018-11
影响因子：
4.3
通讯作者：
Linjian Ma;Edgar Solomonik
中科院分区：
文献类型：
--
作者：
Linjian Ma;Edgar Solomonik
交替最小二乘（ALS）算法的CP和塔克分解的成本占主导地位的张量收缩所需的二次优化子问题。我们引入了一个新的家庭的算法，使用微扰校正的子问题，而不是重新计算张量收缩。当因子矩阵在迭代中变化很小时，这种近似是准确的，这发生在ALS接近收敛时。我们提供了一个理论分析，以约束的近似误差。我们的数值实验表明，所提出的成对扰动算法易于控制，收敛到最小值，是一样好的ALS。实验结果表明，对于各种模型张量问题和真实的数据集，最先进的ALS方法的改进高达3.1倍。
The alternating least squares (ALS) algorithm for CP and Tucker decomposition is dominated in cost by the tensor contractions necessary to set up the quadratic optimization subproblems. We introduce a novel family of algorithms that uses perturbative corrections to the subproblems rather than recomputing the tensor contractions. This approximation is accurate when the factor matrices are changing little across iterations, which occurs when ALS approaches convergence. We provide a theoretical analysis to bound the approximation error. Our numerical experiments demonstrate that the proposed pairwise perturbation algorithms are easy to control and converge to minima that are as good as ALS. The experimental results show improvements of up to 3.1 × with respect to state‐of‐the‐art ALS approaches for various model tensor problems and real datasets.