Title: Randomized CP Tensor Decomposition,
Abstract: The CANDECOMP/PARAFAC (CP) tensor decomposition is a popular
dimensionality-reduction method for multiway data. Dimensionality reduction is
often sought since many high-dimensional tensors have low intrinsic rank
relative to the dimension of the ambient measurement space. However, the
emergence of `big data' poses significant computational challenges for
computing this fundamental tensor decomposition. Leveraging modern randomized
algorithms, we demonstrate that the coherent structure can be learned from a
smaller representation of the tensor in a fraction of the time. Moreover, the
high-dimensional signal can be faithfully approximated from the compressed
measurements. Thus, this simple but powerful algorithm enables one to compute
the approximate CP decomposition even for massive tensors. The approximation
error can thereby be controlled via oversampling and the computation of power
iterations. In addition to theoretical results, several empirical results
demonstrate the performance of the proposed algorithm.