Systems of Polynomial Equations, Higher-order Tensor Decompositions, and Multidimensional Harmonic Retrieval: A Unifying Framework. Part I: The Canonical Polyadic Decomposition

We propose a multilinear algebra framework to solve systems of polynomial equations with simple roots. We translate connections between univariate polynomial root-finding, eigenvalue decompositions, and harmonic retrieval to their higher-order counterparts: a canonical polyadic decomposition (CPD) that exploits shift invariance structures in the null space of the Macaulay matrix reveals the roots of the polynomial system. The new framework allows us to use numerical CPD algorithms for solving systems of polynomial equations. For the same degree of the Macaulay matrix as in numerical polynomial algebra/polynomial numerical linear algebra, the CPD is interpreted as the joint eigenvalue decomposition of the multiplication tables. In our approach the degree can also be lower. Affine roots and roots at infinity can be handled in the same way. With minor modifications, the technique can be used to estimate approximate roots of overconstrained systems.