Title: A Practical Randomized CP Tensor Decomposition,
Abstract: 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.