Complexity Estimation of Cubical Tensor Represented through 3D Frequency-Ordered Hierarchical KLT

Abstract

In this work is introduced one new hierarchical decomposition for cubical tensor of size 2n, based on the well-known orthogonal transforms Principal Component Analysis and Karhunen–Loeve Transform. The decomposition is called 3D Frequency-Ordered Hierarchical KLT (3D-FOHKLT). It is separable, and its calculation is based on the one-dimensional Frequency-Ordered Hierarchical KLT (1D-FOHKLT) applied on a sequence of matrices. The transform matrix is the product of n sparse matrices, symmetrical at the point of their main diagonal. In particular, for the case in which the angles which define the transform coefficients for the couples of matrices in each hierarchical level of 1D-FOHKLT are equal to π/4, the transform coincides with this of the frequency-ordered 1D Walsh–Hadamard. Compared to the hierarchical decompositions of Tucker (H-Tucker) and the Tensor-Train (TT), the offered approach does not ensure full decorrelation between its components, but is close to the maximum. On the other hand, the evaluation of the computational complexity (CC) of the new decomposition proves that it is lower than that of the above-mentioned similar approaches. In correspondence with the comparison results for H-Tucker and TT, the CC decreases fast together with the increase of the hierarchical levels’ number, n. An additional advantage of 3D-FOHKLT is that it is based on the use of operations of low complexity, while the similar famous decompositions need large numbers of iterations to achieve the coveted accuracy.

Keywords

• cubical tensor decomposition
• 3D hierarchical adaptive PCA transform
• 3D Frequency-Ordered Hierarchical KLT
• computational complexity