Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time

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