Normal Forms for Tensor Rank Decomposition

We propose a new algorithm for computing the tensor rank decomposition or canonical polyadic decomposition of higher-order tensors subject to a rank and genericity constraint. Reformulating this as a system of polynomial equations allows us to leverage recent numerical linear algebra tools from computational algebraic geometry. We describe the complexity of our algorithm in terms of the multigraded regularity of a multihomogeneous ideal. We prove effective bounds for many formats and ranks and conjecture a general formula. These bounds are of independent interest for overconstrained polynomial system solving. Our experiments show that our algorithm can outperform state-of-the-art algebraic algorithms by an order of magnitude in terms of accuracy, computation time, and memory consumption.