# TensorCodec: Compact Lossy Compression of Tensors without Strong Data
Assumptions

Taehyung Kwon1, Jihoon Ko1, Jinhong Jung2, and Kijung Shin1
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>1Kim Jaechul Graduate School of AI, KAIST, 2School of
Software, Soongsil University

###### Abstract

Many real-world datasets are represented as tensors, i.e., multi-dimensional
arrays of numerical values. Storing them without compression often requires
substantial space, which grows exponentially with the order. While many tensor
compression algorithms are available, many of them rely on strong data
assumptions regarding its order, sparsity, rank, and smoothness.

In this work, we propose TensorCodec, a lossy compression algorithm for
general tensors that do not necessarily adhere to strong input data
assumptions. TensorCodec incorporates three key ideas. The first idea is
Neural Tensor-Train Decomposition (NTTD) where we integrate a recurrent neural
network into Tensor-Train Decomposition to enhance its expressive power and
alleviate the limitations imposed by the low-rank assumption. Another idea is
to fold the input tensor into a higher-order tensor to reduce the space
required by NTTD. Finally, the mode indices of the input tensor are reordered
to reveal patterns that can be exploited by NTTD for improved approximation.

Our analysis and experiments on $8$ real-world datasets demonstrate that
TensorCodec is (a) Concise: it gives up to $7.38\times$ more compact
compression than the best competitor with similar reconstruction error, (b)
Accurate: given the same budget for compressed size, it yields up to
$3.33\times$ more accurate reconstruction than the best competitor, (c)
Scalable: its empirical compression time is linear in the number of tensor
entries, and it reconstructs each entry in logarithmic time. Our code and
datasets are available at https://github.com/kbrother/TensorCodec.

###### Index Terms:

Tensor, Decomposition, Data Compression

##  I Introduction

A tensor is a multi-dimensional array of numerical values [1] and can be
considered a higher-order generalization of a matrix. Various real-world
datasets, including sensory data [2], stock market history [3], and extracted
features from motion videos [4], are represented as tensors.

Many real-world tensors are large, making compression crucial for efficient
storage. Storing a tensor in its uncompressed form requires space proportional
to the total number of entries, which grows exponentially with the tensor’s
order. For instance, storing a tensor of size $704\times 2049\times 7997$ from
the music dataset [5] as a double-precision floating-point value per entry
consumes approximately $92$GB. This storage approach places a significant
burden on memory-limited devices such as mobile and IoT devices. Moreover,
transmitting such large datasets online can lead to substantial communication
costs.

Consequently, a variety of tensor compression methods have been devised, but
many of them rely on specific assumptions regarding input data, particularly
in terms of order, sparsity, rank, and smoothness. For instance, numerous
compression methods [6, 7] assume that the input tensor is of order two, i.e.,
a matrix. Additionally, many other compression methods [8, 9] are tailored for
compressing sparse tensors, which are tensors with a majority of zero entries.
Another category of compression methods based on tensor decomposition [10, 11,
12, 13] assumes that the input tensor has (approximately) a low-rank
structure. Furthermore, some compression methods [14, 15, 16, 17] presume that
tensor entries exhibit smooth variations, meaning that adjacent entries tend
to be similar, as in images and videos. However, many real-world tensors do
not necessarily conform to these assumptions, as shown in Section V-B.

How can we compactly compress tensors with minimal reconstruction error,
without imposing strong assumptions on data properties? To address this
question, we present TensorCodec, a lossy compression algorithm for general
tensors that do not depend on strict input data assumptions. To achieve this,
we first introduce Neural Tensor-Train Decomposition (NTTD). In contrast to
the original Tensor-Train Decomposition, where factor matrices are fixed for
all entries of a mode index, we use a recurrent neural network to obtain these
matrices, making them dependent on the other mode indices of the entries. This
modification allows NTTD to effectively approximate input tensors with a
limited number of parameters, even when they exhibit high rank. Secondly, we
fold the input tensor into a higher-order tensor, further reducing the number
of parameters needed for NTTD. Lastly, we introduce a reordering algorithm for
the mode indices of the input tensor, which uncovers patterns that NTTD can
exploit for accurate approximation of the tensor entries. The output of
TensorCodec consists of (a) the parameters of the recurrent neural network in
NTTD and (b) the mapping between the original and reordered mode indices,
which are used to approximate the entries of the input tensor.

We demonstrate the advantages of TensorCodec through complexity analysis and
comprehensive experiments on 8 real-world datasets, which are summarized as
follows:

  * •

Concise: It gives up to 7.38$\times$ smaller output than the best-performing
competitor with similar approximation error.

  * •

Accurate: It outperforms the most accurate competitor in terms of
approximation error by up to 3.33$\times$, while achieving comparable
compression sizes.

  * •

Scalable: Its empirical compression time scales linearly with the number of
entries, while the reconstruction time scales logarithmically with the largest
mode size.

We present related works in Section II, give preliminaries in Section III,
propose TensorCodec in Section V, review experiments in Section IV, and make
conclusions in Section VI.

##  II Related work

Compression methods for low-rank tensors: Tensor decomposition compresses
tensors lossily into smaller matrices and tensors. CP Decomposition (CPD) [18]
approximates the input tensor by the weighted sum of the outer products of
columns of the same order in the matrices. That is, the outer product of the
$i$-th columns of the matrices is computed for each $i$. Tucker Decomposition
(TKD) [11] generalizes CPD by allowing outer products of columns of different
orders, and TTHRESH [14] further compresses the outputs of TKD using run-
length and arithmetic coding. Tensor Train Decomppsition (TTD) [12]
approximates each entry by the product of matrices that vary depending on mode
indices, while Tensor Ring Decomposition (TRD) [13] uses the trace of the
product for approximation. That is, if two entries share $k$ mode indices, $k$
matrices are shared for their approximation. The approximation power of these
methods is limited by their reliance on low-rank assumptions and linear
operations, especially when the input tensor does not have a low rank and the
parameter size is restricted, as shown in Section V-B.

Compression methods for smooth tensors: Numerous tensor compression techniques
assume smoothness in the input data, meaning that adjacent entries tend to
have similar values. This assumption is especially prominent for image and
video data. Compression of images and videos constitutes a distinct and
advanced field of study [17, 16], and consequently, this paper focuses on
compression methods for tensors that are neither images nor videos. Smoothness
is also assumed when compressing scientific simulation data [15]. A notable
example, SZ3 [15] performs interpolation for each entry, based on smoothness,
and compactly but lossily encodes the errors using Huffman coding. Naturally,
the compression power of these methods diminishes when the smoothness
assumption is not met, as shown empirically in Section V-B.

Compression methods for sparse tensors: Many real-world tensors are sparse,
i.e. the majority of their entries are zero. This characteristic is commonly
leveraged in the aforementioned tensor decomposition methods for speed and
memory efficiency [19, 20, 21] without affecting the compressed outputs.
NeuKron [9] optimizes the entries of a small tensor, referred to as a seed
tensor, so that its generalized Kronecker power closely approximates the input
tensor. To improve the fit, NeuKron first reorders the mode indices in the
input tensor. NeuKron leverages the sparsity of the input tensor in three
ways: (a) it builds on the observation that real-world sparse matrices exhibit
self-similarity and can thus be approximated by Kronecker powers [22], (b) it
reorders mode indices based on the sparsity patterns of the sub-tensors formed
by the entries with each mode index, and (c) it enables rapid computation of
the objective function by taking advantage of the sparsity. Therefore, NeuKron
has been applied only to extremely sparse tensors where the ratio of non-zero
entries is less than 0.00354 [9]. NeuKron and our proposed TensorCodec share
similarities in that they both employ reordering and generalization using
auto-regressive models. However, TensorCodec generalizes TTD, instead of
Kronecker powers, and reorders mode indices based on the entry values, not on
sparsity patterns. It should be noticed that, unlike Kronecker powers, TTD has
been used to model various real-world tensors without being limited to sparse
ones. Due to these differences, TensorCodec significantly outperforms NeuKron
in terms of both compressed size and approximation accuracy for tensors that
are not extremely sparse, as demonstrated in Section V-B.

Usage of TTD for neural networks: TTD [12] has been utilized to compress
neural-network parameters in the form of tensors, including (a) weights of
fully connected layers [23] and Recurrent Neural Networks [24], and (b)
embeddings in recommender systems [25] and Graph Neural Networks [26]. These
works employ TTD for compressing neural networks, which is distinctly
different from our approach of employing a neural network to enhance the
expressiveness of TTD.

##  III preliminaries

In this section, we introduce preliminaries, followed by a formal definition
of the considered problem. Frequently-used notations are listed in Table I.
For any positive integer $n$, $[n]:=\\{0,\cdots,n-1\\}$ denotes the set of
integers from 0 to $n-1$.

###  III-A Basic Concepts and Notations

