Accelerated Canonical Polyadic Decomposition by Using Mode Reduction

CP) decomposition (CPD) is widely applied to N th-order (N ≥ 3) tensor analysis. Existing CPD methods mainly use alternating least squares iterations and hence need to unfold tensors to each of their N modes frequently, which is one major performance bottleneck for large-scale data, especially when the order N is large. To overcome this problem, in this paper we proposed a new CPD method in which the CPD of a high order tensor (i.e. N> 3) is realized by applying CPD to a mode reduced one (typically, 3rd-order tensor) followed by a Khatri-Rao product projection procedure. This way is not only quite efficient as frequently unfolding to N modes is avoided, but also promising to conquer the bottleneck problem caused by high collinearity of components. We showed that, under mild conditions, any N th-order CPD can be converted to an equivalent 3rd-order one but without destroying essential uniqueness, and theoretically they simply give consistent results. Besides, once the CPD of any unfolded lower-order tensor is essentially unique, it is also true for the CPD of the original higher order tensor. Error bounds of truncated CPD were also analyzed in presence of noise. Simulations showed that, compared with state-of-the-art CPD methods, the proposed method is more efficient and is able to escape from local solutions more easily. Index Terms—CP (PARAFAC) decompositions, tensor decom-positions, mode reduction, Khatri-Rao product, alternating least squares. I