  This paper describes a new algorithm for computing a low-Tucker-rank
approximation of a tensor. The method applies a randomized linear map to the
tensor to obtain a sketch that captures the important directions within each
mode, as well as the interactions among the modes. The sketch can be extracted
from streaming or distributed data or with a single pass over the tensor, and
it uses storage proportional to the degrees of freedom in the output Tucker
approximation. The algorithm does not require a second pass over the tensor,
although it can exploit another view to compute a superior approximation. The
paper provides a rigorous theoretical guarantee on the approximation error.
Extensive numerical experiments show that that the algorithm produces useful
results that improve on the state of the art for streaming Tucker
decomposition.
