Low-Complexity Levenberg-Marquardt Algorithm for Tensor Canonical Polyadic Decomposition

In this paper, we propose CPD-fLM++, a fast implementation of the Levenberg-Marquardt (LM) algorithm for the tensor canonical polyadic decomposition. The overall algorithmic framework follows exactly the LM approach, which enjoys locally a super-linear convergence rate and has been observed to be able to avoid the swamp effect commonly seen in other CPD algorithms. However, unlike the common wisdom that LM requires very high per-iteration complexity to execute, we show each iteration of CPD-fLM++ only requires \mathcal{O}\left( {N{K^6}} \right) flops to perform matrix inversions, where N is the number of modes and K is the target CPD rank. This is done by carefully exploiting the structures in the Jacobian Gramian matrix, and is by far the most efficient implementation of LM for CPD using direct methods. Experiments on synthetic data confirm the good performance of CPD-fLM++ for large-scale higher-order tensors.