Matrix and tensor: We denote matrices in boldface capital letters. Given a
real-valued matrix $\mathbf{M}$ of size $N_{1}\times N_{2}$, the entry located
in the $i$-th row and $j$-th column is denoted by $\mathbf{M}(i,j)$. Tensors
are denoted by boldface Euler script letters. The order of a tensor refers to
the number of modes. Let $\mathbf{\mathcal{X}}$ be a real-valued $d$-order
tensor of size $N_{1}\times\cdots\times N_{d}$. The entry at the
$(i_{1},\cdots,i_{d})$-th position of $\mathbf{\mathcal{X}}$ is denoted by
$\mathbf{\mathcal{X}}(i_{1},\cdots,i_{d})$.

Slicing and reordering a tensor: For a mode-$j$ index $i\in[N_{j}]$,
$\mathbf{\mathcal{X}}^{(j)}(i)\in\mathbb{R}^{N_{1}\cdots N_{j-1}\times
N_{j+1}\cdots N_{d}}$ denotes the $i$-th slice of $\mathbf{\mathcal{X}}$ along
the $j$-th mode, i.e.,
$\mathbf{\mathcal{X}}^{(j)}(i)\coloneqq\mathbf{\mathcal{X}}(:_{1},\cdots,:_{j-1},i,:_{j+1},\cdots,:_{d})$,
where $:_{k}$ indicates all possible mode-$k$ indices (i.e., those in
$[N_{k}]$). We consider reordering of mode indices. Let
${\mathbf{\mathcal{X}}}_{\bm{\pi}}$ denote the tensor reordered from
$\mathbf{\mathcal{X}}$ by a set $\bm{\pi}=\\{\pi_{1},\cdots,\pi_{d}\\}$ of
reordering functions, where each $\pi_{i}:[N_{i}]\rightarrow[N_{i}]$ is a
bijective function from the set of the mode-$i$ indices to themselves. In
${\mathbf{\mathcal{X}}}_{\bm{\pi}}$, the $(i_{1},\cdots,i_{d})$-th entry
corresponds to the $(\pi_{1}(i_{1}),\pi_{2}(i_{2}),...,\pi_{d}(i_{d}))$-th
entry of $\mathbf{\mathcal{X}}$.

Frobenius norm: The Frobenius norm $\lVert\mathbf{\mathcal{X}}\rVert_{F}$ of
$\mathbf{\mathcal{X}}$ is defined as the squared root of the squared sum of
all its entries, i.e.,

$\lVert\mathbf{\mathcal{X}}\rVert_{F}=\sqrt{\sum_{(i_{1},\cdots,i_{d})\in[N_{1}]\times\cdots\times[N_{d}]}\big{(}\mathbf{\mathcal{X}}(i_{1},\cdots,i_{d})\big{)}^{2}}.$
(1)

###  III-B Tensor-Train Decomposition (TTD)

Tensor-Train Decomposition (TTD) [12] decomposes a given $d$-order tensor
$\mathbf{\mathcal{X}}$ into $d$ tensors $\mathbf{\mathcal{G}}_{1}$, $\cdots$,
$\mathbf{\mathcal{G}}_{d}$, called TT cores, so that each entry of
$\mathbf{\mathcal{X}}$ is approximated as follows:

$\mathcal{X}(i_{1},\cdots,i_{d})\approx\mathbf{\mathcal{G}}_{1}^{(2)}(i_{1})\mathbf{\mathcal{G}}_{2}^{(2)}(i_{2})\cdots\mathbf{\mathcal{G}}_{d}^{(2)}(i_{d}),$
(2)

where, for all $k$, $\mathbf{\mathcal{G}}_{k}\in\mathbb{R}^{r_{k-1}\times
N_{k}\times r_{k}}$, and
$\mathbf{\mathcal{G}}_{k}^{(2)}(i)\in\mathbb{R}^{r_{k-1}\times r_{k}}$ is the
$i$-th slice of $\mathbf{\mathcal{G}}_{k}$ along the second mode. Note that
$r_{0}$ and $r_{d}$ are always set to $1$. For simplicity, in this paper, we
unify all other TT ranks (i.e., $r_{1},\cdots,r_{d-1}$) to a single value
denoted by $R$. The representative optimization algorithm for TTD is TT-SVD
[12], which aims to obtain
$\mathbf{\mathcal{G}}_{1},\cdots,\mathbf{\mathcal{G}}_{d}$ satisfying
$\lVert\mathbf{\mathcal{X}}-\mathbf{\mathcal{\tilde{X}}}_{TT}\rVert_{F}\leq\epsilon\lVert\mathbf{\mathcal{X}}\rVert_{F}$
for a prescribed accuracy $\epsilon$, where
$\mathbf{\mathcal{\tilde{X}}}_{TT}$ is the approximated tensor by TTD. In TT-
SVD, Truncated SVD is applied after reshaping a tensor to a matrix. TTD is
naturally used as a lossy tensor compression algorithm, with the compressed
results being the entries of the TT-core tensors. The number of these entries
is $R^{2}\sum_{k=1}^{d}N_{k}=O(dNR^{2})$, where $N$ represents the maximum
mode length.

TABLE I: Symbol description Symbol | Description
---|---
$\mathbf{A}\in\mathbb{R}^{N_{1}\times N_{2}}$ |  $N_{1}$-by-$N_{2}$ matrix
$\mathbf{A}(i,j)$ |  $(i,j)$-th entry of $\mathbf{A}$
$\mathbf{\mathcal{X}}\in\mathbb{R}^{N_{1}\times\cdots\times N_{d}}$ | tensor
$d$ | order of $\mathbf{\mathcal{X}}$
$\mathbf{\mathcal{X}}(i_{1},\cdots,i_{d})$ |  $(i_{1},\cdots,i_{d})$-th entry of $\mathbf{\mathcal{X}}$
$N_{\text{max}}$ | maximum length of modes in $\mathbf{\mathcal{X}}$
${\mathbf{\mathcal{X}}}^{(j)}(i)$ |  $i$-th slice of $\mathbf{\mathcal{X}}$ along the $j$-th mode
$[n]$ | set of consecutive integers from $0$ to $n-1$
$\bm{\pi}=(\pi_{1},\cdots,\pi_{d})$ | set of reordering functions for a tensor
$\pi_{i}$ | reordering function for the $i$-th mode indices
${\mathbf{\mathcal{X}}}_{\bm{\pi}}$ | reordered tensor of $\mathbf{\mathcal{X}}$ by $\bm{\pi}$
$\lVert\mathbf{\mathcal{X}}\rVert_{F}$ | Frobenius norm of $\mathbf{\mathcal{X}}$
$R$ | ranks of TT cores
$h$ | hidden dimension of LSTM
$\theta$ | set of the parameters of NTTD
$\mathbf{\mathcal{\tilde{X}}}$ | approximated tensor of $\mathbf{\mathcal{X}}$ by TensorCodec
$\mathbf{\mathcal{X}}^{\texttt{folded}}$ | folded tensor of $\mathbf{\mathcal{X}}$
$d^{\prime}$ | order of $\mathbf{\mathcal{X}}^{\texttt{folded}}$
$\mathbf{T}_{i}$ |  $i$-th TT core generated by $\theta$

###  III-C Problem Definition

We provide the formal definition of the lossy tensor compression problem
addressed in this paper as follows:

######  Problem 1.

(Lossy Compression of a Tensor) • Given: a tensor
$\mathcal{X}\in\mathbb{R}^{N_{1}\times\cdots\times N_{d}}$, • Find: the
compressed data $D$ • to Minimize: (1) the size of $D$
(2) the approximation error (e.g.,
$\lVert\mathbf{\mathcal{X}}-\mathbf{\mathcal{Y}}\rVert_{F}^{2}$,
where $\mathbf{\mathcal{Y}}$ is the tensor reconstructed from $D$)

In TensorCodec, the compressed data $D$ is composed of (a) the set $\theta$ of
parameters in Neural Tensor-Train Decomposition (NTTD), and (b) the set
$\bm{\pi}$ of reordering functions.

##  IV Proposed Method

In this section, we propose TensorCodec, a precise and concise tensor-
compression algorithm.

###  IV-A Overview

For our method, we focus on the following challenges in devising a compression
algorithm based on TTD:

  1. Q1.

Expressiveness. Since TTD (see Section III-B) relies only on linear operations
of small-sized matrices, its expressiveness is limited.111For a more in-depth
discussion of expressiveness, refer to [12]. How can we enhance its
expressiveness to closely approximate a wider variety of tensors?

  2. Q2.

Conciseness. The number of parameters of TTD increases with the order, mode
length, and TT-rank. Can we further reduce the parameter number for additional
compression?

  3. Q3.

Data arrangement. The approximation by TTD depends on the arrangement of
tensor entries since it shares TT cores based on mode indices. How can we re-
arrange tensor entries to achieve a more accurate approximation?

TensorCodec is based on the following ideas for addressing each of the
aforementioned challenges:

  1. A1.

