Efficient QR-Based CP Decomposition Acceleration via Restructured Dimension Tree and Customized Extrapolation

The canonical polyadic (CP) decomposition is one of the most widely used tensor decomposition techniques. The conventional CP decomposition algorithm combines alternating least squares (ALS) with the normal equation. However, the normal equation is susceptible to numerical ill-conditioning, which can adversely affect the decomposition results. To mitigate this issue, ALS combined with QR decomposition has been proposed as a more numerically stable alternative. Although this method enhances stability, its iterative process involves tensor-times-matrix (TTM) operations, which typically result in higher computational costs. To reduce this cost, we propose restructured dimension tree, which increases the reuse of intermediate tensors and reduces the number of TTM operations. Compared with the standard dimension tree structure, this dimension tree structure can reduce the computational complexity of TTM operations for tensors of any order by 33\%. Additionally, we introduce a customized extrapolation strategy in the CP-ALS-QR algorithm, leveraging the unique structure of the matrix $\mathbf{Q}_0$ to further accelerate convergence. By integrating these two techniques, we propose a novel CP decomposition algorithm that significantly improves iteration efficiency, achieving up to twofold acceleration on datasets with certain specific structures. Numerical experiments on five real-world datasets show that, compared with the baseline algorithm, our proposed algorithm improves iteration efficiency while simultaneously enhancing fitting accuracy.