  Low-tubal-rank tensor approximation has been proposed to analyze large-scale
and multi-dimensional data. However, finding such an accurate approximation is
challenging in the streaming setting, due to the limited computational
resources. To alleviate this issue, this paper extends a popular matrix
sketching technique, namely Frequent Directions, for constructing an efficient
and accurate low-tubal-rank tensor approximation from streaming data based on
the tensor Singular Value Decomposition (t-SVD). Specifically, the new
algorithm allows the tensor data to be observed slice by slice, but only needs
to maintain and incrementally update a much smaller sketch which could capture
the principal information of the original tensor. The rigorous theoretical
analysis shows that the approximation error of the new algorithm can be
arbitrarily small when the sketch size grows linearly. Extensive experimental
results on both synthetic and real multi-dimensional data further reveal the
superiority of the proposed algorithm compared with other sketching algorithms
for getting low-tubal-rank approximation, in terms of both efficiency and
accuracy.
