Accelerating Alternating Least Squares for Tensor Decomposition by Pairwise Perturbation

Linjian Ma, Edgar Solomonik

The alternating least squares 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 alternating least squares 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 alternating least squares. We evaluate the performance of both sequential and parallel version of the new algorithms, and the results show improvements of up to 2.5X with respect to state of the art alternating least squares approaches for various model tensor problems and real datasets.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment