Wednesday October 12, 12pm1pm, 1116E Klaus
A Practical Randomized CP Tensor DecompositionCasey Battaglino
Advisor: Prof. Richard Vuduc


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 (CPALS) involves a series of highly overdetermined least squares problems. We show that, by extending randomized least squares ("sketching") methods to tensors, the workload of CPALS 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 samplingbased technique for checking the stopping condition. We also show more generally that the KhatriRao product (used within the CP iteration) produces conditions favorable for direct sampling without any preprocessing. In numerical results, we see improvements in speed, storage, and robustness.
BIO
Casey Battaglino is a PhD student in Computational Science and Engineering working with Prof. Richard Vuduc. He is interested in bridging the gap between theory and practice towards the acceleration of largescale tensor and graph computations.