A Practical Randomized CP Tensor Decomposition

Understand

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.