Neural Tensor-Train Decomposition (NTTD). We incorporate an auto-regressive
neural network into TTD to improve its expressiveness while maintaining the
number of parameters small (Section IV-B).

  2. A2.

Folding. We fold the input tensor into a higher-order tensor to reduce the
number of parameters and thus the size of the compressed output (Section
IV-C).

  3. A3.

Reordering. We aid the model in better fitting the folded tensor by reordering
the mode indices of the input tensor (Section IV-D).

We summarize the overall process of TensorCodec in Algorithm 1. First,
TensorCodec initializes the NTTD model $\theta$ and the reordering functions
$\bm{\pi}$. Next, it reorders and folds $\mathbf{\mathcal{X}}$, creating a
higher-order tensor ${\mathbf{\mathcal{X}}}_{\bm{\pi}}^{\texttt{folded}}$.
Subsequently, the model parameters and reordering functions are updated to
minimize the approximation error. TensorCodec repeats this process until
convergence is reached, meaning that the approximation error no longer
exhibits significant changes. The outputs of the compression process are
optimized $\theta$ and $\bm{\pi}$ based on which each tensor entry is
approximated in logarithmic time, as proven in Section IV-E.

To simplify the explanation, we assume that the input tensor
${\mathbf{\mathcal{X}}}$ is already properly ordered in Sections IV-B and
IV-C. Afterward, we elaborate on how to initialize and update reordering
functions $\bm{\pi}$ in Section IV-D.

Figure 1: The overall process of Neural Tensor-Train Decomposition (NTTD),
which is the key component of TensorCodec. In order to generate TT cores for
approximation, the mode indices of a target entry are encoded through an
embedding layer and fed into an LSTM layer. Each TT core is obtained through a
linear layer from the LSTM output. An approximation is computed by the matrix
product of the TT cores. Note that the parameters of NTTD are those of the
neural networks, not TT cores themselves.

Input: a tensor $\mathbf{\mathcal{X}}\in\mathbb{R}^{N_{1}\times\cdots\times
N_{d}}$

Output: orders $\bm{\pi}$ and an NTTD model $\theta$

1 intialize $\theta$ and $\bm{\pi}$ $\triangleright$ Section IV-D and Alg. 4
of [27]

2 while  _${fitness}$ does not converge_ do

3 ${\mathbf{\mathcal{X}}}_{\bm{\pi}}^{\texttt{folded}}\leftarrow$ reorder and
fold $\mathbf{\mathcal{X}}$ $\triangleright$ Section IV-C

4 Update $\theta$ $\triangleright$ Section IV-B

5 Update $\bm{\pi}$ $\triangleright$ Section IV-D and Alg. 3

6 $\mathbf{\mathcal{\tilde{X}}}\leftarrow$ approximation using $\theta$ and
$\bm{\pi}$

7 ${fitness}\leftarrow
1-\lVert\mathbf{\mathcal{X}}-\mathbf{\mathcal{\tilde{X}}}\rVert_{F}/\lVert\mathbf{\mathcal{X}}\rVert_{F}$

8

return $\theta$ and $\bm{\pi}$

Algorithm 1 Overview of TensorCodec

###  IV-B Neural TT Decomposition (NTTD) for Fitting a Tensor

TensorCodec is a lossy compression algorithm, and its primary goal is to
accurately approximate tensor entries with a small number of parameters. As a
key component of TensorCodec, we propose Neural Tensor-Train Decomposition
(NTTD), a generalization of Tensor-Train Decomposition (TTD) that incorporates
an auto-regressive neural network.

Input: (a) an index $(i_{1},\cdots,i_{d})$

(b) parameters of embedding layers ($E_{1},\cdots,E_{d}$)

(c) parameters of an LSTM layer

(d) parameters of linear layers ($\mathbf{W}_{\\{1,d\\}}$, $\mathbf{W}$,
$\mathbf{b}_{\\{1,d\\}}$, $\mathbf{b}$)

Output: an approximated entry $\theta(i_{1},\cdots,i_{d})$

1 for  _$k\leftarrow 1$ to $d$_ do

2 $\mathbf{e}_{k}\leftarrow E_{k}(i_{k})$

3

4$\mathbf{h}_{1},\cdots,\mathbf{h}_{d}\leftarrow\texttt{LSTM}(\mathbf{e}_{1},\cdots,\mathbf{e}_{d})$
$\triangleright$ $\mathbf{h}_{k}\in\mathbb{R}^{h}$ for $1\leq k\leq d$

5 $\mathbf{T}_{1}\leftarrow\mathbf{W}_{1}\mathbf{h}_{1}+\mathbf{b}_{1}$
$\triangleright$ $\mathbf{W}_{1}\in\mathbb{R}^{1\times R\times h}$ and
$\mathbf{b}_{1}\in\mathbb{R}^{1\times R}$

6 for  _$k\leftarrow 2$ to $d-1$_ do

7 $\mathbf{T}_{k}\leftarrow\mathbf{W}\mathbf{h}_{k}+\mathbf{b}$
$\triangleright$ $\mathbf{W}\in\mathbb{R}^{R\times R\times h}$ and
$\mathbf{b}\in\mathbb{R}^{R\times R}$

8

9$\mathbf{T}_{d}\leftarrow\mathbf{W}_{d}\mathbf{h}_{d}+\mathbf{b}_{d}$
$\triangleright$ $\mathbf{W}_{d}\in\mathbb{R}^{R\times 1\times h}$ and
$\mathbf{b}_{d}\in\mathbb{R}^{R\times 1}$

return $\mathbf{T}_{1}\mathbf{T}_{2}\cdots\mathbf{T}_{d}$

Algorithm 2 Approximation of an entry by NTTD ($\theta$)

Instead of directly learning TT cores as free variables, for each
$(i_{1},\cdots,i_{d})$-th entry of the tensor, TT cores are obtained as the
output of a neural network that takes the mode indices of the entry as an
input. The neural network, which we denote by $\theta$, is trained to
approximate the entry as follows:

$\mathbf{\mathcal{X}}(i_{1},\cdots,i_{d})\approx\theta(i_{1},\cdots,i_{d})=\mathbf{T}_{1}\mathbf{T}_{2}\cdots\mathbf{T}_{d},$
(3)

where $\mathbf{T}_{1}\in\mathbb{R}^{1\times R}$,
$\mathbf{T}_{2}\in\mathbb{R}^{R\times R}$, $\cdots$,
$\mathbf{T}_{d-1}\in\mathbb{R}^{R\times R}$, and
$\mathbf{T}_{d}\in\mathbb{R}^{R\times 1}$ are the TT cores generated by
$\theta$.

Detailed procedures of NTTD are given in Algorithm 2 and illustrated in Figure
1. Note that NTTD consists of embedding, LSTM [28], and linear layers. To
encode each mode index $i_{k}$, our model first looks up the embedding
$\mathbf{e}_{k}$ from the embedding layer $E_{k}$ (lines 2 and 2). Then, it
feeds the embeddings $\mathbf{e}_{k}$ into the LSTM layer and obtains the
hidden embeddings $\mathbf{h}_{k}$ for $1\leq k\leq d$ (line 2). After
generating TT cores $\mathbf{T}_{k}$ from $\mathbf{h}_{k}$ using the linear
layers (lines 2-2), the product of the TT cores is returned as the
approximated entry value (line 2)222To further reduce the model size, we share
the same embedding parameters for modes of the same length (i.e.,
$E_{k}=E_{j}$ if $N_{k}=N_{j}$). The effect of this approach is explored in
Section V of [27]..

Note that we employ an auto-regressive model to allow for the dependency
between TT cores and mode indices. However, in NTTD, each $\mathbf{T}_{k}$
depends not only on the mode-$k$ index of the target entry (as in TTD) but
also on its mode-$j$ indices for all $j\leq k$. While we employ LSTM [28], any
alternatives, such as GRU [29] and Scaled Dot-product Attention [30], can be
used instead. In Section 8 of [27], we examine the performance of TensorCodec
equipped with alternatives.

Benefits over TTD: The NTTD model $\theta$ has the following advantages over
traditional TTD:

  * •

Contextual: In NTTD, as mentioned earlier, each TT core varies depending on
not only the current mode index but also all preceding mode indices. For
example, consider approximating $\mathbf{\mathcal{X}}(2,1,2)$ and
$\mathbf{\mathcal{X}}(1,2,2)$. The TT cores used for the third mode in NTTD
are different in these two cases. However, in TTD, the same TT core is used
for both cases since the third mode indices are identical. By being contextual
and non-linear (described below), NTTD is able to model tensors that cannot be
easily approximated by TTD, even with more parameters, as shown experimentally
in Section V-E. This improved expressiveness reduces the reliance on
structural assumptions about input tensors.

  * •

Non-linear: NTTD incorporates non-linear operations introduced by the LSTM
layer, while TTD does not. This contributes to enhancing the expressiveness of
NTTD, enabling TensorCodec to better approximate tensor entries.

  * •

