  The CANDECOMP/PARAFAC (CP) tensor decomposition is a popular
dimensionality-reduction method for multiway data. Dimensionality reduction is
often sought after 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. By leveraging modern
randomized algorithms, we demonstrate that coherent structures can be learned
from a smaller representation of the tensor in a fraction of the time. 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.
