Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time

Ivan V. Oseledets, Dmitry V. Savostyanov, Eugene E. TyrtyshnikovSIAM J. Matrix Anal. Appl 2008 · DOI · OpenReview

Abstract

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.
BibTeX
@article{oseledets2008tucker,
  author = {Ivan V. Oseledets and Dmitry V. Savostyanov and Eugene E. Tyrtyshnikov},
  title = {{Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2008},
  doi = {10.1137/060655894},
}

Loading related content...

Figure