Concise: NTTD shares parameters (specifically, $\mathbf{W}$ and $\mathbf{b}$
in line 2 of Algorithm 2) for different modes, which enables the model to be
concise with fewer parameters than TTD. In contrast, TTD requires a unique TT
core for each mode.

We empirically examine the contribution of each component of NTTD to
approximation accuracy in Section V-C.

Space complexity analysis: We present the compressed output size of NTTD in
Theorem 1. The hidden dimension of LSTM and the rank of TT cores are denoted
by $h$ and $R$.

######  Theorem 1 (Compressed Output Size of NTTD).

The size of the compressed output of NTTD (i.e., the number of its parameters)
is $O(h(h+R^{2}+\sum_{i=1}^{d}N_{i}))$, which becomes $O(\sum_{i=1}^{d}N_{i})$
if we treat $h$ and $R$ as constants.

###### Proof.

The embedding layers have $O(\sum_{i=1}^{d}N_{i}h)$ parameters. The LSTM and
fully connected layers have $O(h^{2}+hR^{2})$ parameters. Hence, the total
size is $O(h(h+R^{2}+\sum_{i=1}^{d}N_{i}))$. ∎

Optimization method for $\theta$: We update the parameters $\theta$ of NTTD
using mini-batch gradient descent to minimize the loss function in Problem 1,
i.e., $\lVert\mathbf{\mathcal{X}}-\mathbf{\mathcal{Y}}\rVert_{F}^{2}$, where
$\mathbf{\mathcal{Y}}$ is the tensor approximated by $\theta$. As outlined in
Section IV-A, we alternately update $\theta$ and the reordering functions
$\pi$. After updating $\pi$, we reinitialize the optimizer (spec., Adam [31])
since the loss surface changes after reordering, as detailed in Section IV-D.

###  IV-C Folding Technique for Lightweight NTTD

Figure 2: An example of folding an 8$\times$8 matrix into a
4$\times$4$\times$4 tensor, where entries with similar values have similar
colors. Note that when the rows of the matrix are reordered (R) such that
adjacent rows are similar, the similar entries are located close to each other
when the tensor is folded (F). In particular, similar entries share mode-$1$
and $2$ indices in the folded tensor.

We discuss the folding technique, which serves as the second component of
TensorCodec. It aims to further reduce the size of the compressed output of
NTTD, which is proportional to $\sum_{i=1}^{d}N_{i}$ according to Theorem 1.
The main idea is to fold the input tensor into a higher-order tensor,
maintaining the same number of entries but with smaller mode lengths. In
TensorCodec, the NTTD model $\theta$ aims to fit the folded tensor rather than
the input tensor after the arrangement process discussed in Section IV-D.

TT-matrix format: Our folding technique is inspired by the TT-matrix format
[12], which aims to fold a matrix into a tensor for reducing the number of
parameters in TTD. Given a matrix $\mathbf{A}$ of size $N\times M$ where
$N=\prod_{k=1}^{d}n_{k}$ and $M=\prod_{k=1}^{d}m_{k}$, the format folds
$\mathbf{A}$ into a $d$-order tensor $\mathbf{\mathcal{A}}$ of size
$n_{1}m_{1}\times\cdots\times n_{d}m_{d}$ (see the example with $d=3$ in
Figure 2) so that each entry of $\mathbf{A}$ is mapped to an entry of
$\mathbf{\mathcal{A}}$ as follows:

$\mathbf{A}(i,j)=\mathbf{\mathcal{A}}(i_{1}m_{1}+j_{1},\cdots,i_{d}m_{d}+j_{d}),$

where $i_{k}\in[n_{k}]$ and $j_{k}\in[m_{k}]$ for each $1\leq k\leq d$ are
those satisfying $i=\sum_{k=1}^{d}i_{k}\prod_{l=k+1}^{d}n_{l}$ and
$j=\sum_{k=1}^{d}j_{k}\prod_{l=k+1}^{d}m_{l}$. The impact of this folding
technique on NTTD is discussed below in the context of more general cases.

TT-tensor format: While the TT-matrix format can be naturally extended to
tensors, to the best of our knowledge, there has been no attempt to do so. In
this work, we extend the TT-matrix format to tensors by folding the input
tensor into a higher-order tensor with smaller mode lengths. We call this
process the TT-tensor format. Given a tensor $\mathbf{\mathcal{X}}$ of size
$N_{1}\times\cdots\times N_{d}$ where $N_{k}=\prod_{l=1}^{d^{\prime}}n_{k,l}$,
we fold $\mathcal{X}$ into a $d^{\prime}$-order tensor
$\mathbf{\mathcal{X}}^{\texttt{folded}}$ of size
$\prod_{k=1}^{d}n_{k,1}\times\cdots\times\prod_{k=1}^{d}n_{k,d^{\prime}}$.
Then, the mapping between the entries of $\mathbf{\mathcal{X}}$ and
$\mathbf{\mathcal{X}}^{\texttt{folded}}$ is:

$\displaystyle\mathbf{\mathcal{X}}\Big{(}\sum_{k=1}^{d^{\prime}}(i_{1,k}\prod_{l=k+1}^{d^{\prime}}n_{1,l}),\cdots,\sum_{k=1}^{d^{\prime}}(i_{d,k}\prod_{l=k+1}^{d^{\prime}}n_{d,l})\Big{)}$
(4)
$\displaystyle\rightarrow\mathbf{\mathcal{X}}^{\texttt{folded}}\Big{(}\sum_{k=1}^{d}(i_{k,1}\prod_{l=k+1}^{d}n_{l,1}),\cdots,\sum_{k=1}^{d}(i_{k,d^{\prime}}\prod_{l=k+1}^{d}n_{l,d^{\prime}})\Big{)},$

where $i_{k,l}\in[n_{k,l}]$ for all $k\in\\{1,\cdots,d\\}$ and
$l\in\\{1,\cdots,d^{\prime}\\}$.

In TensorCodec, we select the new order $d^{\prime}$ such that the folded
tensor has a higher order than the input tensor (i.e., $d^{\prime}>d$), while
maintaining $d^{\prime}=O(\log N_{\text{max}})$, where $N_{\text{max}}$
represents the maximum mode length in the input tensor $\mathbf{\mathcal{X}}$.
In real-world tensors, this is usually feasible since their mode lengths are
usually much larger than their orders. For instance, a 4-order tensor of size
$256\times 256\times 256\times 256$ can be folded into an 8-order tensor with
each mode having a length of 16. It may not always be feasible to construct a
folded tensor that meets the above criteria while having the same number of
entries as the input tensor. In such cases, the folded tensor may contain
extra entries, the values of which are disregarded. For real-world tensors
(see Section V), we initially assign $2$ to $n_{k,l}$ for all
$k\in\\{1,\cdots,d\\}$ and $l\in\\{1,\cdots,d^{\prime}\\}$ and modify some of
them using integers at most $5$ to ensure that the input and folded tensors
have similar numbers of entries. For example, for the PEMS-SF dataset (a
3-order tensor of size $963\times 144\times 440$), the assigned values in the
form of a $d$ by $d^{\prime}$ matrix are

$\left[\begin{array}[]{*{20}c}2&2&2&2&2&2&2&2&2&2\\\ 2&2&2&2&2&5&1&1&1&1\\\
2&2&2&2&2&2&2&2&2&1\end{array}\right],$

which result in a $10$-order tensor of size $8\times 8\times 8\times 8\times
8\times 20\times 4\times 4\times 4\times 2$. Note that
$\prod_{l=1}^{d^{\prime}}n_{1,l}=1024$, $\prod_{l=1}^{d^{\prime}}n_{2,l}=160$,
$\prod_{l=1}^{d^{\prime}}n_{3,l}=512$ are close to $963$, $144$, and $440$,
respectively. See Section IV of [27] for the values used for other datasets.

Space complexity analysis: We analyze the effect of folding on the number of
parameters (i.e., size of compressed output) in $\theta$. For simplicity, we
assume $n_{k,l}=\sqrt[d^{\prime}]{N_{k}}$ for all $k\in[d]$ and
$l\in[d^{\prime}]$. According to Theorem 1, the number of parameters of NTTD
of the original $\mathbf{\mathcal{X}}$ is

$O\Big{(}\sum_{k=1}^{d}\prod_{l=1}^{d^{\prime}}n_{k,l}\Big{)}=O(N_{1}+\cdots+N_{d}),$

if we treat $h$ and $R$ as constants.

The number of parameters of NTTD of $\mathbf{\mathcal{X}}^{\texttt{folded}}$
is

$O\Big{(}\sum_{l=1}^{d^{\prime}}\prod_{k=1}^{d}n_{k,l}\Big{)}=O\Big{(}d^{\prime}\\!\\!\sqrt[d^{\prime}]{N_{1}\cdots
N_{d}}\Big{)},$

