Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time

We consider Tucker-like approximations with an r × r × r core tensor for three-dimensional n × n × n arrays in the case of r n and possibly very large n (up to 10⁴–10⁶). As the approximation contains only O(rn + r³) parameters, it is natural to ask if it can be computed using only a small amount of entries of the given array. A similar question for matrices (two-dimensional tensors) was asked and positively answered in [S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, A theory of pseudo-skeleton approximations, Linear Algebra Appl., 261 (1997), pp. 1–21]. In the present paper we extend the positive answer to the case of three-dimensional tensors. More specifically, it is shown that if the tensor admits a good Tucker approximation for some (small) rank r, then this approximation can be computed using only O(nr) entries with O(nr³) complexity.