A Practical Randomized CP Tensor Decomposition


The CANDECOMP/PARAFAC (CP) decomposition is a leading method for the analysis of multiway data. The standard alternating least squares algorithm for the CP decomposition (CP-ALS) involves a series of highly overdetermined linear least squares problems. We extend randomized least squares methods to tensors and show the workload of CP-ALS can be drastically reduced without a sacrifice in quality. We introduce techniques for efficiently preprocessing, sampling, and computing randomized least squares on a dense tensor of arbitrary order, as well as an efficient sampling-based technique for checking the stopping condition. We also show more generally that the Khatri-Rao product (used within the CP-ALS iteration) produces conditions favorable for direct sampling. In numerical results, we see improvements in speed, reductions in memory requirements, and robustness with respect to initialization.

SIAM Journal on Matrix Analysis and Applications
C. Battaglino, G. Ballard, T. G. Kolda. A Practical Randomized CP Tensor Decomposition. SIAM Journal on Matrix Analysis and Applications, Vol. 39, No. 2, pp. 876-901, 26 pages, 2018. https://doi.org/10.1137/17M1112303


author = {Casey Battaglino and Grey Ballard and Tamara G. Kolda}, 
title = {A Practical Randomized {CP} Tensor Decomposition}, 
journal = {SIAM Journal on Matrix Analysis and Applications}, 
volume = {39}, 
number = {2}, 
pages = {876--901},
pagetotal = {26} 
year = {2018},
doi = {10.1137/17M1112303},
eprint = {1701.06600},