which is significantly smaller than $O(N_{1}+\cdots+N_{d})$ in NTTD of the
original tensor since
$O\left(d^{\prime}\cdot\\!\\!\sqrt[d^{\prime}]{\prod_{k=1}^{d}{N_{k}}}\right)\in
o(N_{\text{max}})$, where $N_{\text{max}}$ is the maximum mode length in
$\mathbf{\mathcal{X}}$. This is because $d^{\prime}=O(\log N_{\text{max}})$,
$d^{\prime}>d$, and thus
$O\left(d^{\prime}\cdot\\!\\!\sqrt[d^{\prime}]{\prod_{k=1}^{d}{N_{k}}}\right)=O(N_{\text{max}}^{e}\log
N_{\text{max}})$ for some $e<1$. If we consider $R$ and $h$, according to
Theorem 1, the space complexity becomes

$O\Big{(}h\Big{(}h+R^{2}+d^{\prime}\\!\\!\sqrt[d^{\prime}]{N_{1}\cdots
N_{d}}\Big{)}\Big{)}.$ (5)

###  IV-D Reordering Technique for Better Fitting a Folded Tensor

We present the reordering technique, the last component of TensorCodec.
Essentially, we reorder the mode indices in the input tensor before folding so
that entries with similar values are placed close to each other by sharing
mode indices in the folded tensor. This arrangement improves the ability of
our NTTD model $\theta$, to fit the folded tensor more effectively, as
$\theta$ generates TT cores based on mode indices of target entries that serve
as input for the model.

In the example in Figure 2, the closer two entries are located in the original
tensor, the more indices they tend to share in the folded tensor.
Specifically, the entries in the black region share only the first mode index
in the folded tensor. The adjacent entries in the blue region share both the
first and second mode indices in the folded tensor. It is important to note
that in our model $\theta$, the $k$-th TT cores $\mathbf{T}_{k}$ in Eq. (3)
for approximating two entries are the same if their first $k$ indices are the
same. Consequently, two TT cores are shared for the entries in the blue
region. Therefore, the closer two entries are located in the original tensor,
the more inputs and TT cores of $\theta$ are likely to share for these
entries. Due to this property, positioning similar entries close to each other
helps $\theta$ easily approximate entries more accurately. We achieve such re-
locations by reordering mode indices in the input tensor, as demonstrated in
the example in Figure 2, where the blue region comprises more similar entries
after reordering.

In TensorCodec, the mode-index reordering is accomplished by learning
reordering functions $\bm{\pi}$. As outlined in Section IV-A, we alternately
update the model $\theta$ and $\bm{\pi}$. In the following, we describe the
initialization and update procedures for $\bm{\pi}$. It is worth noting that
mode-index ordering by TensorCodec is associated with increasing smoothness,
which is discussed in Section I, while many other compression methods presume
that the input tensor is already highly smooth.

Initializing the orders: We initialize the set $\bm{\pi}$ of reordering
functions using a surrogate loss function. For all $k$, reordering the
mode-$k$ indices (i.e., optimizing $\pi_{k}$) is formulated as:

$\vspace{-2mm}\min_{\pi_{k}}\sum_{i=1}^{N_{k}-1}\left(\lVert{\mathbf{\mathcal{X}}}^{(k)}(\pi_{k}(i))-{\mathbf{\mathcal{X}}}^{(k)}(\pi_{k}(i+1))\rVert_{F}\right),$
(6)

where ${\mathbf{\mathcal{X}}}^{(k)}(i)$ is the $i$-th slice of
$\mathbf{\mathcal{X}}$ along the $k$-th mode. Note that minimizing Eq. (6)
makes adjacent slices similar.

The problem in Eq. (6) can be reduced to Metric Travelling Salesman Problem
[32]. Suppose each node represents a slice of the tensor, and each pair of
nodes forms an edge with a weight equal to the Frobenius norm of the
difference between their slices. Then, the optimal solution of the TSP problem
on the resulting complete graph can be used to minimize Eq. (6). However,
since computing it is NP-hard, we instead obtain a 2-approximation solution
based on the fact that the Frobenius norm satisfies the triangle inequality.
Then, we delete the edge with the largest weight from the obtained solution,
which is a TSP cycle, and set each $i$-th node in the resulting path to
$\pi_{k}(i)$. Refer to Section II of [27] for details on the TSP problem and
the 2-approximation algorithm, including pseudocode.

Updating the orders based on $\theta$ (Algorithm 3): As outlined in Section
IV-A, after updating the NTTD model $\theta$, we update the set $\bm{\pi}$ of
reordering functions based on updated $\theta$ and the loss function in
Problem 1. This update step is described in Algorithm 3. As defined in Section
III-A, we use ${\mathbf{\mathcal{X}}}_{\bm{\pi}}$ to denote the tensor
reordered from $\mathbf{\mathcal{X}}$ by $\bm{\pi}$. For each $k$-th mode, we
consider $\left\lfloor N_{k}/2\right\rfloor$ disjoint candidate pairs of
mode-$k$ indices (lines 17-18). The process of obtaining candidate pairs is
described in the following paragraph. For each pair $(i,i^{\prime})$ of mode
indices, we consider the corresponding slices
${\mathbf{\mathcal{X}}}_{\bm{\pi}}^{(k)}(i)$ and
${\mathbf{\mathcal{X}}}_{\bm{\pi}}^{(k)}(i^{\prime})$. If swapping them
reduces the loss function in Problem 1, we swap the values of $\pi_{k}(i)$ and
$\pi_{k}(i^{\prime})$ (lines 22-24). Note that, since pairs are disjoint, we
can compute the changes in the loss and update $\pi_{k}$ in parallel using
GPUs.

In the above process, each pair is composed so that swapping them tends to
make similar slices located nearby in ${\mathbf{\mathcal{X}}}_{\bm{\pi}}$. We
find such pairs using locality-sensitivity hashing (LSH) for Euclidean
distance [33]. We sample half of the indices in each mode and vectorize the
corresponding slices as points in a high-dimensional space. We project the
vectorized slices onto a random vector (lines 6-10) and evenly divide the
projected points to create buckets. We then repeatedly select two points in
the same bucket. Assuming that corresponding mode indices are $i_{1}$ and
$i_{2}$, two pairs $(i_{1},i_{2}\oplus 1)$ and $(i_{1}\oplus 1,i_{2})$ are
added as candidate pairs where $\oplus$ denotes the XOR operation (lines
17-18). This approach aims to locate indices corresponding to similar slices
nearby. The remaining mode indices are paired randomly (lines 19-21). The
effectiveness of the reordering process is experimentally validated in Section
V-C.

Input: (a) a tensor
$\mathbf{\mathcal{X}}\in\mathbb{R}^{N_{1}\times\cdots\times N_{d}}$, (b) a
NTTD model $\theta$,

(c) orders $\pi_{1},\cdots,\pi_{d}$

Output: updated orders $\pi_{1},\cdots,\pi_{d}$

1

2for  _$k$ $\leftarrow$ $1$ to $d$_ do

// Project each slice

3 $I\leftarrow\emptyset$

4 for  _$j\leftarrow 0$ to $N_{k}-1$ by $2$_ do

5 $u\sim U(0,1)$

6 if $u$ $<$ $1/2$ then $I$ $\leftarrow$ $I\cup\\{j\\}$ else $I$ $\leftarrow$
$I\cup\\{j+1\\}$

7

8 $s\leftarrow(\prod_{j=1}^{d}N_{j})/N_{k}$; $P\leftarrow\emptyset$

9 $r\leftarrow$ a random point from $\mathbb{R}^{s}$

10 foreach  _$j\in I$_ do

11 $v\leftarrow$ vec$({\mathbf{\mathcal{X}}}^{(k)}(j))$

12 $P[j]\leftarrow r\cdot v/(\lVert r\rVert_{F}\lVert v\rVert_{F})$

// Hash points to buckets

13 $num\\_buckets\leftarrow\left\lfloor N_{k}/8\right\rfloor$

14 $bs\leftarrow\left\lfloor(\max(P)-\min(P))/num\\_buckets\right\rfloor$;
$B\leftarrow\emptyset$

15 foreach  _$j\in I$_ do

16 $bi\leftarrow\left\lfloor(P[j]-\min(P))/bs\right\rfloor$

17 $B[bi]\leftarrow(B[bi]\cup\\{j\\}$)

// Build pairs (run in parallel)

18 $S\leftarrow\emptyset$; $S^{\prime}\leftarrow\emptyset$

19 foreach  _$b\in B$_ do

20 $\textnormal{{AddPairs}}(b,S,True)$ $\triangleright$ Defined below

21 $S^{\prime}\leftarrow S^{\prime}\cup b$

22 $S^{\prime}\leftarrow S^{\prime}\cup\\{j\oplus 1:j\in S^{\prime}\\}$

23 $\textnormal{{AddPairs}}(S^{\prime},S,False)$

// Update orders (run in parallel)

24 foreach  _$(i,i^{\prime})\in S$_ do

