Tyrtyshnikov: Tucker dimensionality reduction of threedimensional arrays in linear time

Abstract. 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 104−106). As the approximation contains only O(rn+ r3) 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 [14]. 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. Moreover, in many cases it can be computed with O(nr3) complexity. Key words. Multidimensional arrays, Tucker decomposition, tensor approximations, low rank approximations, skeleton decompositions, dimensionality reduction, data compression, large-scale matrices, data-sparse methods. 1. Introduction. Multidimensiona