Accelerating alternating least squares for tensor decomposition by pairwise perturbation

Linjian Ma, Edgar Solomonik

Research output: Contribution to journalArticlepeer-review


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 (Formula presented.) with respect to state-of-the-art ALS approaches for various model tensor problems and real datasets.

Original languageEnglish (US)
Article numbere2431
JournalNumerical Linear Algebra with Applications
Issue number4
StatePublished - Aug 2022
Externally publishedYes


  • CP decomposition
  • Tucker decomposition
  • alternating least squares
  • tensor

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Applied Mathematics


Dive into the research topics of 'Accelerating alternating least squares for tensor decomposition by pairwise perturbation'. Together they form a unique fingerprint.

Cite this