25 $\Delta\leftarrow$ change in the loss when $\pi_{k}(i)$,
$\pi_{k}(i^{\prime})$ are exchanged

26 if  _$\Delta <0$_ then
$\pi_{k}(i),\pi_{k}(i^{\prime})\leftarrow\pi_{k}(i^{\prime}),\pi_{k}(i)$

27

28return $\pi_{1},\cdots,\pi_{d}$

29 Function  _AddPairs( C, S, xor)_

30 while  _$|C| >1$_ do

31 Randomly sample $(i_{1},i_{2})$ from $C$

32 if  _$xor$_ then $S\leftarrow S\cup\\{(i_{1},i_{2}\oplus
1)\\}\cup\\{(i_{1}\oplus 1,i_{2})\\}$

33 else $S\leftarrow S\cup\\{(i_{1},i_{2})\\}$

34 $C\leftarrow C\setminus\\{i_{1},i_{2}\\}$

Algorithm 3 Update of the reordering functions $\bm{\pi}$

###  IV-E Theoretical Analysis

We theoretically analyze TensorCodec’s compressed-output size, entry-
reconstruction speed, and compression speed. For simplicity, we assume that
all mode sizes of the input tensor
$\mathbf{\mathcal{X}}\in\mathbb{R}^{N_{1}\times\cdots\times N_{d}}$ are powers
of 2 (i.e., $n_{l,k}\in\\{1,2\\}$ for all $l\in\\{1,\cdots,d\\}$ and
$k\in\\{1,\cdots,d^{\prime}\\}$ in Section IV-C). We use $N_{\text{max}}$ to
denote the maximum size of modes in $\mathbf{\mathcal{X}}$, and use $h$ and
$R$ to denote the hidden dimension and TT rank of our model.

Size of compressed outputs: We present the space complexity of the outputs
produced by TensorCodec in Theorem 2. It is important to note that the
complexity is much lower than $O(\prod_{i=1}^{d}N_{i})$ of the original tensor
and can also be lower than $O(R^{2}\sum_{i=1}^{d}N_{i})$ of TTD and
$O(R\sum_{i=1}^{d}N_{i})$ of CP Decomposition (CPD), especially for large
values of $R$.

######  Theorem 2 (Size of Compressed Outputs).

The size of the compressed output $D=(\theta,\bm{\pi})$ produced by
TensorCodec (i.e., Algorithm 1) is $O(h(2^{d}+h+R^{2})+\sum_{i=1}^{d}N_{i}\log
N_{i})$.

###### Proof.

The embedding layer of $\theta$ has $O(h2^{d})$ parameters because our model
shares the embedding layers across different modes in
${X}_{\bm{\pi}}^{\texttt{folded}}$ and the largest mode size of
${X}_{\bm{\pi}}^{\texttt{folded}}$ is $2^{d}$, as detailed in Section IV-C.
The numbers of parameters of LSTM and fully connected layers are
$O(h^{2}+hR^{2})$ since the number of parameters of each linear layer is
proportional to the product of the input dimension and the output dimension.
For each mode $i$, the number of all possible orderings of $\pi_{i}$ is
$N_{i}!$. Thus, we need $O(\log N_{i}!)\in O(N_{i}\log N_{i})$ bits to save
one among them. Hence, the total size of the compressed output is
$O(h(2^{d}+h+R^{2})+\sum_{i=1}^{d}N_{i}\log N_{i})$. ∎

Speed of reconstruction: Another important aspect of a compression algorithm
is the speed of reconstruction. Theorem 3 formalizes the reconstruction speed
for the output of TensorCodec. While the complexity is higher than $O(dR^{2})$
of TTD or $O(dR)$ of CPD, it is only logarithmic in mode lengths.

######  Theorem 3 (Reconstruction Speed).

Given the output $D=(\theta,\bm{\pi})$ of TensorCodec (i.e., Algorithm 1),
approximating the value of an input tensor entry (i.e., Algorithm 2 on
${\mathbf{\mathcal{X}}}_{\bm{\pi}}$) takes $O((d+h^{2}+hR^{2})\log
N_{\textnormal{max}})$ time.

###### Proof.

For each entry of $\mathbf{\mathcal{X}}$, earning the mode indices in
${\mathbf{\mathcal{X}}}_{\bm{\pi}}$ requires $O(d)$ time. Computing the mode
indices in ${\mathbf{\mathcal{X}}}_{\bm{\pi}}^{\texttt{folded}}$ requires
$O(d\log N_{\text{max}})$ time because all $i_{kl}$ in Eq. (4) must be
computed where $k$ ranges from 1 to $d$ and $l$ ranges from 1 to
$d^{\prime}=O(\log N_{\text{max}})$. Processing the inputs through the
embedding layer and LSTM in $\theta$ requires $O(h^{2}\log N_{\text{max}})$
time. The time complexity of computing TT cores with fully connected layers is
$O(hR^{2}\log N_{\text{max}})$, and that of computing products of TT cores is
$O(R^{2}\log N_{\text{max}})$, provided that the order of computations is
optimized. Therefore, the total time complexity of approximating each entry is
$O((d+h^{2}+hR^{2})\log N_{\text{max}})$. ∎

Speed of compression: We analyze the speed of the compression process of
TensorCodec.

######  Theorem 4 (Compression Speed).

The time complexity of TensorCodec (i.e., Algorithm 1) with $T$ update steps
is $O((Td(d+h^{2}+hR^{2})\log
N_{\textnormal{max}}+\sum_{i=1}^{d}N_{i})\prod_{i=1}^{d}N_{i})$, where
$\prod_{i=1}^{d}N_{i}$ is the number of tensor entries.

Proof Sketch. Initializing all reordering functions $\bm{\pi}$ takes
$O((\sum_{i=1}^{d}N_{i})\cdot(\prod_{i=1}^{d}N_{i}))$ time. Updating $\theta$
and $\pi$ once (i.e., lines 1-1) takes
$O(d(d+h^{2}+hR^{2})\prod_{i=1}^{d}N_{i}\log N_{\textnormal{max}})$ time. For
a full proof, see Section I of [27]. ∎

Connection to actual running time: In Sections V-D, we measure the actual
running time for compression and reconstruction to confirm the time
complexity. In practice, the term $\prod_{i=1}^{d}N_{i}$, which corresponds to
the number of entries, is much larger and also increases much faster than all
other terms, and as thus the compression time increases near linearly with it.

Memory requirements: The complexity of memory space required for compression
by TensorCodec does not exceed the combined memory requirements for a mini-
batch, the compressed output, and the reordering functions.

######  Theorem 5 (Memory Requirements for Compression).

TensorCodec (Algorithm 1) requires $O(Bd+h(2^{d}+B(h+R^{2})\log
N_{\textnormal{max}})+\sum_{i=1}^{d}N_{i})$ memory space, where $B$ is the
number of tensor entries in a mini-batch.

###### Proof.

Refer to Section I of [27]. ∎

##  V Experiments

We review our experiments for the following questions:

  1. Q1.

Compression Performance: How accurately and compactly does TensorCodec
compress real-world tensors?

  2. Q2.

Ablation Study: How effective is each component of TensorCodec for
reconstruction accuracy?

  3. Q3.

Scalability: How does TensorCodec’s compression and reconstruction time scale
with input tensor size?

  4. Q4.

Further Inspection: Can our method accurately compress high-rank tensors? How
does it reorder mode indices?

  5. Q5.

Compression Time: How does the speed of compression by TensorCodec compare to
that of its competitors?

  6. Q6.

Effect of Hyperparameters (Section VII of [27]): How sensitive is TensorCodec
to hyperparameter settings?

TABLE II:  Statistics of public real-world datasets used in the paper.

Name | Size | Order | Order | Density | Smoothness
---|---|---|---|---|---
(Original) | (Folded)
Uber | $183\times 24\times 1140$ | 3 | 9 | 0.138 | 0.861
Air Quality | $5600\times 362\times 6$ | 12 | 0.917 | 0.513
Action | $100\times 570\times 567$ | 8 | 0.393 | 0.484
PEMS-SF | $963\times 144\times 440$ | 10 | 0.999 | 0.461
Activity | $337\times 570\times 320$ | 8 | 0.569 | 0.553
Stock | $1,317\times 88\times 916$ | 10 | 0.816 | 0.976
NYC |  $265\times 265\times 28\times 35$ | 4 | 7 | 0.118 | 0.788
Absorb |  $192\times 288\times 30\times 120$ | 7 | 1.000 | 0.935

(a) Stock (b) Activity (c) Action (d) Air Quality (e) PEMS-SF (f) Uber (g)
Absorb (h) NYC

Figure 3:  TensorCodec provides compact and accurate tensor compression. Its
compressed size is up to 7.38$\times$ smaller than that of the best competitor
showing similar fitness. Given a budget for compressed size, TensorCodec shows
up to 3.33$\times$ higher fitness than the best baseline.

###  V-A Experimental Settings

