Practical Leverage Score-Based Sampling for Low-Rank Tensor Decompositions
Brett Larsen, Stanford University
Conventional algorithms for finding low-rank tensor decompositions can be unwieldly or even infeasible for extremely large and sparse tensors. In this work, we present an application of randomized algorithms to fitting the CANDECOMP/PARAFAC (CP) decomposition of such tensors, essentially solving a much smaller sampled version at each iterate with probabilistic guarantees on the approximation errors. In our algorithm, sketching is applied to the highly overdetermined least-squares problem that occurs repeatedly in alternating least squares (ALS). We perform sketching through leverage score sampling, which avoids working with dense tensors created by random mixing, crucially relying on the fact that the structure of the Khatri-Rao product allows sampling from overestimates of the leverage scores without forming the full product or the corresponding probabilities. Finally, we test our algorithm on both sparse synthetic tensors and data from the Formidable Repository of Open Sparse Tensors and Tools (FROSTT). For both, we demonstrate a substantial speed up in running time while still achieving an equivalent fit to the decomposition found by CP-ALS.
Abstract Author(s): Brett W. Larsen, Tamara G. Kolda