A semi-algebraic framework for approximate CP decompositions via simultaneous matrix diagonalizations (SECSI)

摘要

In this paper, we propose a framework to compute approximate CANDECOMP / PARAFAC (CP) decompositions. Such tensor decompositions are viable tools in a broad range of applications, creating the need for versatile tools to compute such decompositions with an adjustable complexity-accuracy trade-off. To this end, we propose a novel SEmi-algebraic framework that allows the computation of approximate C P decompositions via S/multaneous Matrix Diagonalizations (SECSI). In contrast to previous Simultaneous Matrix Diagonalization (SMD)-based approaches, we use the tensor structure to construct not only one but the full set of possible SMDs. Solving all SMDs, we obtain multiple estimates of the factor matrices and present strategies to choose the best estimate in a subsequent step. This SECSI framework retains the option to choose the number of SMDs to solve and to adopt various strategies for the selection of the final solution out of the multiple estimates. A best matching scheme based on an exhaustive search as well as heuristic selection schemes are devised to flexibly adapt to specific applications. Four example algorithms with different accuracy-complexity trade-off points are compared to state-of-the-art algorithms. We obtain more reliable estimates and a reduced computational complexity.