Machine: For TensorCodec and NeuKron, which require GPUs, we used a machine
with 4 RTX 2080Ti GPUs and 128GB RAM. For all other algorithms, we used a
machine with an i5-9600K (6 cores) and 64GB RAM. Note that the outputs are
independent of machine specifications.

Datasets: We used 8 real-valued tensors from real-world datasets to verify the
effectiveness of our method. We provide basic statistics of the tensors in
Table II. Smoothness is defined as
$1-\frac{\mathbb{E}_{i}[\sigma_{3}(i)]}{\sigma}$, where $\sigma_{3}(i)$
denotes the standard deviation of values in the sub-tensor of size $3^{d}$
centered at the position $i$, and $\sigma$ denotes the standard deviation of
the values of the entire tensor. Note that we used tensors with diverse
properties, including varying density and smoothness, from different domains,
without any assumption on data property. See Section III of [27] for data
semantics and pre-processing steps.

Competitors: We compared TensorCodec with 7 state-of-the-art methods (refer to
Section II) to evaluate their performance in terms of tensor compression. We
employed four well-known tensor decomposition methods: CPD [18], TKD [11], TTD
[12], and TRD [13] (Section II). These methods are implemented in MATLAB
R2020a, which offers a highly efficient linear algebra library.333Tensor
Toolbox. https://tensortoolbox.org/. 444TT-Toolbox.
https://github.com/oseledets/TT-Toolbox.
555https://github.com/oscarmickelin/tensor-ring-decomposition We used the
official C++ implementation of TTHRESH [14] and SZ3 [15], which are for
compressing tensors of visual data. Since the compression results of TTHRESH
and SZ3 depend on mode-index orders, we applied our order-initialization
technique to these methods only when it was helpful. We also used the official
PyTorch implementation of NeuKron [9], the state-of-the-art deep-learning-
based method for compressing sparse tensors. We implemented TensorCodec using
PyTorch.

Experimental Setup: To measure the accuracy of the compression methods, we
employed fitness, which is defined as:

$\vspace{-1mm}{fitness}=1-({\lVert\mathbf{\mathcal{X}}-\hat{\mathbf{\mathcal{X}}}\rVert_{F}}/{\lVert\mathbf{\mathcal{X}}\rVert_{F}})$

where $\hat{\mathbf{\mathcal{X}}}$ is an approximation of
$\mathbf{\mathcal{X}}$ obtained by the evaluated method. This metric has been
widely used to assess the approximation accuracy of tensor decomposition
methods [34, 35]. The fitness value is smaller than 1, with higher fitness
indicating more accurate approximation. For comparing compressed sizes, we
used the double-precision floating-point format for all methods. We encoded
the order of $N_{k}$ indices in each $k$-th mode using $N_{k}\log_{2}N_{k}$
bits, by representing each integer from 0 to $N_{k}-1$ in $\log_{2}N_{k}$
bits. Orders of all mode indices were stored separately in TensorCodec and
NeuKron (and also in SZ3 and TTHRESH when our reordering scheme was applied to
them). We conducted each experiment 5 times to obtain the average and standard
deviation of running time and fitness. Refer to Section IV of [27] for more
details.

###  V-B Q1. Compression Performance

We evaluated the compression performance of TensorCodec and its competitors,
focusing on the trade-off between compressed size and fitness. The
hyperparameters of the compared methods were configured to yield similar
compressed sizes, as detailed in Section IV of [27]. A time limit of 24 hours
was set for running each method.

TensorCodec outperforms all competitors by offering a superior trade-off
between compressed size and fitness, as shown in Figure 3. Particularly, on
the Stock dataset, TensorCodec achieves a compressed size 7.38$\times$ smaller
than that of the second-best method, while offering similar fitness. Moreover,
when the compressed size is almost the same, the fitness of TensorCodec is
3.33$\times$ greater than that of the competitor with the best fitness. While
NeuKron is specifically designed for sparse tensors and performs relatively
better in such datasets, including the Uber dataset, TensorCodec still
outperforms it on all datasets.

(a) Action (b) Air Quality (c) PEMS-SF (d) Uber

Figure 4: Every component of TensorCodec is effective for improved
compression. Fitness significantly increases as more components are added.

###  V-C Q2. Ablation Study

To demonstrate the effectiveness of each component of TensorCodec, we
considered the following variants of it:

  1. 1.

TensorCodec-R: a variant of TensorCodec that does not include the repeated
reordering of mode indices.

  2. 2.

TensorCodec-T: a variant of TensorCodec-R that does not initialize the order
of mode indices based on the $2$-approximate solution of Metric TSP.

  3. 3.

TensorCodec-N: a variant of TensorCodec-T without an auto-regressive neural
network for generating TT cores. Instead, it simply applies TTD to the folded
tensor.

We compared the reconstruction accuracy in terms of fitness for the four small
datasets, to evaluate the performance of the TensorCodec variants.
TensorCodec-N is optimized by TT-SVD, while the other variants are optimized
by gradient descents. We set the TT ranks of TensorCodec-N so that its number
of parameters is closest to that of the other variants, which have exactly the
same number of parameters.

Each component of TensorCodec contributes to improved compression. As shown in
Figure 4, the fitness of TensorCodec increases as more components are added.
An exception occurs in the Uber dataset, where the fitness shows a slight
increase from TensorCodec-T to TensorCodec-N. This is likely to be influenced
by the difference in the number of parameters (i.e., TensorCodec-N uses 10,776
bytes while TensorCodec-T uses 10,104 bytes for parameters).

Figure 5:  The compression time of TensorCodec scales near linearly with the
number of entries in the input $4$-order tensor. See Section VI of [27] for
the near-linear scalability on $3$-order tensors.

###  V-D Q3. Scalability

We investigate the scalability of TensorCodec with respect to the tensor size
while fixing $R$ and $h$ values to 8.

Compression speed: We examined the increase in compression time for
TensorCodec as the number of entries in the input tensors grows. Specifically,
we measured the time taken for order initialization and a single iteration of
the model and order optimization on five synthetic full tensors with varying
sizes. Their sizes can be found in Table V of [27]. Each entry of them is
sampled uniformly between 0 and 1.

The compression time of TensorCodec, specifically, all its three steps.
increases near linearly with the number of entries in the input tensor, as
illustrated in Figure 5. This is because the number of tensor entries is much
larger and also increases much faster than all other terms in the time
complexity in Theorem 4 in Section IV-E.

Reconstruction speed: We also examined the scalability of reconstruction from
the compressed output of TensorCodec. We generated synthetic tensors of orders
3 and 4, with mode sizes increasing from $2^{6}$ to $2^{18}$ by a factor of 2.
Then, we measured the total elapsed time for reconstructing $2^{18}$ entries
sampled uniformly at random from each tensor.

The reconstruction time of TensorCodec is sublinear as shown in Figure 6.
Specifically, the time increases logarithmically with the size of the largest
mode in the input tensor. This result is in line with Theorem 3 presented in
Section IV-E.

(a) 3-order tensor (b) 4-order tensor

Figure 6:  The reconstruction time of TensorCodec is sub-linear. When
reconstructing the input tensor entries from the outputs of TensorCodec, the
required time is logarithmic with respect to the largest mode size.

###  V-E Q4. Further Investigation

Order of mode indices: We compare the mode index orders obtained by
TensorCodec and NeuKron in the NYC dataset.666We set $R$ to 10 and $h$ to 9
for TensorCodec. For NeuKron, we set $h$ to $14$ so that it uses slightly more
space than TensorCodec. However, NeuKron’s compression did not terminate
within 24 hours, so we used the result obtained at the time limit. The indices
of the first two modes of the dataset indicate regions of New York City (see
Section III of [27]).

As visualized in Figure 7. the reordering process of TensorCodec assigns
nearby locations to similar mode indices. This is particularly evident in
Manhattan and Staten Island, where the colors of nearby locations are similar
to each other. However, the mode indices obtained by NeuKron do not exhibit
any clear patterns. This result demonstrates the effectiveness of the
reordering technique used in TensorCodec.

(a) Reordering by TensorCodec

(b) Reordering by NeuKron

Figure 7:  In the NYC dataset, where mode indices correspond to locations
within New York City, TensorCodec assigns nearby locations to similar mode
indices, as shown in (a), resulting in comparable colors for nearby areas,
particularly in Manhattan and Staten Island. However, the order obtained by
NeuKron in (b) does not exhibit any clear patterns.

Expressiveness: We evaluated the expressiveness of TensorCodec by analyzing
the number of parameters required for typical tensor decomposition methods to
accurately approximate tensors generated by TensorCodec. To conduct the
experiment, we created two tensors, one with size $256\times 256\times 256$
and another with size $128\times 128\times 128\times 128$, by unfolding
higher-order tensors generated by TensorCodec.777The TT rank $R$ and hidden
dimension $h$ of NTTD were both set to $5$, and the parameters of NTTD were
randomly initialized.

