Parallel Gauss-Newton method for CP decomposition

In this thesis, we formulate the Gauss-Newton algorithm to make it viable for running on distributed memory architectures and comparative to Alternating least squares algorithm for CP decomposition. Alternating least squares may exhibit slow or no convergence, especially when high accuracy is required. CP decomposition problem can be formulated as a non-linear least squares problem to apply iterative Newton-like methods. Direct solution of linear systems involving an approximated Hessian is an expensive approach, however, recent advancements have shown that use of an implicit representation of the linear system makes these methods competitive with alternating least squares in terms of speed. We provide a 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 to that, we introduce a regularization scheme for the Gauss-Newton method which shows better convergence results across a variety of tensors. We study the convergence of variants of the Gauss-Newton method relative to Alternating least squares for finding exact CP decompositions as well as approximate decompositions of real-world tensors.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Applied Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2020

Author dc:creator

• Singh, Navjot

Contributors dc:contributor

• Solomonik, Edgar

• tensor decompositions, canonical decomposition (CANDECOMP),Gauss Newton

Statement dc:rights

• Copyright 2020 Navjot Singh

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/108074

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/108074