Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time

• Published in: SIAM journal on matrix analysis and applications 2008-01, Vol.30 (3), p.939-956
• Main Authors: Oseledets, I. V., Savostianov, D. V., Tyrtyshnikov, E. E.
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Arrays; Data compression; Decomposition; Linear algebra; Methods
• ISSN: 0895-4798; 1095-7162
• DOI: 10.1137/060655894

We consider Tucker-like approximations with an $r \times r \times r$ core tensor for three-dimensional $n \times n \times n$ arrays in the case of $r \ll n$ and possibly very large $n$ (up to $10^4$-$10^6$). As the approximation contains only $\mathcal{O}(rn + r^3)$ 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 $\mathcal{O}(nr)$ entries with $\mathcal{O}(nr^{3})$ complexity.