Abstract

The canonical decomposition (CPD) is a fundamental tensor decomposition which expresses a tensor as a sum of rank one tensors. In stark contrast to the matrix case, with light assumptions, the CPD of a low rank tensor is (essentially) unique. The essential uniqueness of CPD makes this decomposition a powerful tool in many applications as it allows for extraction of component information from a signal of interest. One popular algorithm for algebraic computation of a CPD is the generalized eigenvalue decomposition (GEVD) which selects a matrix subpencil of a tensor, then computes the generalized eigenvectors of the pencil. In this article, we present a simplification of GEVD which improves the accuracy of the algorithm. Surprisingly, the generalized eigenvector computation in GEVD is in fact unnecessary and can be replaced by a QZ decomposition which factors a pair of matrices as a product of unitary and upper triangular matrices. Computing a QZ decomposition is a standard first step when computing generalized eigenvectors, so our algorithm can been seen as a direct simplification of GEVD.

Code description

This package provides an implementation of the two methods from 1 to compute the CPD of a tensor with the use of QZ decompositions. A tutorial on how to use the methods and files to generate the experiments from the paper are included as well.

Reference

E. Evert, M. Vandecappelle and L. De Lathauwer, "Canonical Polyadic Decomposition via the Generalized Schur Decomposition," in IEEE Signal Processing Letters, vol. 29, pp. 937-941, 2022.

Download code