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^3) complexity.