Journal
SIAM JOURNAL ON SCIENTIFIC COMPUTING
Volume 43, Issue 4, Pages C290-C311Publisher
SIAM PUBLICATIONS
DOI: 10.1137/20M1344561
Keywords
tensor decomposition; CP decomposition; Gauss-Newton method; alternating least squares; Cyclops tensor framework
Categories
Funding
- US NSF OAC SSI program [1931258]
- National Science Foundation [ACI1548562, OCI-0725070, ACI-1238993]
- Texas Advanced Computing Center (TACC) [TG-CCR180006]
Ask authors/readers for more resources
The paper introduces a parallel implementation of the Gauss-Newton method for CP decomposition, which iteratively solves linear least squares problems to improve accuracy. It explores the convergence of the Gauss-Newton method compared to alternating least squares for finding exact and approximate CP decompositions.
Alternating least squares is the most widely used algorithm for CANDECOMC/PARAFAC (CP) tensor decomposition. However, alternating least squares may exhibit slow or no convergence, especially when high accuracy is required. An alternative approach is to regard CP decomposition as a nonlinear least squares problem and employ Newton-like methods. Direct solution of linear systems involving an approximated Hessian is generally expensive. However, recent advancements have shown that use of an implicit representation of the linear system makes these methods competitive with alternating least squares (ALS). We provide the first parallel implementation of a Gauss-Newton method for CP decomposition, which iteratively solves linear least squares problems at each Gauss-Newton step. In particular, we leverage a formulation that employs tensor contractions for implicit matrix-vector products within the conjugate gradient method. The use of tensor contractions enables us to employ the Cyclops library for distributed-memory tensor computations to parallelize the Gauss-Newton approach with a high-level Python implementation. In addition, we propose a regularization scheme for the Gauss-Newton method to improve convergence properties without any additional cost. We study the convergence of variants of the Gauss-Newton method relative to ALS for finding exact CP decompositions as well as approximate decompositions of realworld tensors. We evaluate the performance of sequential and parallel versions of both approaches, and study the parallel scalability on the Stampede2 supercomputer.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available