Efficient CP Rounding Using Alternating Least Squares with QR Decomposition
- 16 April 2026
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 47 (2) , 544-563
Abstract
The CANDECOMP/PARAFAC (CP) decomposition is widely used for analyzing multidimensional data, and the alternating least squares (CP-ALS) algorithm is a common method for its computation. CP rounding is the problem of computing a lower-rank CP decomposition of an input already in a higher-rank CP format. While the normal equations (NE) approach in CP-ALS is efficient for the CP rounding problem and frequently used, it becomes unstable in the presence of ill-conditioned subproblems. This paper presents a new QR-based CP-ALS method for CP rounding that preserves both numerical stability and computational efficiency. Our experiments show that the proposed method offers significant speedup over a previous QR-based approach and the Tensor Toolbox’s NE-based implementation, particularly for higher-order tensors. Furthermore, our approach demonstrates a marked reduction in error for ill-conditioned problems, with error reductions several orders of magnitude smaller compared to the NE-based method, while achieving faster convergence and more accurate solutions. By using a more numerically stable approach, we can solve more problems in reduced working precision, which enables further reduction in time to solution. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SIMAX and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/alexz949/CP-Rounding.git . [Formula: see text]Keywords
Funding Information
- National Science Foundation (CCF-1942892)
- U.S. Department of Energy (DE-SC-0023296)
This publication has 14 references indexed in Scilit:
- Tensor Decompositions for Data Science2025
- CP decomposition for tensors via alternating least squares with QR decompositionNumerical Linear Algebra with Applications, 2023
- Low rank approximation in simulations of quantum algorithmsJournal of Computational Science, 2022
- Tensor methods for the Boltzmann-BGK equationJournal of Computational Physics, 2020
- Computing Dense Tensor Decompositions with Optimal Dimension TreesAlgorithmica, 2018
- Fast Alternating LS Algorithms for High Order CANDECOMP/PARAFAC Tensor FactorizationsIEEE Transactions on Signal Processing, 2013
- Trigonometric identities and sums of separable functionsThe Mathematical Intelligencer, 2005
- Numerical operator calculus in higher dimensionsProceedings of the National Academy of Sciences, 2002
- Analysis of Individual Differences in Multidimensional Scaling Via an N-way Generalization of “Eckart-Young” DecompositionPsychometrika, 1970
- The Expression of a Tensor or a Polyadic as a Sum of ProductsJournal of Mathematics and Physics, 1927