The results, depicted in Figure 8, demonstrate that TensorCodec is capable of
expressing high-rank tensors that require a large number of parameters for
typical tensor decomposition methods to approximate accurately.

(a) 3-order tensor (b) 4-order tensor

Figure 8:  Expressiveness of TensorCodec. It is capable of generating high-
rank tensors, which require a large number of parameters to be precisely
approximated by traditional tensor decomposition methods.

###  V-F Q5. Compression Speed

We compare the total compression time of all considered methods. We use the
experimental setups in Section V-B. For each dataset, we chose the setting of
$R$ and $h$ with the smallest number of parameters. For the competitors, we
used the settings with the fitness most similar to our method. As shown in
Figure 9, while TensorCodec takes less time than NeuKron, which sometimes
takes more than 24 hours, it is still slower than the non-deep-learning-based
methods.

In Sections VII of [27], we provide additional experimental results, including
hyperparameter sensitivity analysis.

##  VI Conclusions

Figure 9: The total compression time of TensorCodec and the competitors.
NeuKron runs out of time on some datasets, taking more than 24 hours.

In this work, we study the problem of lossy compression of tensors and devise
TensorCodec that compactly compresses tensors without strong data assumptions.
Our main ideas are (a) Neural Tensor-Train Decomposition, (b) high-order
tensor folding, and (c) mode-index reordering. Using $8$ real-world tensors,
we show the following advantages of TensorCodec:

  * •

Concise: It offers up to $7.38\times$ more compact compression than the best
competitor with similar reconstruction error.

  * •

Accurate: When compression ratios are comparable, TensorCodec achieves up to
$3.33\times$ lower reconstruction error than the competitor with the smallest
error.

  * •

Scalable: Empricially, its compression time is linear in the number of
entries. It reconstructs each entry in logarithmic time with respect to the
largest mode size.

We plan to improve the speed of TensorCodec and theoretically analyze its
approximation accuracy in future work.

## Acknowledgements

This work was funded by the Korea Meteorological Administration Research and
Development Program “Developing Intelligent Assistant Technology and Its
Application for Weather Forecasting Process” (KMA2021-00123). This work was
supported by Institute of Information & Communications Technology Planning &
Evaluation (IITP) grant funded by the Korea government (MSIT) (No.
2022-0-00157, Robust, Fair, Extensible Data-Centric Continual Learning) (No.
2019-0-00075, Artificial Intelligence Graduate School Program (KAIST))
(No.2021-0-02068, Artificial Intelligence Innovation Hub) This work was
supported by the National Research Foundation of Korea (NRF) grant funded by
the Korea government (MSIT) (No. NRF-2020R1C1C1008296) (No.
NRF-2021R1C1C1008526).

## References

  * [1] T. G. Kolda and B. W. Bader, “Tensor decompositions and applications,” _SIAM review_ , vol. 51, no. 3, pp. 455–500, 2009.
  * [2] J.-G. Jang and U. Kang, “D-tucker: Fast and memory-efficient tucker decomposition for dense tensors,” in _ICDE_ , 2020.
  * [3] ——, “Fast and memory-efficient tucker decomposition for answering diverse time range queries,” in _KDD_ , 2021.
  * [4] J. Wang, Z. Liu, Y. Wu, and J. Yuan, “Mining actionlet ensemble for action recognition with depth cameras,” in _CVPR_ , 2012.
  * [5] M. Defferrard, K. Benzi, P. Vandergheynst, and X. Bresson, “Fma: A dataset for music analysis,” _arXiv preprint arXiv:1612.01840_ , 2016.
  * [6] P. Xu, “Truncated svd methods for discrete linear ill-posed problems,” _Geophysical Journal International_ , vol. 135, no. 2, pp. 505–514, 1998\.
  * [7] J. Sun, Y. Xie, H. Zhang, and C. Faloutsos, “Less is more: Compact matrix decomposition for large sparse graphs,” in _SDM_ , 2007.
  * [8] S. Smith, N. Ravindran, N. D. Sidiropoulos, and G. Karypis, “Splatt: Efficient and parallel sparse tensor-matrix multiplication,” in _IPDPS_ , 2015.
  * [9] T. Kwon, J. Ko, J. Jung, and K. Shin, “Neukron: Constant-size lossy compression of sparse reorderable matrices and tensors,” in _WWW_ , 2023\.
  * [10] F. L. Hitchcock, “The expression of a tensor or a polyadic as a sum of products,” _J. Math. Phys_ , vol. 6, no. 1-4, pp. 164–189, 1927.
  * [11] L. R. Tucker, “Some mathematical notes on three-mode factor analysis,” _Psychometrika_ , vol. 31, no. 3, pp. 279–311, 1966.
  * [12] I. V. Oseledets, “Tensor-train decomposition,” _SISC_ , vol. 33, no. 5, pp. 2295–2317, 2011.
  * [13] Q. Zhao, M. Sugiyama, L. Yuan, and A. Cichocki, “Learning efficient tensor representations with ring-structured networks,” in _ICASSP_ , 2019.
  * [14] R. Ballester-Ripoll, P. Lindstrom, and R. Pajarola, “Tthresh: Tensor compression for multidimensional visual data,” _TVCG_ , vol. 26, no. 9, pp. 2891–2903, 2019.
  * [15] K. Zhao, S. Di, M. Dmitriev, T.-L. D. Tonellot, Z. Chen, and F. Cappello, “Optimizing error-bounded lossy compression for scientific data by dynamic spline interpolation,” in _ICDE_ , 2021.
  * [16] S. Ma, X. Zhang, C. Jia, Z. Zhao, S. Wang, and S. Wang, “Image and video compression with neural networks: A review,” _TCSVT_ , vol. 30, no. 6, pp. 1683–1698, 2019.
  * [17] V. Bhaskaran and K. Konstantinides, “Image and video compression standards: algorithms and architectures,” 1997.
  * [18] J. D. Carroll and J.-J. Chang, “Analysis of individual differences in multidimensional scaling via an n-way generalization of “eckart-young” decomposition,” _Psychometrika_ , vol. 35, no. 3, pp. 283–319, 1970.
  * [19] B. W. Bader and T. G. Kolda, “Efficient matlab computations with sparse and factored tensors,” _SISC_ , vol. 30, no. 1, pp. 205–231, 2008.
  * [20] T. G. Kolda and J. Sun, “Scalable tensor decompositions for multi-aspect data mining,” in _ICDM_ , 2008.
  * [21] J. Zhang, J. Oh, K. Shin, E. E. Papalexakis, C. Faloutsos, and H. Yu, “Fast and memory-efficient algorithms for high-order tucker decomposition,” _KAIS_ , vol. 62, no. 7, pp. 2765–2794, 2020.
  * [22] J. Leskovec and C. Faloutsos, “Scalable modeling of real graphs using kronecker multiplication,” in _ICML_ , 2007.
  * [23] A. Novikov, D. Podoprikhin, A. Osokin, and D. P. Vetrov, “Tensorizing neural networks,” in _NeurIPS_ , 2015.
  * [24] Y. Yang, D. Krompass, and V. Tresp, “Tensor-train recurrent neural networks for video classification,” in _ICML_ , 2017.
  * [25] C. Yin, B. Acun, C.-J. Wu, and X. Liu, “Tt-rec: Tensor train compression for deep learning recommendation models,” _MLSys_ , 2021.
  * [26] C. Yin, D. Zheng, I. Nisa, C. Faloutsos, G. Karypis, and R. Vuduc, “Nimble gnn embedding with tensor-train decomposition,” in _KDD_ , 2022.
  * [27] T. Kwon, J. Ko, J. Jung, and K. Shin. (2023) Tensorcodec: Compact lossy compression of tensors without strong assumptions on data properties (supplementary materials). [Online]. Available: https://github.com/kbrother/TensorCodec
  * [28] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural computation_ , vol. 9, no. 8, pp. 1735–1780, 1997.
  * [29] K. Cho, B. Merrienboer, C. Gulcehre, F. Bougares, H. Schwenk, and Y. Bengio, “Learning phrase representations using rnn encoder-decoder for statistical machine translation,” in _EMNLP_ , 2014.
  * [30] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _NeurIPS_ , 2017.
  * [31] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _ICLR_ , 2015.
  * [32] M.-Y. Kao, _Encyclopedia of algorithms_. Springer Science & Business Media, 2008.
  * [33] J. Leskovec, A. Rajaraman, and J. D. Ullman, _Mining of massive data sets_. Cambridge university press, 2020\.
  * [34] C. Battaglino, G. Ballard, and T. G. Kolda, “A practical randomized cp tensor decomposition,” _SIMAX_ , vol. 39, no. 2, pp. 876–901, 2018.
  * [35] I. Perros, E. E. Papalexakis, H. Park, R. Vuduc, X. Yan, C. Defilippi, W. F. Stewart, and J. Sun, “Sustain: Scalable unsupervised scoring for tensors and its application to phenotyping,” in _KDD_ , 2018.