#  Multidimensional Data Analysis Based on Block Convolutional Tensor
Decomposition

Mahdi Molavi
Department of Computer Science, Tarbiat Modares, Tehran-Iran Mansoor Rezghi
<EMAIL_ADDRESS>
Department of Computer Science, Tarbiat Modares, Tehran-Iran Tayyebeh Saeedi
Department of Computer Science, Tarbiat Modares, Tehran-Iran

###### Abstract

Tensor decompositions are powerful tools for analyzing multi-dimensional data
in their original format. Besides tensor decompositions like Tucker and CP,
Tensor SVD (t-SVD) which is based on the t-product of tensors is another
extension of SVD to tensors that recently developed and has found numerous
applications in analyzing high dimensional data. This paper offers a new
insight into the t-Product and shows that this product is a block convolution
of two tensors with periodic boundary conditions. Based on this viewpoint, we
propose a new tensor-tensor product called the $\star_{c}{}\text{-Product}$
based on Block convolution with reflective boundary conditions. Using a tensor
framework, this product can be easily extended to tensors of arbitrary order.
Additionally, we introduce a tensor decomposition based on our
$\star_{c}{}\text{-Product}$ for arbitrary order tensors. Compared to t-SVD,
our new decomposition has lower complexity, and experiments show that it
yields higher-quality results in applications such as classification and
compression.

Keywords: Tensor-tensor product, Tensor singular value decomposition,
Convolution, Boundary condition, Reflective boundary condition.

##  1 Introduction

In recent years, the popularity of devices such as smartphones, digital
cameras, and traffic cameras has led to an abundance of image and video data.
To effectively use machine learning algorithms on this type of data, we need
non-vector tools for representation. While matrices are well-suited for
displaying gray-scale images, tensors offer an extension to matrices that can
handle multidimensional data such as color images and videos. Although
traditional machine learning algorithms can be applied to vectorized data,
this approach has significant drawbacks. First, vectorization can destroy
structural relationships between various features, such as the spatial
relationships between pixels in image data. Second, folding data into vectors
can lead to high-dimensional data, resulting in overfitting and the curse of
dimensionality. To address these issues, tensor-based, multi-linear methods
have been developed that can work directly with multidimensional data. This
approach has gained significant attention in recent years, and several tensor-
based algorithms have been developed for well-known machine learning
algorithms such as SVM, PCA, and LDA, including STM Cai et al. (2006), MPCA Lu
et al. (2008), and MLDA Liu et al. (2010), respectively. Moreover, tensor
methods have also been used in neural network layers and deep learning to
reduce network parameters while maintaining network quality.

Matrix decomposition methods, such as Singular Value Decomposition (SVD), are
commonly used in machine learning applications such as classification Selvan
and Ramakrishnan (2007), clustering Liang (2007), and dimension reduction
methods Wang and Zhu (2017), and have proven to be effective Zaki et al.
(2014). Due to the advantages of SVD, there have been efforts to extend it to
tensors. Over the past decade, various extensions of SVD for tensors have been
proposed, such as CP and Tucker Kolda and Bader (2009). These methods are
widely used in various applications, including EEG classification Bi and Wang
(2019), image processing Zhang et al. (2019), rs-fMRI classification Noroozi
and Rezghi (2020), tensor robust principal component analysis, and tensor
completion Fan et al. (2020); Xie et al. (2017). Recently, Kilmer and Martin
proposed a new decomposition method called t-SVD that decomposes an order-3
tensor into three tensors using a new product between tensors called the
tensor-tensor product (t-Product) Kilmer and Martin (2011).

The t-SVD decomposition has numerous applications in various fields such as
tensor completion Zhang and Aeron (2016), video recovery Lou and Cheung
(2019), dynamic MRI reconstruction Ai et al. (2018), color image denoising
Wang et al. (2020), and tensor robust principal analysis Lu et al. (2019).
However, while the t-SVD decomposition becomes SVD on an order-2 tensor
(matrix), the tensors obtained from the decomposition are not guaranteed to be
real in their work and some related works Hao et al. (2013); Martin et al.
(2013). This issue has recently been resolved by Canyi Lu et al. in Lu et al.
(2019).

Moreover, in Martin et al. (2013), the t-Product and hence the t-SVD have been
generalized for n-dimensional data. However, their definition of the t-Product
involves the terms fold and unfold, which transform tensors into structured
circulant block matrices. Additionally, the extension of the t-Product defined
in Martin et al. (2013) for high dimensions (n-order tensors) has a recursive
form, leading to increased complexity in the definition. This complexity
becomes even more challenging for higher dimensions, making the definitions of
t-Product and t-SVD more difficult to comprehend. For instance, in the
algorithm (2) presented in Martin et al. (2013), numerous folding and
unfolding operations are used in different modes, making the implementation
complex and time-consuming.

In this paper, we sight at the t-Product from another viewpoint and show that
the t-Product is actually a block convolution with a periodic boundary between
two tensors. Then, this viewpoint gives us an opportunity to use image
processing literature in artificial boundary conditions to define a new tensor
product with better properties. Different kinds of artificial boundaries are
used in image restoration for modeling of blurring process Rezghi et al.
(2014). Zero, periodic, reflective, and anti-reflective are known boundary
conditions. It has been shown that the blurring matrix with periodic and
reflective boundary (by symmetric mask) is diagonalizable by Fourier and
Cosine transformation respectively Ng et al. (1999); Rezghi and Elden (2011).
Also, the computational complexity and quality of the modeling by the
reflective boundary case are better than the periodic boundary case. So here,
we use reflective boundary conditions and introduce a new tensor product
called $\star_{c}{}\text{-Product}$ that works on order-n tensors. Finally, we
present a novel tensor decomposition based on this product named
$\star_{c}{}\text{-SVD}$. Based on this decomposition, we apply classification
and clustering techniques and we show our work has better performance compared
to other state-of-the-art methods.

In recent years, structured tensors have been proposed to model convolution
between high-dimensional tensors. For example, in Rezghi and Elden (2011),
circulant tensors with arbitrary order were introduced and it was demonstrated
that these tensors can be used to restore 3D images with periodic boundaries
in a specific case. Additionally, in Rezghi and Amirmazlaghani (2019),
Toeplitz tensors with arbitrary dimensions were used for convolution modeling.
In this paper, we show that t-Product and $\star_{c}{}\text{-Product}$ can be
presented as structured Circulant and Toeplitz+Hankel tensors. This leads to
the generalization of the t-Product and $\star_{c}{}\text{-Product}$ for any
dimension using structured circulant and Toeplitz plus Hankel tensors,
respectively. The advantages of our proposed method are its simplicity in
generalizing the t-Product and $\star_{c}{}\text{-Product}$ to arbitrary
dimensions using structured circulant Toeplitz plus Hankel tensors. This
method also inherits the useful properties of these products, such as their
equivalent SVD. Moreover, it is easier to implement and has a lower
computational cost compared to previous methods.

The rest of this paper is organized as takes after: Section 2 contains
notations that we use in the paper and related works. Section 3 includes of
the our viewpoint to t-Product. In section 4, we present our new product and
corresponding decomposition. Section 5 represents some experimental results in
compression, clustering, and classification.

##  2 Notations and related works

###  2.1 Notations

In this paper, we denote tensors by boldface calligraphic letters, e.g.,
$\mathcal{A}$. We use boldface uppercase letters for matrices, e.g., $A$. We
use the Python notation $\mathcal{A}[:,:,i]$ to denote the $i$-th frontal
slice and it is denoted compactly as $A_{i}$, also we denote the $i$-th column
and $i$-th row of a matrix as $A[:,i]$ and $A[i,:]$, respectively. Vectors are
denoted by boldface lowercase letters, e.g., $a$, and scalars are denoted by
lowercase letters, e.g., $a$.

We define the mode-n product of a tensor and a matrix as follows, as defined
in Rezghi (2017); Rezghi and Elden (2011):

$\displaystyle\boldsymbol{\mathcal{G}}:=(M){n}.\boldsymbol{\mathcal{Z}},$

where $M\in\mathbb{R}^{J\times I_{n}}$, is a matrix,
$\boldsymbol{\mathcal{Z}}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times
I_{n}\times\cdots\times I_{N}}$ is an $N$-order tensor, and
$\boldsymbol{\mathcal{G}}\in\mathbb{R}^{I_{1}\times\cdots\times I_{n-1}\times
J\times I_{n+1}\times\cdots\times I_{N}}$.

Really, in mode-n product each mode-n fiber of tensor is multiplied by matrix,
Bahri et al. (2018). This inner product and other matrix-vector, matrix-
matrix, and also matrix-tensor products can be considered as a special case of
contraction product of two tensors, which is a tensor product followed by a
contraction along specified modes. For two tensors
$\mathcal{A}\in\mathbb{R}^{I_{1}\times\cdots\times I_{D}\times
J_{1}\times\cdots\times J_{M}}$ and
$\mathcal{B}\in\mathbb{R}^{K_{1}\times\cdots\times K_{L}\times
J_{1}\times\cdots\times J_{M}}$, their contractive product corresponding to
contraction modes $D+1,\cdots,D+M$ and $L+1,\cdots,L+M$ of tensors
$\mathcal{A}$ and $\mathcal{B}$, respectively, can be defined as follows Bader
and Kolda (2006)

$\displaystyle\mathcal{C}=\langle\mathcal{A},\mathcal{B}\rangle_{D+1,\cdots,D+M;L+1,\cdots,L+M}=\langle\mathcal{A},\mathcal{B}\rangle_{D+1:D+M;L+1:L+M}$
(1)

where

$\displaystyle\boldsymbol{c}_{i_{1},\cdots,i_{D},k_{1},\cdots,k_{L}}=\sum_{1\leq
j_{k}\leq
J_{k}}\boldsymbol{a}_{i_{1},\cdots,i_{D},j_{1},\cdots,j_{M}}\boldsymbol{b}_{k_{1},\cdots,k_{L},j_{1},\cdots,j_{M}}.$

The extension of diagonal concept to tensors is not unique, but the general
from of such concept is proposed in Rezghi and Elden (2011), which can cover
the other definitions. For arbitrary order $\mathcal{A}$, let
$S=\\{s_{1},\cdots,s_{t}\\}$ be a subset of modes $\\{1,\cdots,N\\}$,
$\mathcal{A}={\sf diag}(\mathcal{D})\in\mathbb{R}^{I_{1}\times\cdots\times
I_{N}}$ is $\\{S\\}$-diagonal, if $A_{i_{1}\cdots i_{N}}$ can be nonzero only
if $i_{s_{1}}=\cdots=i_{s_{t}}$ and are elements of $(N-|S|+1)$-order tensor
$\mathcal{D}$. For Example we say that $3$-order tensor
$\mathcal{A}\in\mathbb{R}^{I_{1}\times I_{2}\times I_{3}}$ is
$\\{\\{1,3\\}\\}$-diagonal with elements $D$ and denote by $\mathcal{A}={\sf
diag}_{\\{1,3\\}}(D)$, if

$\displaystyle\mathcal{A}[i_{1},i_{2},i_{3}]=\delta_{i_{1}i_{3}}D[i_{2},i_{3}],\quad\delta_{ij}=\begin{cases}1&i=j\\\
0&\text{otherwise}\end{cases}$ (2)

Also for two disjoint subsets $S=\\{s_{1},\cdots,s_{t}\\}$ and
$Q=\\{q_{1},\cdots,q_{t^{\prime}}\\}$ of modes $\\{1,\cdots,N\\}$.
$\mathcal{A}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$ is called
$\\{S,Q\\}$-diagonal if $A_{i_{1}\cdots i_{N}}$ can be nonzero only if
$i_{s_{1}}=\cdots=i_{s_{t}}$ and $i_{q_{1}}=\cdots=i_{q_{t^{\prime}}}$.

In the following we will face with structured circulant tensors which defined
in Rezghi and Elden (2011) as follows: $\mathcal{A}\in\mathbb{R}^{I_{1}\times
I_{2}\times\cdots\times I_{N}}$ is called $\\{l,k\\}$-circulant tensor, if
$I_{l}=I_{k}=n$, and

$\mathcal{A}[:,\cdots,:,i_{l},:,\cdots,:,i_{k},:,\cdots,:]=\mathcal{A}[:,\cdots,:,i^{\prime}_{l},:,\cdots,:,i^{\prime}_{k},:,\cdots,:],\quad\text{if}\quad
i_{l}-i_{k}\equiv i^{\prime}_{l}-i^{\prime}_{k}\quad(\text{mod}\quad n).$

The authors in Rezghi and Elden (2011) showed that such structured tensor can
be diagonalized partially by FFT, which causes fast computation of some
contraction products with such tensors.

###  2.2 t-Product and t-SVD

For the first time, tensor-tensor product (t-Product) for $3$-order tensors
$\mathcal{A}\in\mathbb{R}^{n_{1}\times\ell\times n_{3}}$ and
$\mathcal{B}\in\mathbb{R}^{\ell\times n_{2}\times n_{3}}$ is introduced in
Kilmer and Martin (2011) as follows:

$\displaystyle\mathbb{R}^{n_{1}\times n_{2}\times
n_{3}}\ni\mathcal{C}=\mathcal{A}\star_{t}\mathcal{B}=\mathsf{fold}\left(\mathsf{circ}(\mathsf{unfold}(\mathcal{A})).\mathsf{unfold}(\mathcal{B})\right),$

which

$\displaystyle\mathsf{circ}(\mathsf{unfold}(\mathcal{A}))=\begin{bmatrix}{{\boldsymbol{A}_{1}}}&{{\boldsymbol{A}_{{n_{3}}}}}&\cdots&{{\boldsymbol{A}_{2}}}\\\
{{\boldsymbol{A}_{2}}}&{{\boldsymbol{A}_{1}}}&\cdots&{{\boldsymbol{A}_{3}}}\\\
\vdots&\vdots&\ddots&\vdots\\\
{{\boldsymbol{A}_{{n_{3}}}}}&{{\boldsymbol{A}_{{n_{3}}-1}}}&\cdots&{{\boldsymbol{A}_{1}}}\end{bmatrix}\in\mathbb{R}^{n_{1}n_{3}\times\ell
n_{3}},$

is a block circulant matrix. Also, $\mathsf{fold}$ and $\mathsf{unfold}$ are
the following operations:

$\displaystyle\mathsf{unfold}(\mathcal{A})=\begin{bmatrix}{{\boldsymbol{A}_{1}}}\\\
{{\boldsymbol{A}_{2}}}\\\ \vdots\\\
{{\boldsymbol{A}_{{n_{3}}}}}\end{bmatrix}\in\mathbb{R}^{n_{1}n_{3}\times\ell},~{}~{}\mathsf{fold}(\mathsf{unfold}(\mathcal{A}))=\mathcal{A}.$

Based on the properties of block circulant matrices, t-Product can be
efficiently computed using the Fast Fourier Transform (FFT) algorithm, as
follows:

$\displaystyle\mathsf{unfold}(\mathcal{C})=(\boldsymbol{F}_{n_{3}}^{*}\otimes
I_{n_{1}})\left((\boldsymbol{F}_{n_{3}}\otimes
I_{n_{1}})\mathsf{circ}\left(\mathsf{unfold}(\mathcal{A})\right)(\boldsymbol{F}_{n_{3}}^{*}\otimes
I_{\ell})\right)(\boldsymbol{F}_{n_{3}}\otimes
I_{\ell})\mathsf{unfold}(\mathcal{B}).$

Based on the t-Product operator Kilmer and Martin (2011), proved that on
arbitrary 3-order tensors $\mathcal{A}\in\mathbb{R}^{n_{1}\times n_{2}\times
n_{3}}$, can be decompoed as follows

$\displaystyle\mathcal{A}=\mathcal{U}\star_{t}\mathcal{S}\star_{t}\mathcal{V}^{\mathsf{T}},$
(3)

where $\mathcal{U}\in\mathbb{R}^{n_{1}\times n_{1}\times n_{3}}$ and
$\mathcal{V}\in\mathbb{R}^{n_{2}\times n_{2}\times n_{3}}$ are orthogonal, and
$\mathcal{S}\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$ is a f-diagonal
tensor (according to our definition $\\{1,2\\}$-diagonal) Kilmer and Martin
(2011). Also, the transpose $\mathcal{V}^{\sf T}$ in (3) is defined in Kilmer
and Martin (2011). This decomposition is an extension of SVD for $3$-order
tensors named t-SVD. The scheme of this decomposition is shown in Fig. 1.

Figure 1:  t-SVD scheme of an $n_{1}\times n_{2}\times n_{3}$ tensor Hao et
al. (2013),Lu et al. (2019).

Furthermore, when $n_{3}=1$, the t-SVD reduces to the SVD of a matrix. The
t-SVD, similar to SVD, has various applications including dimension reduction,
classification, tensor completion, and even in deep neural networks Wu et al.
(2022). In Martin et al. (2013), the authors extended the t-Product and t-SVD
to arbitrary order tensors in 2013.

##  3 t-Product with signal processing viewpoint

This section presents a new perspective on the t-Product and demonstrates that
it can be interpreted as a block convolution between two tensors. This
perspective enables us to define a new tensor-tensor product with better
properties than the t-Product. Another advantage of this approach is that it
provides a simple framework for computing the t-SVD for higher dimensions,
which is easier to implement.

Convolution is a fundamental concept in signal and image processing with many
applications such as edge detection Shen and Sethi (1996); Wen et al. (2018),
image enhancement and deblurring Han and Kan (2019); Mohan et al. (2020).
Convolution is also the basis of outstanding convolutional neural network
architectures in deep learning Goodfellow et al. (2016).

Mathematically, the convolution between two vectors
$\boldsymbol{x,h}\in\mathbb{R}^{n}$ is defined as following:

$\displaystyle y_{i}=\sum h_{i-j}x_{j},~{}i=1,\cdots,n.$ (4)

Here, $\boldsymbol{x}$, $\boldsymbol{y}$, are considered as exact and filtered
signals respectively and $\boldsymbol{h}$ denotes the filter kernel. In the
convolution process, computing some elements of $\boldsymbol{y}$ requires
signals from the boundary of $\boldsymbol{x}$. Various approaches have been
proposed to deal with the boundary of $\boldsymbol{x}$, such as using zero
(black) boundary Rezghi et al. (2014), repetition (periodic) boundary Rezghi
and Elden (2011), reflective boundary Ng et al. (1999), etc., which are known
as artificial boundary conditions (BC). Here, we show that a block convolution
with a periodic boundary condition provides insight into the t-Product from a
signal processing viewpoint.

Let $\boldsymbol{x}=[x_{1},x_{2},\cdots,x_{n}]\in\mathbb{R}^{n}$ and
$\boldsymbol{h}=[h_{0},h_{1},\cdots,h_{n-1}]=[a_{1},a_{2},\cdots,a_{n}]=\boldsymbol{a}\in\mathbb{R}^{n}$,
became the input signal and nonzero part of the kernel $\\{h_{i}\\}$,
respectively. By considering the periodic boundary condition for signal
$\boldsymbol{x}$ in convolution process (4), the out side of
$\boldsymbol{x}=[x_{1},x_{2},\cdots,x_{n}]$ will be

$\displaystyle x_{i}=\begin{cases}x_{n+i},&i=1-n,\cdots,0\\\
x_{i-n},&i=n+1,\cdots,2n\end{cases},$ (5)

or schematically as shown in Fig. 2.

Figure 2: Scheme of the periodic boundary condition. The dashed part is the
periodic boundary of signal $\boldsymbol{x}$.

By this assumption, $y_{i}$ for $i=1,\cdots,n$ will be

$\displaystyle
y_{i}=\sum_{j=1}^{i}a_{i-j+1}x_{j}+\sum_{j=i+1}^{n}a_{n+1+i-j}x_{j},\qquad
i=1,\cdots,n.$ (6)

By defining the circulant matrix
$\mathsf{circ}(\boldsymbol{a})\in\mathbb{R}^{n\times n}$ as follows:

$\displaystyle\mathsf{circ}(\boldsymbol{a})[i,j]=a_{k},\quad\mathrm{where}\quad
k=\begin{cases}i-j+1,&i\geq j\\\ n+1+i-j,&i<j\end{cases},\qquad
i,j=1,\cdots,n,$ (7)

the equation (6) will be:

$\displaystyle\begin{bmatrix}y_{1}\\\ y_{2}\\\ \vdots\\\
y_{n}\end{bmatrix}=\begin{bmatrix}{{a_{1}}}&{{a_{{n}}}}&\cdots&{{a_{2}}}\\\
{{a_{2}}}&{{a_{1}}}&\cdots&{{a_{3}}}\\\ \vdots&\vdots&\ddots&\vdots\\\
{{a_{{n}}}}&{{a_{{n}-1}}}&\cdots&{{a_{1}}}\end{bmatrix}\begin{bmatrix}x_{1}\\\
x_{2}\\\ \vdots\\\
x_{n}\end{bmatrix}\quad\mathrm{or}\quad\boldsymbol{y}=\mathsf{circ}(\boldsymbol{a})\boldsymbol{x}.$
(8)

According to the properties of the circulant matrix Rezghi and Elden (2011),
we will have
$\boldsymbol{y}=\mathsf{ifft}(\mathsf{fft}(\boldsymbol{a})\odot\mathsf{fft}(\boldsymbol{x}))$,
which shows that $\boldsymbol{y}$ could be computed very fast by FFT without
the need to construct $\mathsf{circ}(\boldsymbol{a})$. Here $\odot$ denotes
Hadamard (point-wise) product.

Now, if the elements $a_{i},x_{i}$ and $y_{i}$ in convolution with periodic
BC, are substituted with matrices
$\mathcal{A}[:,i,:]=A_{i}\in\mathbb{R}^{n_{1}\times n_{3}}$,
$\mathcal{X}[:,i,:]=X_{i}\in\mathbb{R}^{n_{3}\times n_{4}}$, and
$\mathcal{Y}[:,i,:]=Y_{i}\in\mathbb{R}^{n_{1}\times
n_{4}},~{}i=1,\cdots,n_{2}$, the block version of equations (5) and (6) will
be

$\displaystyle X_{i}=\begin{cases}X_{n_{2}+i},&i=0,\cdots,1-n_{2}\\\
X_{i-n_{2}},&i=n_{2}+1,\cdots,2n_{2}\end{cases},$ (9)

and

$\displaystyle\mathcal{Y}[:,i,:]=\sum_{j=1}^{i}\mathcal{A}[:,i-j+1,:]X_{j}+\sum_{j=i+1}^{n_{2}}\mathcal{A}[:,n_{2}+1+i-j,:]X_{j},\qquad
i=1,\cdots,n_{2}.$ (10)

So, this equation is the bock convolution with periodic BC of tensor
$\mathcal{A}\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$ and
$\mathcal{X}\in\mathbb{R}^{n_{3}\times n_{2}\times n_{4}}$ in mode-2 which
gives $\mathcal{Y}\in\mathbb{R}^{n_{1}\times n_{2}\times n_{4}}$. Similar to
definition of $\mathsf{circ}(\boldsymbol{a})$ in (7), by defining a $4$-order
tensor $\text{Tcirc}(\mathcal{A})\in\mathbb{R}^{n_{1}\times n_{2}\times
n_{3}\times n_{2}}$, with elements,

$\displaystyle\text{Tcirc}(\mathcal{A})[:,i,:,j]=\mathcal{A}[:,k,:],\quad\mathrm{where}\quad
k=\begin{cases}i-j+1,&i\geq j\\\ n_{2}+1+i-j,&i<j\end{cases},\qquad
i,j=1,\cdots,n_{2},$ (11)

the equation (10) becomes:

$\displaystyle\mathcal{Y}[:,i,:]=\sum_{j=1}^{n_{2}}\text{Tcirc}(\mathcal{A})[:,i,:,j]\mathcal{X}[:,j,:],\qquad
i=1,\cdots,n_{2}.$ (12)

Which is equal to the following contraction:

$\displaystyle\mathcal{Y}=\left\langle\text{Tcirc}(\mathcal{A}),\mathcal{X}\right\rangle_{3:4;1:2}.$
(13)

between $\text{Tcirc}(\mathcal{A})$ and $\mathcal{X}$, Furthermore, by folding
this equation, we get the following equation

$\displaystyle\begin{bmatrix}Y_{1}\\\ Y_{2}\\\ \vdots\\\
Y_{n}\end{bmatrix}=\begin{bmatrix}{{A_{1}}}&{{A_{{n}}}}&\cdots&{{A_{2}}}\\\
{{A_{2}}}&{{A_{1}}}&\cdots&{{A_{3}}}\\\ \vdots&\vdots&\ddots&\vdots\\\
{{A_{{n}}}}&{{A_{{n}-1}}}&\cdots&{{A_{1}}}\end{bmatrix}\begin{bmatrix}X_{1}\\\
X_{2}\\\ \vdots\\\ X_{n}\end{bmatrix}.$ (14)

This shows that our tensor viewpoint is equal to the defined block form in
Kilmer and Martin (2011) of t-product only by reordering of modes 2 and 3.

The tensor $\text{Tcirc}(\mathcal{A})$ according to definition of circulant
tensors in Rezghi and Elden (2011), is an $\\{2,4\\}$\- circulant tensor,
which enables us to calculate the contraction (13), without constructing
$\text{Tcirc}(\mathcal{A})$ and very fast by FFT on mode-2 of tensors
$\mathcal{A},\mathcal{X}$ as follows:

###### Lemma 1

The equation
$\mathcal{Y}=\langle\text{Tcirc}(\mathcal{A}),\mathcal{X}\rangle_{3{:}4;1{:}2}$
could be computed very fast by fast Fourier transform as follows:

$\displaystyle\mathcal{Y}=\left(F^{*}\right)_{3}.{\mathcal{\bar{Y}}}$

where
${\mathcal{\bar{Y}}}[:,i,:]={\mathcal{\bar{A}}}[:,i,:]{\mathcal{\bar{X}}}[:,i,:]$,
${\mathcal{\bar{A}}}=\left(F\right)_{3}.\mathcal{A}$, and
${\mathcal{\bar{X}}}=\left(F\right)_{3}.\mathcal{X}$, and $F$, $F^{*}$ are
Fourier transform and its conjugate transpose, respectively.

Proof  This can be proved based on Theorem 5.1 and Corollary 5.4 in Rezghi and
Elden (2011).
This notation and representation of t-product by tensor form (13) give us a
viewpoint that comfort the extension of t-product to arbitrary order.

Now, if we substitute the block components $A_{i},X_{i}$ of Block convolution
(10) and its corresponding boundary (9) by the slices
$\mathcal{A}[:,i_{2},\cdots,i_{N-1},:]$ and
$\mathcal{X}[:,i_{2},\cdots,i_{N-1},:]$ of tensors
$\mathcal{A}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times I_{N-1}\times
J}$, $\mathcal{X}\in\mathbb{R}^{J\times I_{2}\times\cdots\times I_{N}}$, we
have $\\{2,\cdots,N-1\\}-$period padding of $\mathcal{X}$ as follows

$\displaystyle\mathcal{X}[:,i_{2},i_{3},\cdots,i_{N-1},:]=\mathcal{X}[:,s_{2},s_{3},\cdots,s_{N-1},:],\quad
s_{j}=\begin{cases}I_{j}+i_{j},&i_{j}=0,\cdots,1-I_{j}\\\
i_{j}-I_{j},&i_{j}=I_{j}+1,\cdots,2I_{j}\end{cases}.$ (15)

and convolution (10) will be

$\displaystyle\mathcal{Y}[:,\bar{i},:]=\sum_{j_{2},\cdots,j_{N-1}}^{I_{2},\cdots,I_{N-1}}\text{Tcirc}(\mathcal{A})[:,\bar{i},:,\bar{j},:]\mathcal{X}[:,\bar{j},:],$
(16)

where $\bar{i}=i_{2},\cdots,i_{N-1}$, $\bar{j}=j_{2},\cdots,j_{N-1}$. Here
$\text{Tcirc}(\mathcal{A})\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times
I_{N-1}\times J\times I_{2}\times\cdots\times I_{N-1}}$ defined as

$\displaystyle\text{Tcirc}(\mathcal{A})[:,\bar{i},:\bar{j}]=\mathcal{A}[:,\bar{k},:],\qquad\bar{k}=k_{2},\cdots,k_{N-1},\quad
k_{l}=\begin{cases}i_{l}-j_{l}+1,&i_{l}\geq j_{l}\\\
n_{l}+1+i_{l}-j_{l},&i_{l}<j_{l}\end{cases},i_{l},j_{l}=1,\cdots,n_{l},$ (17)

is a $\\{2{:}N-1;N+1{:}2N-2\\}$-circulant tensor based on definition of
circulant tensor in Rezghi and Elden (2011). So, we call (16) as a
$\\{2,\cdots,N-1\\}-$mode block convolution of tensors
$\mathcal{A}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times I_{N-1}\times
J}$, $\mathcal{X}\in\mathbb{R}^{J\times I_{2}\times\cdots\times I_{N}}$, with
periodic padding in modes $\\{2,\cdots,N-1\\}$, which gives
$\mathcal{Y}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times I_{N-1}\times
I_{N}}$. It’s clear that the block convolution (16) is equal to the following
contraction:

$\displaystyle\mathcal{A}\star_{t}\mathcal{X}:=\mathcal{Y}=\langle\text{Tcirc}(\mathcal{A}),\mathcal{X}\rangle_{N{:}2(N-1);1{:}N-1}$
(18)

Therefor, we define the t-product of two N-order tensors
$\mathcal{A}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times I_{N-1}\times
J}$, $\mathcal{X}\in\mathbb{R}^{J\times I_{2}\times\cdots\times I_{N}}$ as
equation (18). By some mathematical manipulation, we could show that this
arbitrary order t-product definition is equal to extension of t-product in
Martin et al. (2013). But our viewpoint gives an instrument that computing
this t-product becomes more straightforward in notation, complexity, and
computation than the definition in Martin et al. (2013).

Since $\text{Tcirc}(\mathcal{A})$ is a $\\{2{:}N-1;N+1{:}2N-2\\}$-circulant
tensor from Rezghi and Elden (2011), we could prove that equation (18) could
be done without construction of $\text{t-circ}(\mathcal{A})$ only by applying
of FFT on tensors $\mathcal{A}$ and $\mathcal{X}$ as shown in Algorithm 1.

Algorithm 1 t-Product for arbitrary order tensors

1:$\mathcal{A}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times I_{N-1}\times
J}$, $\mathcal{X}\in\mathbb{R}^{J\times I_{2}\times I_{3}\times\cdots\times
I_{N}}$

2:$\mathcal{Y}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$

3:${\bar{\mathcal{A}}}=\left(F,\cdots,F\right)_{2:N-1}.\mathcal{A}$,
${\bar{\mathcal{Y}}}=\left(F,\cdots,F\right)_{2:N-1}.\mathcal{Y}$

4:${\mathcal{\bar{Y}}}[:,\bar{i},:]={\mathcal{\bar{A}}}[:,\bar{i},:]{\mathcal{\bar{X}}}[:,\bar{i},:],\quad\bar{i}=i_{2},\cdots,i_{N-1},i_{k}=1,\cdots,I_{k}$

5:${\mathcal{Y}}=\left(F^{*},\cdots,F^{*}\right)_{2:N-1}.{\mathcal{\bar{Y}}}$

######  Theorem 2 (t-SVD for arbitrary order tensors)

For each tensor $\mathcal{A}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$
with arbitrary order $N$, There exists the following decomposition of:

$\mathcal{A}=\mathcal{U}\star_{t}\mathcal{S}\star_{t}\mathcal{V}^{T}$

Proof  The approach for proof is similar to theorem 7 that we will prove in
the following.

##  4 Novel tensor product and decomposition based on block convolution with
reflective boundary conditions

The previous section has shown that the t-Product is a type of block
convolution that utilizes periodic boundary conditions between two tensors.
The concept of convolution has a rich history in the field of signal and image
processing, and has been applied in various contexts such as image
enhancement, image restoration, and deep convolutional neural networks (CNNs).
For example, in image enhancement, a mask is convolved with an image for
denoising or edge detection purposes, while in image restoration, the blurring
process can be modeled as the convolution of the blurring mask and the input
image Rezghi et al. (2014).

Although convolution masks must operate on the image boundary, it’s not always
possible to access the actual boundaries in all of these applications. As a
result, various artificial boundary conditions (BCs) have been proposed and
utilized in multiple scenarios. Examples of well-known BCs in the literature
of image restoration include zero, periodic, reflective, and anti-reflective
BCs. Experimental results have shown that reflective BCs generally outperform
periodic and zero BCs due to their ability to model more complex scenarios
that are more compatible with real situations Ng et al. (1999).

This section introduces a new type of tensor-tensor product based on block
convolution between two tensors with reflective boundary conditions. The
linear operator that corresponds to convolution by reflective BC can be
diagonalized with a Cosine operator, which always produces real numbers unlike
the FFT. Moreover, the complexity of this transformation is less than that of
the FFT.

To extend this concept, we first describe convolution with reflective BCs and
then introduce block matrix and block tensor versions of this operation,
following a similar approach as in the previous section.

In convolution equation (4) Let
$\boldsymbol{x}=[x_{1},\dots,x_{n}]^{\mathsf{T}}$ and
$\boldsymbol{h}=[h_{1-n},\dots,h_{1},\dots,h_{n-1}]^{\mathsf{T}}=[a_{n},\dots,a_{1},\dots,a_{n}]^{\mathsf{T}}\in
R^{2n-1}$ be the input signal and the nonzero part of a symmetric kernel
$\boldsymbol{h}$. Also consider reflective BC in outside the real signal
$\boldsymbol{x}$ , i.e.

$\displaystyle x_{i}=\begin{cases}x_{1-i}&i=0,\cdots,1-n\\\
x_{2n-i+1}&i=n+1,\cdots,2n\end{cases}$

By these assumptions the convolution (4), becomes

$\displaystyle
y_{i}=\sum_{j=1}^{n}\left(a_{|i-j|+1}+(1-\delta_{i+j,n+1})\begin{cases}a_{i+j}&i+j\leq
n\\\ a_{2(n+1)-(i+j)}&i+j>n\end{cases}\right)x_{j},\quad i=1,\cdots,n.$ (19)

where

$\displaystyle\delta_{i,j}=\begin{cases}1&i=j\\\ 0&i\neq j\end{cases}$

By defining $\mathsf{Th}(\boldsymbol{a})\in\mathbb{R}^{n\times n}$ matrix as
following:

$\displaystyle\mathsf{Th}(\boldsymbol{a})[i,j]=a_{|i-j|+1}+(1-\delta_{i+j,n+1})\begin{cases}a_{i+j}&i+j\leq
n\\\ a_{2(n+1)-(i+j)}&i+j>n\end{cases},\quad i,j=1,\cdots,n$ (20)

the equation (19) becomes to the following linear equation:

$\displaystyle\boldsymbol{y}=\mathsf{Th}(\boldsymbol{a})\boldsymbol{x},$ (21)

$\mathsf{Th}(\boldsymbol{a})$ has the following form in detail:

$\displaystyle\mathsf{Th}(\boldsymbol{a})$
$\displaystyle=\begin{bmatrix}a_{1}&a_{2}&\cdots&a_{n-1}&a_{n}\\\
a_{2}&a_{1}&\cdots&a_{n-2}&a_{n-1}\\\ \vdots&\ddots&\ddots&\ddots&\vdots\\\
a_{n-1}&a_{n-2}&\cdots&a_{1}&a_{2}\\\ a_{n}&a_{n-1}&\cdots&a_{2}&a_{1}\\\
\end{bmatrix}+\begin{bmatrix}a_{2}&a_{3}&\cdots&a_{n}&0\\\
a_{3}&\adots&\adots&\adots&a_{n}\\\ \vdots&\adots&0&\adots&\vdots\\\
a_{n}&\adots&\adots&\adots&a_{3}\\\ 0&a_{n}&\cdots&a_{3}&a_{2}\\\
\end{bmatrix}$ (22)
$\displaystyle=\mathsf{Toep}(\boldsymbol{a})+\mathsf{Hank}(\boldsymbol{a})$
(23)

which shows that the $\mathsf{Th}(\boldsymbol{a})$ is a spacial kind of
Toeplitz-plus-Hankel matrix,Ng et al. (1999).

(a) $y_{1}$

(b) $y_{2}$

(c) $y_{3}$

Figure 3:  Convolution with with reflective boundary

For example, figure 3 demonstrates this BC schematically for $n=3$. In Ng et
al. (1999) it has been shown that for any $\boldsymbol{a}\in\mathbb{R}^{n}$,
Toeplitz-plus-Hankel matrix in the $\mathsf{Th}(\boldsymbol{a})$ form, can be
diagonalized by Cosine transform as:

$\displaystyle\mathsf{Th}(\boldsymbol{a})={\overline{C}}^{\mathsf{T}}\boldsymbol{\Lambda}\overline{C},\quad\boldsymbol{\Lambda}=\mathsf{diag}(\bar{\boldsymbol{a}}),\quad\bar{\boldsymbol{a}}=\mathsf{diag}(c_{1})~{}\overline{C}~{}\mathsf{Th}_{1}(\boldsymbol{a}),\qquad
c_{1}=1./{\overline{C}}[{:},1]$ (24)

where ${\overline{C}}\in\mathbb{R}^{n\times n}$ is discrete cosine matrix
defined as

$\displaystyle{\overline{C}}\left[i,j\right]=\sqrt{\dfrac{2-\delta_{i1}}{n}}\cos\left(\dfrac{(i-1)(2j-1)}{2n}\pi\right),~{}i,j=1,\cdots,n,\qquad\delta_{ij}=\begin{cases}1,\quad
i=j\\\ 0,\quad\mathrm{otherwise}\end{cases},$

and

$\displaystyle\mathsf{Th}_{1}(\boldsymbol{a})=\begin{bmatrix}{{a_{1}}+{a_{2}}}\\\
{{a_{2}}+{a_{3}}}\\\ \vdots\\\ {{a_{n-1}}+{a_{n}}}\\\
a_{n}\end{bmatrix}=\boldsymbol{\Gamma}\boldsymbol{a},\qquad\boldsymbol{\Gamma}=\begin{bmatrix}1&1&0&\cdots&0\\\
0&1&1&\ddots&\vdots\\\ 0&\ddots&\ddots&\ddots&0\\\ \vdots&\ddots&0&1&1\\\
0&\cdots&0&0&1\end{bmatrix},~{}\boldsymbol{a}=\begin{bmatrix}{{a_{1}}}\\\
{{a_{2}}}\\\ \vdots\\\ {{a_{n-1}}}\\\ a_{n}\end{bmatrix},$

is the first column of $\mathsf{Th}(\boldsymbol{a})$. Since
$\mathsf{diag}(c_{1})~{}\boldsymbol{\Lambda}~{}{\mathsf{diag}(c_{1})}^{-1}=\boldsymbol{\Lambda}$,
diagonalization form (24) could be rewritten as

$\displaystyle\mathsf{Th}(\boldsymbol{a})={{C}}^{\raisebox{1.0pt}{$-1$}}\boldsymbol{\Lambda}{C},\quad{C}=\mathsf{diag}(c_{1})~{}\overline{C},\quad\boldsymbol{\Lambda}=\mathsf{diag}(\bar{\boldsymbol{a}}),\quad\bar{\boldsymbol{a}}=C~{}\Gamma
a.$ (25)

where $C^{-1}=\overline{C}^{\sf T}\mathsf{diag}(1./c_{1})$. By this
decomposition its clear that (21) could be computed by fast cosine transform
as follows

$\displaystyle\boldsymbol{y}$
$\displaystyle=\mathsf{Th}(\boldsymbol{a})\boldsymbol{x}={C}^{\raisebox{1.0pt}{$-1$}}(\bar{\boldsymbol{a}}\odot\bar{\boldsymbol{x}}),\quad\bar{\boldsymbol{a}}={C}\Gamma\boldsymbol{a},\quad\bar{\boldsymbol{x}}={C}\boldsymbol{x}$
(26)

where $\odot$ denotes Hadamard(pointwise) product of vectors. The equation
(26) is our base for defining new tensor product of tensors. But its clear
that if we define
$\boldsymbol{y}=\boldsymbol{a}\star_{c}\boldsymbol{x}=\mathsf{Th}(\boldsymbol{a})\boldsymbol{x}$
obviously, this multiplication does not have the associative property, i.e.,

$\boldsymbol{b}\star_{c}(\boldsymbol{a}\star_{c}\boldsymbol{\boldsymbol{x}})\neq(\boldsymbol{b}\star_{c}\boldsymbol{a})\star_{c}\boldsymbol{\boldsymbol{x}},$

which is not suitable for defining a new product operator. So we define

$\boldsymbol{y}{:=}\boldsymbol{a}\star_{c}\boldsymbol{x}=\mathsf{Th}(\Gamma^{-1}\boldsymbol{a})\boldsymbol{x}$

clearly this product which is convolution (with reflective BC) between
$\widehat{\boldsymbol{a}}=\Gamma^{-1}\boldsymbol{a}$ and $x$ has associative
property.

Similar to convolution with periodic BC in section 3, if we substitute the
elements $a_{i},x_{i}$ and $y_{i}$ of convolution with reflective BC (19),
with the matrices
$\widehat{\mathcal{A}}[:,i,:]=\widehat{A}_{i}\in\mathbb{R}^{n_{1}\times
n_{3}}$, $\mathcal{X}[:,i,:]=X_{i}\in\mathbb{R}^{n_{3}\times n_{4}}$, and
$\mathcal{Y}[:,i,:]=Y_{i}\in\mathbb{R}^{n_{1}\times n_{4}}$ for
$i=1,\cdots,n_{2}$, where
$\widehat{\mathcal{A}}=(\Gamma^{-1})_{2}.\mathcal{A},$ the mode-2 block
reflective padding of $\mathcal{X}$ will be

$\displaystyle X_{i}=\begin{cases}X_{1-i}&i=0,\cdots,1-n_{2}\\\
X_{2n_{2}-i+1}&i=n_{2}+1,\cdots,2n_{2}\end{cases}$ (27)

and (20) for $i=1,\cdots,n_{2}$ becomes

$\displaystyle\mathcal{Y}[:,i,:]=\sum_{j=1}^{n_{2}}\left(\widehat{\boldsymbol{A}}_{|i-j|+1}+(1-\delta_{i+j,n_{2}+1})\begin{cases}\widehat{\boldsymbol{A}}_{i+j}&i+j\leq
n_{2}\\\
\widehat{\boldsymbol{A}}_{2(n_{2}+1)-(i+j)}&i+j>n_{2}\end{cases}\right)X[:,i,:].$
(28)

So, this is the bock convolution with reflective-padding(BC) in mode-2 of
tensors $\widehat{\mathcal{A}}\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}$
and $\mathcal{X}\in\mathbb{R}^{n_{3}\times n_{2}\times n_{4}}$ which gives
$\mathcal{Y}\in\mathbb{R}^{n_{1}\times n_{2}\times n_{4}}$. By defining the
4-order tensor $\mathsf{TH}(\mathcal{A})$ with elements

$\displaystyle\mathsf{TH}(\widehat{\mathcal{A}})[:,i_{2},:,i_{4}]=\widehat{\mathcal{A}}[:,|i_{2}-i_{4}|+1,:]+\left(1-\delta_{i_{2}+i_{4},n_{2}+1}\right)\begin{cases}\widehat{\mathcal{A}}[:,i_{2}+i_{4},:]&i_{2}+i_{4}\leq
n_{2}\\\
\widehat{\mathcal{A}}[:,2(n_{2}+1)-(i_{2}+i_{4}),:]&i_{2}+i_{4}>n_{2}\end{cases}.$
(29)

equation (28) becomes

$\displaystyle\mathcal{Y}[:,i_{2},:]=\sum_{i_{4}=1}^{n}\mathsf{TH}(\widehat{\mathcal{A}})[:,i_{2},:i_{4}]\mathcal{X}[:,i_{4},:],\quad
i_{2}=1,\cdots,n_{2}$

which is equal to the following contraction:

$\displaystyle\mathcal{Y}=\langle\mathsf{TH}(\widehat{\mathcal{A}}),\mathcal{X}\rangle_{3:4;1:2}.$
(30)

######  Definition 4.1 ($\star_{c}{}\text{-Product}$)

We define $\star_{c}$ operation between $\mathcal{A}\in\mathbb{R}^{I_{1}\times
I_{2}\times J}$ and $\mathcal{X}\in\mathbb{R}^{J\times I_{2}\times I_{3}}$
tensors, as

$\displaystyle\mathcal{Y}=\mathcal{A}\star_{c}\mathcal{X}=\langle\mathsf{TH}(\widehat{\mathcal{A}}),{\mathcal{X}}\rangle_{3{:}4,1{:}2},\quad\widehat{A}=(\Gamma)_{2}.\mathcal{A}.$
(31)

In the following we show that this $\star_{c}$ product can be done very fast
by Fast cosine trasform on mode-2 of tensors $\mathcal{A}$ and $\mathcal{X}$,
without constraucting tensors $\widehat{A}$ and
$\mathsf{TH}(\widehat{\mathcal{A}})$.

From (29) it’s clear that
$\mathsf{TH}(\widehat{\mathcal{A}})[i_{1},:,i_{3},:]$ is a Toeplitz plus
Hankel matrix, in the form (22), constructed by
$\widehat{\mathcal{A}}[i_{1},:,i_{3}]$ vector. so

$\displaystyle\mathsf{TH}(\widehat{\mathcal{A}})[i_{1},:,i_{3},:]=\mathsf{Th}(\widehat{\mathcal{A}}[i_{1},:,i_{3}])$
(32)

where $\mathsf{Th}(\mathcal{A}[i_{1},:,i_{3}])$ has the structure like (24).
Similar to definition of circulant and Toeplitz tensor in Rezghi and Elden
(2011), we say that $\mathsf{TH}(\widehat{\mathcal{A}})$ is an
$\\{2,4\\}$-Toeplitz-plus-Hankel tensor(and for simplicity in abbreviation say
$\mathsf{TH}(\widehat{\mathcal{A}})$ is $\\{2,4\\}$-TH tensor).

###### Lemma 3

The $\\{2,4\\}-$TH tensor $\mathsf{TH}(\widehat{\mathcal{A}})$, where
$\widehat{\mathcal{A}}=(\Gamma^{-1})_{2}.\mathcal{A}$ could be decomposed as
follows:

$\displaystyle\mathsf{TH}(\widehat{\mathcal{A}})=({C^{-1}},{C^{\sf
T}})_{2,4}.\mathcal{D},$ (33)

where $\mathcal{D}={\sf diag}_{\\{2,4\\}}(\overline{\mathcal{A}})$ is a
$\\{\\{2,4\\}\\}$-diagonal tensor with elements,

$\displaystyle\mathcal{D}[i_{1},i_{2},i_{3},i_{4}]=\delta_{i_{2},i_{2}}{\overline{\mathcal{A}}}[i_{1},i_{2},i_{3}],\quad\overline{\mathcal{A}}=(\overline{C})_{2}.\mathcal{A}$
(34)

Proof  From (32)
$\mathsf{TH}(\widehat{\mathcal{A}})[i_{1},:,i_{3},:]=\mathsf{Th}(\widehat{\mathcal{A}}[i_{1},:,i_{3}])$
is a Toeplitz-plus-Hankel matrix and so by decomposition (25) and
$\widehat{\mathcal{A}}=(\Gamma^{-1})_{2}.{\mathcal{A}}$, we have

$\displaystyle\mathsf{TH}(\widehat{\mathcal{A}})[i_{1},:,i_{3},:]={C}^{\raisebox{1.0pt}{$-1$}}\Lambda^{(i_{1},i_{3})}{C}=\left(C^{-1},C^{\sf
T}\right)_{1,2}.\Lambda^{(i_{1},i_{3})}$ (35)

where

$\displaystyle\Lambda^{(i_{1},i_{3})}={\sf
diag}({C}~{}\Gamma~{}\widehat{\mathcal{A}}[i_{1},:,i_{3}])={\sf
diag}({C}~{}\mathcal{A}[i_{1},:,i_{3}])={\sf
diag}(\overline{\mathcal{A}}[i_{1},:,i_{3}]).$ (36)

Here
$\Lambda^{(i_{1},i_{3})}(i_{2},j_{4})=\delta_{i_{2}i_{4}}\overline{\mathcal{A}}[i_{1},i_{2},i_{3}]$.
Therefore, the tensor $\mathcal{D}$ defined as
$\mathcal{D}[i_{1},{:},i_{3},{:}]=\Lambda^{(i_{1},i_{3})}$ satisfies

$\mathcal{D}[i_{1},i_{2},i_{3},i_{4}]=\Lambda^{(i_{1},i_{3})}(i_{2},i_{4})=\delta_{i_{2}i_{4}}\overline{\mathcal{A}}[i_{1},i_{2},i_{3}],$

which proves (34). Also, from definition of $\mathcal{D}$, the equation (35)
will be

$\displaystyle\mathsf{TH}(\widehat{\mathcal{A}})[i_{1},:,i_{3},:]=({C}^{\raisebox{1.0pt}{$-1$}},{C}^{\raisebox{1.0pt}{${\sf
T}$}})_{2,4}.\mathcal{D}(i_{1},:,i_{3},:)$ (37)

which proves (33).

Now, the lemma (3), helps to develop a fast methods to compute $\star_{c}$
product by cosine transform on mode-2 of tensors $\mathcal{A}$ and
$\mathcal{X}$, without constructing tensors $\widehat{A}$ and
$\mathsf{TH}(\widehat{\mathcal{A}})$ as following lemma.

###### Lemma 4

The $\star_{c}$ product
$\mathcal{Y}=\mathcal{A}\star_{c}\mathcal{X}=\langle\mathsf{TH}(\widehat{\mathcal{A}}),{\mathcal{X}}\rangle_{3{:}4,1{:}2},$
in equation (31) could be computed by cosine transform as follows:

$\displaystyle\mathcal{Y}=({C}^{\raisebox{1.0pt}{$-1$}})_{2}.\overline{\mathcal{Y}}$

where
$\overline{\mathcal{Y}}[{:},i_{2},{:}]=\overline{\mathcal{A}}[{:},i_{2},{:}]~{}\overline{\mathcal{X}}[{:},i_{2},{:}],\quad
i_{2}=1,\cdots,n_{2}$ and

$\displaystyle\overline{\mathcal{X}}=({C})_{2}.\mathcal{X},\quad\overline{\mathcal{A}}=({C})_{2}.\mathcal{A}$

Proof  Proof: From Lemma 3,
$\mathsf{TH}(\widehat{\mathcal{A}})=({C}^{\raisebox{1.0pt}{$-1$}},{C}^{\raisebox{1.0pt}{${\sf
T}$}})_{2,4}.\mathcal{D}$, where
$\mathcal{D}=\text{diag}_{\\{2,4\\}}(\overline{\mathcal{A}})$, and
$\overline{\mathcal{A}}=(C)_{2}.\mathcal{A}$. So

$\displaystyle\mathcal{Y}$
$\displaystyle=\langle\mathsf{TH}(\widehat{\mathcal{A}}),\mathcal{X}\rangle_{3{:}4,1{:}2}$
$\displaystyle=\langle({C}^{\raisebox{1.0pt}{$-1$}},{C}^{\raisebox{1.0pt}{${\sf
T}$}})_{2,4}.\mathcal{D},\mathcal{X}\rangle_{3{:}4,1{:}2}$
$\displaystyle=({C}^{\raisebox{1.0pt}{$-1$}})_{2}.\left[\langle\mathcal{D},({C})_{2}.\mathcal{X}\rangle_{3{:}4,1{:}2}\right]$
(38)

which the last equation comes immediately follow from the definitions of
contraction and matrix-tensor product. If
$\overline{\mathcal{X}}=({C})_{2}.\mathcal{X}$ and
$\overline{\mathcal{Y}}=({C})_{2}.\mathcal{Y}$ equation (4) becomes

$\displaystyle\overline{\mathcal{Y}}=\langle\mathcal{D},\overline{\mathcal{X}}\rangle_{3{:}4,1{:}2}.$
(39)

Since $\mathcal{D}=\text{diag}_{\\{2,4\\}}(\overline{\mathcal{A}})$ is
$\\{2,4\\}-$diagonal, (39) gives,

$\displaystyle\overline{\mathcal{Y}}[{:},i_{2},{:}]=\overline{\mathcal{A}}[{:},i_{2},{:}]~{}\overline{\mathcal{X}}[{:},i_{2},{:}],$

which proves the Lemma.
Algorithm 2 displays how to compute $\star_{c}{}\text{-Product}$ between two
3D tensors.

Algorithm 2 $\star_{c}{}\text{-Product}$ for 3-order tensors

1:$\mathcal{A}\in\mathbb{R}^{n_{1}\times n_{2}\times\ell}$,
$\mathcal{X}\in\mathbb{R}^{\ell\times n_{2}\times n_{3}}$

2:$\mathcal{Y}$

3:Compute $\overline{\mathcal{A}}=(\boldsymbol{C})_{2}.\mathcal{A}$ and
$\overline{\mathcal{X}}=(\boldsymbol{C})_{2}.\mathcal{X}$

4:Compute each mode-2 slice of $\overline{\mathcal{Y}}$ by
$\overline{\boldsymbol{Y}}_{i}=\overline{\boldsymbol{A}}_{i}\overline{X}_{i}$,
$i=1,\cdots,n_{2}$

5:Compute $\mathcal{Y}=(\boldsymbol{C}^{-1})_{2}.\overline{\mathcal{Y}}$

###  4.1 $\star_{c}$-Product Generalization for arbitrary-order tensors

In this section we would like to extend the $\star_{c}$ product for for
arbitrary order tensors $\mathcal{A}\in\mathbb{R}^{I_{1}\times\dots\times
I_{N-1}\times J}$ and $\mathcal{X}\in\mathbb{R}^{J\times
I_{2}\times\dots\times I_{N}}$. In the last section for 3-order, we defined
$\star_{c}$ product of two tensors $\mathcal{A}\in$ and $\mathcal{X}\in$ as
the Block convolution with reflective padding of mode-2 of $\widehat{A}$ and
$X$, which leads to contraction (30). Now, if we substitute the block
components $\widehat{A}_{i},X_{i}$ of Block convolution (28) with boundary
(27) by the slices $\widehat{\mathcal{A}}[:,i_{2},\cdots,i_{N-1},:]$ and
$\mathcal{X}[:,i_{2},\cdots,i_{N-1},:]$ of tensors

$\widehat{\mathcal{A}}=(\Gamma,\cdots,\Gamma)_{2,\cdots,N-1}.{\mathcal{A}}\in\mathbb{R}^{I_{1}\times
I_{2}\times\cdots\times I_{N-1}\times
J},\quad\mathcal{X}\in\mathbb{R}^{J\times I_{2}\times\cdots\times I_{N}},$

we have $\\{2,\cdots,N-1\\}-$reflective padding as follows:

$\displaystyle\mathcal{X}[:,i_{2},i_{3},\cdots,i_{N-1},:]=\mathcal{X}[:,s_{2},s_{3},\cdots,s_{N-1},:],\quad
s_{j}=\begin{cases}1-i_{j},&i_{j}=0,\cdots,1-I_{j}\\\
2I_{j}-i_{j}+1,&i_{j}=I_{j}+1,\cdots,2I_{j}\end{cases}.$ (40)

and the convolution (28) will be

$\displaystyle\mathcal{Y}[:,\bar{i},:]=\sum_{j_{2},\cdots,j_{N-1}}^{I_{2},\cdots,I_{N-1}}\left(\widehat{\mathcal{A}}[:,{|\bar{i}-\bar{j}|}+1,:]+\prod_{k=2}^{N-1}(1-\delta_{i_{k}+j_{k},n_{k}+1})\widehat{\mathcal{A}}[\bar{:,\ell,:}]\right)\mathcal{X}[:,\bar{j},:],$
(41)

where $\bar{i}=i_{2},\cdots,i_{N-1}$, $\bar{j}=j_{2},\cdots,j_{N-1}$ and

$\displaystyle{|\bar{i}-\bar{j}|+1}$
$\displaystyle=|i_{2}-j_{2}|+1,|i_{3}-j_{3}|+1,\ldots,|i_{N-1}-j_{N-1}|+1$
(42) $\displaystyle\bar{\ell}$
$\displaystyle=\bar{\ell}_{2},\ldots,\bar{\ell}_{N-1},\qquad\bar{\ell}_{k}=\begin{cases}i_{k}+j_{k}&i_{k}+j_{k}\leq
I_{k}\\\ 2n_{k}-(i_{k}+j_{k})&i_{k}+j_{k}>I_{k}\end{cases}$ (43)

Now by defining $\mathsf{TH}(\widehat{\mathcal{A}})$ as

$\displaystyle\mathsf{TH}(\widehat{\mathcal{A}})[{:},i_{2},i_{3},\ldots,i_{N-1},{:},j_{2},j_{3},\ldots,j_{N-1}]=\widehat{\mathcal{A}}[:,{|\bar{i}-\bar{j}|}+1,:]+\prod_{k=2}^{N-1}(1-\delta_{i_{k}+j_{k},n_{k}+1})\widehat{\mathcal{A}}[:,\bar{\ell},:]$
(44)

equation (28) leads to the following contraction product

$\displaystyle\mathcal{Y}=\langle\mathsf{TH}(\widehat{\mathcal{A}}),\mathcal{X}\rangle_{N:2(N-1);1:N-1}.$
(45)

###### Definition 4.2

We define $\star_{c}$ operation between $\mathcal{A}\in\mathbb{R}^{I_{1}\times
I_{2}\cdots\times I_{N-1}\times J}$ and $\mathcal{X}\in\mathbb{R}^{J\times
I_{2}\cdots\times\times I_{N}}$ tensors, as

$\displaystyle\mathcal{Y}=\mathcal{A}\star_{c}\mathcal{X}=\langle\mathsf{TH}(\widehat{\mathcal{A}}),\mathcal{X}\rangle_{N:2(N-1);1:N-1}.$
(46)

Here $\mathsf{TH}(\widehat{\mathcal{A}})\in\mathbb{R}^{I_{1}\times
I_{2}\times\cdots\times I_{N}\times I_{2}\times I_{N}-1}$ is a
$\\{2{:}N-1;N+1{:}2(N-1)\\}$-TH tensor and in the following we show that this
tensor is diagonaizable by cosine transform in $\\{2,\dots,N{-}1\\}$-modes,
which cause to find $x_{c}$ product very fast without construction of
$\mathsf{TH}(\widehat{\mathcal{A}})$ only by applying fast cosine transform in
$\\{2,\dots,N{-}1\\}$-modes of tensors $\mathcal{A}$ and $\mathcal{X}$. To
show this property we need an extension of (Hadamard) point-wise product for
tensors in some modes as follows:

###### Definition 4.3

We define the the $\\{2,\cdots,N-1\\}-$Hadamard (point-wise) product of
order-N tensors $\mathcal{S}\in\mathbb{R}^{I_{1}\times I_{2}\times
I_{N-1}\times I_{N}}$ and $\mathcal{P}\in\mathbb{R}^{I_{N}\times I_{2}\times
I_{N-1}\times J}$ according to ${2,\cdots,N-1}$-modes as follows

$\displaystyle\mathcal{T}=\mathcal{S}\odot_{2{:}N-1}\mathcal{P}\Rightarrow\mathcal{T}[{:},i_{2},\ldots,i_{N-1},{:}]=\mathcal{S}[{:},i_{2},\ldots,i_{N-1},{:}]~{}\mathcal{P}[{:},i_{2},\ldots,i_{N-1},{:}]$

###### Theorem 5

The $\\{2{:}N-1;N+1{:}2(N-1)\\}$-TH tensor
$\mathsf{TH}(\mathcal{A})\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times
I_{N}\times I_{2}\times I_{N}-1}$, where
$\widehat{\mathcal{A}}=(\Gamma,\cdots,\Gamma)_{2,\cdots,N-1}.{\mathcal{A}}\in\mathbb{R}^{I_{1}\times
I_{2}\times\cdots\times I_{N-1}\times J}$, $\mathcal{X}\in\mathbb{R}^{J\times
I_{2}\times\cdots\times I_{N}}$ could be decomposed as follows:

$\mathsf{TH}(\mathcal{A})=({\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}},\cdots,{\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}},{\boldsymbol{C}}^{\raisebox{1.0pt}{${\sf
T}$}},\cdots,{\boldsymbol{C}}^{\raisebox{1.0pt}{${\sf
T}$}})_{2{:}N-1;N+1:2(N-1)}.\mathcal{D}$ $\mathcal{D}={\sf
diag}_{\\{2:N-1;N+1:2N-2\\}}(\overline{\mathcal{A}}),\quad\mathcal{A}=(\overline{\boldsymbol{C}},\cdots,\overline{\boldsymbol{C}})_{2{:}N}.{\mathcal{A}}$

Proof  Without loss of generality, let $\mathcal{A}\in\mathbb{R}^{I_{1}\times
I_{2}\times I_{3}\times I_{4}}$ .So
$\mathsf{TH}(\mathcal{A})\in\mathbb{R}^{I_{1}\times I_{2}\times I_{3}\times
I_{4}\times I_{2}\times I_{3}}$ will be $\\{2,3;5,6\\}-$TH tensor. since
$\mathsf{TH}(\widehat{\mathcal{A}})$ is $\\{3,6\\}-$TH tensor, from lemma 3,
we have

$\displaystyle\mathsf{TH}(\widehat{\mathcal{A}})=({\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}},{\boldsymbol{C}}^{\raisebox{1.0pt}{${\sf
T}$}})_{3,6}.\overline{\mathcal{D}},\quad\overline{\mathcal{D}}={\sf
diag}_{\\{3,6\\}}(\mathcal{D}_{1}),\quad\mathcal{D}_{1}=({\boldsymbol{C}})_{3}.\mathsf{TH}(\widehat{\mathcal{A}})[{:},{:},{:},{:},{:},1]$
(47)

So,

$\displaystyle\overline{\mathcal{D}}[i_{1},i_{2},i_{3},i_{4},i_{5},i_{6}]=\delta_{i_{3},i_{6}}\mathcal{D}_{1}[i_{1},i_{2},i_{3},i_{4},i_{5},1].$
(48)

It’s clear that $\mathcal{D}_{1}$ is a $\\{2,5\\}$-TH tensor and so can be
diagonalized as follows:

$\displaystyle\mathcal{D}_{1}=\left(C^{-1},C^{\sf T}\right)_{\\{2,5\\}}.{\sf
diag(\mathcal{D}_{2})}$ (49)

where

$\displaystyle\mathcal{D}_{2}=({\boldsymbol{C}})_{2}.\mathcal{D}_{1}[{:},{:},{:},{:},1,1]$
(50)

But by replacing $\mathcal{D}_{1}$ from (49) in (50), we have

$\displaystyle\mathcal{D}_{2}=({\boldsymbol{C}},{\boldsymbol{C}})_{2,3}.\mathsf{TH}(\mathcal{A})[{:},{:},{:},{:},1,1]=({\boldsymbol{C}},{\boldsymbol{C}})_{2,3}.\mathcal{A}=\overline{\mathcal{A}}$
(51)

by replacing $\mathcal{D}_{1}$ from (49) to (47) and substituting it with
$\mathcal{D}_{1}$,

$\displaystyle\overline{\mathcal{D}}=$ $\displaystyle{\sf
diag}_{\\{3,6\\}}(\mathcal{D}_{1})={\sf
diag}_{\\{3,6\\}}\left(({\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}},{\boldsymbol{C}}^{\raisebox{1.0pt}{${\sf
T}$}})_{2,5}.{\sf diag}_{\\{2,5\\}}(\mathcal{D}_{2})\right)$ $\displaystyle=$
$\displaystyle({\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}},{\boldsymbol{C}}^{\raisebox{1.0pt}{${\sf
T}$}})_{2,5}.\left({\sf diag}_{\\{3,6\\}}\left({\sf
diag}_{\\{2,5\\}}(\mathcal{D}_{2})\right)\right)$ $\displaystyle=$
$\displaystyle({\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}},{\boldsymbol{C}}^{\raisebox{1.0pt}{${\sf
T}$}})_{2,5}.({\sf diag}_{\\{\\{2,5\\},\\{3,6\\}\\}}(\mathcal{D}_{2}))$
$\displaystyle=$
$\displaystyle({\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}},{\boldsymbol{C}}^{\raisebox{1.0pt}{${\sf
T}$}})_{2,5}.{\sf diag}_{\\{\\{2,5\\},\\{3,6\\}\\}}(\overline{\mathcal{A}})$
(52)

which the last equation comes from (51) and completes the proof.

###### Lemma 6

The $\star_{c}{}\text{-Product}$ $\mathcal{Y}=\mathcal{A}\star_{c}\mathcal{X}$
for $N$-order tensors $\mathcal{A}$ and $\mathcal{X}$ could be handeled by
cosine transform as follows:

$\mathcal{Y}=({\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}},\cdots,{\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}})_{2{:}N-1}\overline{\mathcal{Y}}$

where

$\displaystyle\overline{\mathcal{Y}}=\overline{\mathcal{A}}\odot_{2{:}N-1}\overline{\mathcal{X}},\quad\overline{\mathcal{X}}=({\boldsymbol{C}},\cdots,{\boldsymbol{C}})_{2{:}N-1}.\mathcal{X},\quad\overline{\mathcal{A}}=({\boldsymbol{C}},\cdots,{\boldsymbol{C}})_{2{:}N-1}.\mathcal{A}.$

Proof  By substituting the decomposition of
$\mathsf{TH}(\widehat{\mathcal{A}})$ in Theorem 5, in

$\displaystyle\mathcal{Y}=\langle{\mathsf{TH}}(\widehat{\mathcal{A}}),\mathcal{X}\rangle_{N{:}2(N-1),2{:}N-1}$

we have

$\displaystyle\mathcal{Y}$
$\displaystyle=({\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}},\cdots,{\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}})_{2{:}N-1}.\left[\langle\mathcal{D},({\boldsymbol{C}},\cdots,{\boldsymbol{C}})_{2{:}N-1}.\mathcal{X}\rangle_{N{:}2(N-1),2{:}N-1}\right]$
(53)
$\displaystyle=({\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}},\cdots,{\boldsymbol{C}}^{\raisebox{1.0pt}{$-1$}})_{2{:}2(N-1)}.\left[\langle\mathcal{D},\overline{\mathcal{X}}\rangle_{N{:}2(N-1),2{:}N-1}\right]$

Now its clear that

$\displaystyle\overline{\mathcal{Y}}$ $\displaystyle=\langle
D,\overline{\mathcal{X}}\rangle_{N{:}2(N-1),2{:}N-1}$
$\displaystyle=\overline{\mathcal{A}}\odot_{2{:}N-1}\overline{\mathcal{X}}$

where the second equation comes from definition of $\mathcal{D}$ and completes
the proof.

The algorithm of computing $\star_{c}{}\text{-Product}$ for arbitrary order
tensor is provided in Algorithm 3.

Algorithm 3 $\star_{c}{}\text{-Product}$ for arbitrary order tensors

1:$\mathcal{A}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times I_{N-1}\times
J}$, $\mathcal{X}\in\mathbb{R}^{J\times I_{2}\times I_{3}\times\cdots\times
I_{N}}$

2:$\mathcal{Y}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$

3:${\bar{\mathcal{A}}}=\left(C,\cdots,C\right)_{2:N-1}.\mathcal{A}$,
${\bar{\mathcal{Y}}}=\left(C,\cdots,C\right)_{2:N-1}.\mathcal{Y}$

4:${\mathcal{\bar{Y}}}[:,\bar{i},:]={\mathcal{\bar{A}}}[:,\bar{i},:]{\mathcal{\bar{X}}}[:,\bar{i},:],\quad\bar{i}=i_{2},\cdots,i_{N-1},i_{k}=1,\cdots,I_{k}$

5:${\mathcal{Y}}=\left(C^{\sf T},\cdots,C^{\sf
T}\right)_{2:N-1}.{\overline{\mathcal{Y}}}$

Also we provide the SVD decomposition for any arbitrary $N$-order tensor based
on $\star_{c}$ product. For obtaining this decomposition we need to define
transpose of N-order tensor based on $\star_{c}$ product. $\mathcal{A}^{\sf
T}$ is adjoint operator(Transpose) of $A$ according to $\star_{c}$ operator if
satisfies

$\displaystyle\left<\mathcal{A}\star_{c}\mathcal{X},\mathcal{Y}\right>=\left<\mathcal{X},\mathcal{A}^{\sf
T}\star_{c}\mathcal{Y}\right>$

for every tensors $\mathcal{X},\mathcal{Y}.$ By some mathematical manupulation
, one can see that this Transpose tensor is $\mathcal{A}^{\sf
T}\in\mathbb{R}^{I_{N}\times I_{2}\times\cdots\times I_{N-1}\times I_{1}}$
with the following elements

$\displaystyle\mathcal{A}^{\sf
T}[i_{1},i_{2},\cdots,i_{N-1},i_{N}]=\mathcal{A}[i_{N},i_{2},\cdots,i_{N-1},i_{1}]$
(54)

###### Theorem 7

: $\star_{c}{}\text{-SVD}$ for an $n$-order tensor.For each tensor
$\mathcal{A}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$ with arbitrary
order $N$, the following decomposition named $\star_{c}{}\text{-SVD}$ exists

$\displaystyle\mathcal{A}=\mathcal{U}\star_{c}\mathcal{S}\star_{c}\mathcal{V}^{\mathsf{T}}$

where $\mathcal{U}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N-1}\times I_{N}}$
and $\mathcal{V}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N-1}\times I_{N}}$
are orthogonal tensors according to $\star_{c}{}\text{-Product}$ and
$\mathcal{S}\in\mathbb{R}^{I_{N}\times I_{2}\times\cdots\times I_{N-1}\times
I_{N}}$ is an $\\{1,N\\}$-diagonal tensor.

Proof : Let
$\overline{\mathcal{A}}=(\boldsymbol{C}_{2},\cdots,\boldsymbol{C}_{N-1})_{2{:}N-1}.\mathcal{A}$,
for every index set $\bar{i}=i_{2},\cdots,i_{N-1}$ consider the SVD of
$\overline{\mathcal{A}}[{:},\bar{i},{:}]$ matrix as follows:

$\displaystyle\overline{\mathcal{A}}[{:},\bar{i},{:}]=\overline{U}_{\bar{i}}\overline{S}_{\bar{i}}\overline{V}_{\bar{i}}^{\mathsf{T}},\quad\overline{\boldsymbol{U}}_{\bar{i}}\in\mathbb{R}^{I_{1}\times
I_{1}},\quad\overline{\boldsymbol{S}}_{\bar{i}}\in\mathbb{R}^{I_{1}\times
I_{N}},\quad\overline{\boldsymbol{V}}_{\bar{i}}\in\mathbb{R}^{I_{N}\times
I_{N}}.$ (55)

if we construct the tensors
$\overline{{\mathcal{U}}}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times
I_{N-1}\times I_{1}}$, $\overline{{\mathcal{S}}}\in\mathbb{R}^{I_{1}\times
I_{2}\times\cdots I_{N-1}\times I_{N}}$ and
$\overline{\mathcal{V}}\in\mathbb{R}^{I_{N}\times I_{2}\times\cdots\times
I_{N-1}\times I_{N}}$, as follows:

$\displaystyle\overline{\mathcal{U}}[{:},\bar{i},{:}]=\overline{U}_{\bar{i}},\quad\overline{\mathcal{S}}[{:},\bar{i},{:}]=\overline{S}_{\bar{i}},\quad\overline{\mathcal{V}}[{:},\bar{i},{:}]=\overline{{V}}_{\bar{i}},\quad\bar{i}=i_{2},\cdots,i_{N-1}.$

We claim that

$\displaystyle\mathcal{P}=\mathcal{U}\star_{c}\mathcal{S}\star_{c}\mathcal{V}^{\mathsf{T}}$

where

$\displaystyle\mathcal{U}=(\boldsymbol{C}_{2}^{-1},\cdots,\boldsymbol{C}_{N-1}^{-1})_{2{:}N-1}.\overline{\mathcal{U}},\quad\mathcal{V}=(\boldsymbol{C}_{2}^{-1},\cdots,\boldsymbol{C}_{N-1}^{-1})_{2{:}N-1}.\overline{\mathcal{V}},\quad\mathcal{S}=(\boldsymbol{C}_{2}^{-1},\cdots,\boldsymbol{C}_{N-1}^{-1})_{2{:}N-1}.\overline{\mathcal{S}}$

is equal to $\mathcal{A}$. For showing this let
$\boldsymbol{\mathcal{Q}}=\mathcal{S}\star_{c}\mathcal{V}^{\mathsf{T}}$, then
$\mathcal{P}=\mathcal{U}\star_{c}\boldsymbol{\mathcal{Q}}$. By definition of
$\star_{c}{}\text{-Product}$ we have

$\displaystyle\overline{\mathcal{P}}[{:},i,{:}]$
$\displaystyle=\overline{\mathcal{U}}[{:},i,{:}]\overline{\boldsymbol{\mathcal{Q}}}[{:},i,{:}]$
$\displaystyle\overline{\boldsymbol{\mathcal{Q}}}[{:},i,{:}]$
$\displaystyle=\overline{\mathcal{S}}[{:},i,{:}]\overline{\mathcal{V}}^{\mathsf{T}}[{:},i,{:}]$

So,
$\overline{\mathcal{P}}[{:},\bar{i},{:}]=\overline{\mathcal{U}}[{:},\bar{i},{:}]\overline{\mathcal{S}}[{:},\bar{i},{:}]\overline{\mathcal{V}}^{\mathsf{T}}[{:},\bar{i},{:}]=\overline{\mathcal{A}}[{:},\bar{i},{:}]$
therefore $\overline{\mathcal{P}}=\overline{\mathcal{A}}$ and so
$\mathcal{P}=\mathcal{A}$.
The algorithm 4 provides the process of $\star_{c}{}\text{-SVD}$ for an
arbitrary order tensor. Also, like $t-SVD$ the truncated version of
$\star_{c}{}\text{-SVD}$ for arbitrary $r\leq\min{\\{I_{1},I_{N}\\}}$ could be
obtained as follows

$\mathcal{A}\approx\mathcal{A}_{r}=\mathcal{U}_{r}\star_{c}\mathcal{S}_{r}\star_{c}\mathcal{V}_{r}^{\sf
T}$

where

$\displaystyle\overline{\mathcal{U}_{r}}[:,\bar{i},:]=\overline{U}_{\bar{i}}[:,1:r],\quad\overline{\mathcal{S}_{r}}(:,\bar{i},:)=\overline{S}_{\bar{i}}[1:r,1:r]\quad\overline{\mathcal{V}_{r}}(:,\bar{i},:)=\overline{V}_{\bar{i}}[:,1:r]^{\sf
T}$ (56)

from SVD of $\overline{\mathcal{A}}[:,\bar{i},:]$ in (55). This truncation
could be used for different tasks like compression and denoising.

The mentioned truncation is applied truncated SVD in each slices of data in
cosine space. In the following we show that further this truncation another
truncation that removes some slices (corresponding to some specific
frequencies) in cosine space also could be defined for this decomposition. As
one know for arbitrary vector $a$, $\bar{a}=Ca$, denotes the coefficient of
cosine transform. Here the $\bar{a}_{i}$ with small and large indices
correspond to low and high frequencies. So, by removing the $a_{i}$ with large
indices, we have one high pass filter that could be used as denoising and also
compression of data in $a$. So in $\star_{c}$-SVD, of order-3 tensor
$\mathcal{A}$, the slice’s $\overline{A}[:,i,:]$ for small and large indices,
contain low and high pass coefficients, respectively. Therefor if for some
specific index like $l$, we set $\overline{A}[:,i,:]=0$ for $i>l$, we have
high pass filter. Now if for $i\leq l$, we use the truncated filter like (55),
we have a double filter decomposition. This double filtering uses the benefits
of filtering on svd and frequency space, simultaneously and we expect that has
better results in comparison filers like (56). This double truncation based on
$\star_{c}-SVD$ for arbitrary order can be seen in algorithm 4.

Algorithm 4 Double filtering by $\star_{c}{}\text{-SVD}$

1:$\mathcal{A}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$, $\ell$
truncation index for cosine space, $k$ truncation index for SVD space,

2:truncated $\star_{c}{}\text{-SVD}$
($\mathcal{A}_{k}^{l}=\mathcal{U}_{k}^{l}\star_{c}\mathcal{S}_{k}^{l}\star_{c}\mathcal{V}_{k}^{l}\approx\mathcal{A}$)

3:Compute $\overline{\mathcal{A}}=\left(C,\cdots,C\right)_{2:N-1}.\mathcal{A}$

4:for all $\bar{i}=i_{2},\cdots,i_{N-1}$,
$\overline{\mathcal{A}}[:,\bar{i},:]$ do

5: if $i_{s}<\ell$ for all $s=2,\cdots,N-1$ then

6: Compute
$\overline{\mathcal{A}}[:,\bar{i},:]=\overline{\mathcal{U}}_{\bar{i}}[:,1{:}k]\overline{\mathcal{S}}_{\bar{i}}[1{:}k,1{:}k]\overline{\mathcal{V}}_{\bar{i}}[:,1{:}k]^{T}$

7: else

8: Let $\overline{\mathcal{A}}[:,\bar{i},:]=0$ i.e (
$\overline{\mathcal{U}}_{\bar{i}}[:,1{:}k]=0,\overline{\mathcal{S}}_{\bar{i}}[1{:}k,1{:}k]=0,\overline{\mathcal{V}}_{\bar{i}}[:,1{:}k]=0$
)

9: end if

10:end for

11:$\mathcal{U}_{k}^{l}=\left(C^{-1},\cdots,C^{-1}\right)_{2:N-1}.\overline{\mathcal{U}}$

12:$\mathcal{S}_{k}^{l}=\left(C^{-1},\cdots,C^{-1}\right)_{2:N-1}.\overline{\mathcal{S}}$

13:$\mathcal{V}_{k}^{l}=\left(C^{-1},\cdots,C^{-1}\right)_{2:N-1}.\overline{\mathcal{V}}$

##  5 Experimental results

In this section, we present experiments on both synthetic random tensors and
well-known datasets, as described in Table 1, to demonstrate the efficacy of
the proposed $\star_{c}{}\text{-SVD}$ method. The last dimension in Table 1
represents the number of samples for each dataset. For example, if dataset
$\mathcal{A}\in R^{I_{1},I_{2},\dots,I_{N}}$, then $I_{N}$ denotes the number
of samples in $\mathcal{A}$. In these experiments, we compare the performance
of our $\star_{c}{}\text{-SVD}$ method to that of t-SVD in compression,
clustering, and classification applications.

Table 1: Characters of different datasets

Dataset Name | Size | Compression | Clustering | Classification
---|---|---|---|---
| Brain MRI
---
(Brain Tumor Detection) Chakrabarty (2019)
$253\times 240\times 240$ | Yes | No | Yes
CBCL-face | $2414\times 192\times 168$ | Yes | No | Yes
Coil-100 Nene et al. (1988) | $7200\times 128\times 128$ | Yes | No | Yes
Digit Recognizer (MNIST) | $60000\times 28\times 28$ | Yes | No | Yes
Yale | $2414\times 192\times 168$ | Yes | No | Yes
Cifar | $60000\times 32\times 32\times 3$ | Yes | No | Yes
3D-MNIST | $10000\times 16\times 16\times 16$ | Yes | No | Yes
Bonsai | $256\times 256\times 256$ | Yes | No | No
Engine | $256\times 256\times 128$ | Yes | No | No
Foot | $256\times 256\times 256$ | Yes | No | No
Skull | $256\times 256\times 256$ | Yes | No | No
StatueLeg | $341\times 341\times 93$ | Yes | No | No
SyntheticA | $100\times 40\times 100$ | Yes | No | No
SyntheticB | $100\times 100\times 100$ | Yes | No | No
SyntheticC | $100\times 500\times 100$ | Yes | No | No
SyntheticD | $100\times 500\times 500\times 100$ | Yes | No | No
Letters | $20000\times 16$ | No | Yes | No
PIE pose | $2856\times 32\times 32$ | No | Yes | No
PenDigits | $10992\times 16$ | No | Yes | No
USPS | $11000\times 16\times 16$ | No | Yes | No

###  5.1 Compression

As the first application, we use the proposed tensor decomposition as a
compression method and compare tits results with the $t$-SVD. In compression,
only the decomposed factors of the main data are stored, and the data is
reconstructed when it is called. In $\star_{c}$-SVd and $t$-SVd the factors
could be stored in original or frequency spaces as follows:

  * •

Storage in the frequency domain(SFD):Due to properties of these
decomposition’s we show storing factors in frequency space is better than
storing in the main space in terms of storage space and computational
complexity. For simplicity and without lose of generality consider 3-order
tensor $\mathcal{A}\in\mathbb{R}^{I_{1}\times I_{2}\times I_{3}}$. In this
case the storage of factors of double filtered $\star_{c}$-SVD(l,k) is from
order $(I_{1}+I_{3})lk$ and the operations for reconstruction of
$\mathcal{U}_{k}^{l}\star_{c}\mathcal{S}_{k}^{l}\star_{c}\mathcal{U}_{k}^{l^{\sf
T}}$ is from order $I_{1}I_{3}kl+I_{1}I_{3}I_{2}\log(I_{2})$. Because the
factors of the $t$-SVD are complex in the frequency space, the storage space
and operations required to reconstruct the original data are twice more than
$\star_{c}$-SVD method.

  * •

Storage in the main domain(SMD): If one saves the factors of $\star_{c}$-SVD
in the main space, the storage and operations for reconstruction are from
orders $(I_{1}+I_{3})I_{2}k$ and $I_{1}I_{3}kl+2I_{1}I_{3}I_{2}\log(I_{2})$,
respectively, which is more than the first case. In this case the storage and
operations for reconstruction for $t$-SVD are from orders
$(I_{1}+I_{3})I_{2}k$ and $2(I_{1}I_{3}kl+2I_{1}I_{3}I_{2}\log(I_{2}))$,
respectively.

Its clear that storing the factors in the frequency domain is better than the
last case. Also $\star_{c}$-SVD has less storage and reconstruction
computational complexity in comparison with $t$-SVD, in both cases. Also,
mentioned complexities are summarized in Table 2.

Table 2:  Storage Vs operation for reconstruction in Two approaches(Saving in main (SMD) or frequency (SFD) domains) for $t$-SVD (l,k) and $\star_{c}$-SVD(l,k) Saving Approach | Tensor decomposition | Storage | Operations for reconstruction
---|---|---|---
SFD |  $t$-SVD | $2(I_{1}+I_{3})lk$ | 2($I_{1}I_{3}kl+I_{1}I_{3}I_{2}\log(I_{2})$)
$\star_{c}$-SVD | $(I_{1}+I_{3})lk$ | $I_{1}I_{3}kl+I_{1}I_{3}I_{2}\log(I_{2})$
SMD |  $t$-SVD | $(I_{1}+I_{3})I_{2}k$ | $2(I_{1}I_{3}kl+2I_{1}I_{3}I_{2}\log(I_{2}))$
$\star_{c}$-SVD | $(I_{1}+I_{3})I_{2}k$ | $I_{1}I_{3}kl+2I_{1}I_{3}I_{2}\log(I_{2})$

In the following for compression we considered some experiments for
compression. For simplicity we did not used double filtering(removing high
frequencies did not used). So in the following $k$ denotes the truncation of
slices of data in frequency domain. Table 3 reports running time and Frobenius
norm error between exact synthetic data and reconstructed data by $t$-SVD and
$\star_{c}{}\text{-SVD}$ for different $k$.It is obvious that
$\star_{c}{}\text{-SVD}$ has a better approximation and running time.

Table 3: Approximation data by truncated t-SVD and truncated
$\star_{c}{}\text{-SVD}$ approach

Dataset | method | k
---|---|---
SyntheticA | k | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $15$ | $20$ | $25$ | $30$ | $35$
$\star_{c}{}\text{-SVD}$ | $\|.\|_{F}$ | $150.6799$ | $145.8192$ | $141.0347$ | $136.3285$ | $131.7132$ | $127.1617$ | $122.6856$ | $118.2726$ | $105.3673$ | $84.8171$ | $65.1434$ | $45.9772$ | $26.1436$
Time | $0.0080$ | $0.0088$ | $0.0089$ | $0.0089$ | $0.0092$ | $0.0095$ | $0.0095$ | $0.0101$ | $0.0108$ | $0.0125$ | $0.0142$ | $0.0162$ | $0.0176$
t-SVD | $\|.\|_{F}$ | $151.0204$ | $146.1793$ | $141.4365$ | $136.7594$ | $132.1529$ | $127.6142$ | $123.1437$ | $118.7473$ | $105.8626$ | $85.2859$ | $65.6273$ | $46.4386$ | $26.4272$
Time | $0.0107$ | $0.0109$ | $0.0118$ | $0.0132$ | $0.0132$ | $0.01383$ | $0.0146$ | $0.0162$ | $0.0185$ | $0.0226$ | $0.0278$ | $0.0327$ | $0.0392$
SyntheticB | k | $5$ | $10$ | $15$ | $20$ | $25$ | $35$ | $45$ | $55$ | $65$ | $75$ | $85$ | $95$ | $100$
$\star_{c}{}\text{-SVD}$ | $\|.\|_{F}$ | $267.5346$ | $243.5508$ | $221.3552$ | $200.5162$ | $180.8339$ | $144.4158$ | $111.6186$ | $82.3923$ | $56.6329$ | $34.4405$ | $16.3730$ | $3.6567$ | $0.2511$
Time | $0.0124$ | $0.0149$ | $0.0164$ | $0.0181$ | $0.0205$ | $0.0260$ | $0.0299$ | $0.0323$ | $0.0430$ | $0.0394$ | $0.0471$ | $0.0561$ | $0.0562$
t-SVD | $\|.\|_{F}$ | $267.7304$ | $243.8353$ | $221.6783$ | $200.8804$ | $181.2331$ | $144.8921$ | $112.1286$ | $82.9069$ | $57.1755$ | $34.9470$ | $16.8801$ | $3.8276$ | $0.2875$
Time | $0.0229$ | $0.0282$ | $0.0362$ | $0.0341$ | $0.0393$ | $0.0509$ | $0.0624$ | $0.0680$ | $0.0795$ | $0.0936$ | $0.0994$ | $0.1129$ | $0.1150$
SyntheticC | k | $10$ | $15$ | $30$ | $50$ | $80$ | $100$ | $150$ | $200$ | $250$ | $300$ | $350$ | $450$ | $500$
$\star_{c}{}\text{-SVD}$ | $\|.\|_{F}$ | $589.0791$ | $559.4948$ | $474.6183$ | $366.0083$ | $199.2323$ | $36.4333$ | $4.1076e-12$ | $4.1076e-12$ | $4.1076e-12$ | $4.1076e-12$ | $4.1076e-12$ | $4.1076e-12$ | $4.1076e-12$
Time | $0.0506$ | $0.0543$ | $0.0653$ | $0.08732312$ | $0.1087$ | $0.1273$ | $0.1274$ | $0.1232$ | $0.1219$ | $0.1221$ | $0.1223$ | $0.1221$ | $0.1254$
t-SVD | $\|.\|_{F}$ | $589.3193$ | $559.7748$ | $474.9585$ | $366.3456$ | $199.5488$ | $36.7452$ | $3.5690e-11$ | $3.5690e-11$ | $3.5690e-11$ | $3.5690e-11$ | $3.5690e-11$ | $3.5690e-11$ | $3.5690e-11$
Time | $0.1117$ | $0.1207$ | $0.1553$ | $0.1987$ | $0.2686$ | $0.3150$ | $0.3180$ | $0.3159$ | $0.3180$ | $0.3149$ | $0.3157$ | $0.3168$ | $0.3174$
SyntheticD | k | $10$ | $15$ | $30$ | $50$ | $80$ | $100$ | $150$ | $200$ | $250$ | $300$ | $350$ | $450$ | $500$
$\star_{c}{}\text{-SVD}$ | $\|.\|_{F}$ | $589.0791$ | $559.4948$ | $474.6183$ | $366.0083$ | $199.2323$ | $36.4333$ | $4.1076e-12$ | $4.1076e-12$ | $4.1076e-12$ | $4.1076e-12$ | $4.1076e-12$ | $4.1076e-12$ | $4.1076e-12$
Time | $0.0506$ | $0.0543$ | $0.0653$ | $0.08732312$ | $0.1087$ | $0.1273$ | $0.1274$ | $0.1232$ | $0.1219$ | $0.1221$ | $0.1223$ | $0.1221$ | $0.1254$
t-SVD | $\|.\|_{F}$ | $589.3193$ | $559.7748$ | $474.9585$ | $366.3456$ | $199.5488$ | $36.7452$ | $3.5690e-11$ | $3.5690e-11$ | $3.5690e-11$ | $3.5690e-11$ | $3.5690e-11$ | $3.5690e-11$ | $3.5690e-11$
Time | $0.1117$ | $0.1207$ | $0.1553$ | $0.1987$ | $0.2686$ | $0.3150$ | $0.3180$ | $0.3159$ | $0.3180$ | $0.3149$ | $0.3157$ | $0.3168$ | $0.3174$

The experiments shows the the proposed method gives the same approximation in
error with more less time, in comparison with $t$-SVD for different $k$. Since
this table is based on $k$, it can not show the relation between storage and
quality of the approximations, for two methods. So in the next experiment , we
reports in 5 and 4 the quality of reconstruction (PSNR) vs Storage(Bytes) for
two methods applied on real data in Table 1 for different $k$.

Figure 4: (PSNR Vs storage) and ($k$ Vs Time) for $t$-SVD ans $\star_{c}$-SVD,
on some data from Table 1

All experiments show the quality of the proposed $\star_{c}$-SVD over $t$-SVD
method in compression of data.

###  5.2 $\star_{c}{}\text{-SVD}$ as Feature extraction method

In this experiment, we first extracted new features using both the t-SVD and
$\star_{c}{}\text{-SVD}$ approaches, and then we performed clustering and
classification methods on the resulting data. For Clustering method, we
compute $\star_{c}{}\text{-SVD}$ ($\mathcal{A}$,$\mathbf{k_{1}}$),
$\mathbf{k_{1}}:=(k_{1},\cdots,k_{N-1})$ of the dataset $\mathcal{A}\in
R^{I_{1}\times I_{2}\times\dots\times I_{N}}$ to obtain data with reduced
features $\mathcal{A}_{k1}=(\mathcal{V}_{k1}\star_{c}\mathcal{A})^{\sf T}$. we
used Normalized Mutual Information (NMI) criterion to compare the result of
kmeans method on reduced data obtained by t-SVD and $\star_{c}{}\text{-SVD}$
approaches. You can see the details of k-means clustering on different
datasets in Table 4(a).

Figure 5: (PSNR Vs storage) and ($k$ Vs Time) for $t$-SVD ans $\star_{c}$-SVD,
on some data from Table 1

To perform classification, we used the truncated $\star_{c}{}\text{-SVD}$
method, as described in Algorithm 5, where only $k$ columns of each frontal
slice of $\mathcal{U}$ and $\mathcal{V}$ are selected Hao et al. (2013).

Algorithm 5 $\star_{c}{}\text{-Product}$ for classification method

1:$\text{train}\in\mathbb{R}^{I_{1}\times I_{2}\times\cdots\times I_{N}}$,
$\text{test}\in\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$, $k\in\mathbb{R}$,

2:label test

3:$\mathcal{M}\leftarrow$ mean data

4:$\mathcal{A}\leftarrow$ mean deviation from of train data

5:$\mathcal{U}_{k},\mathcal{S}_{k},\mathcal{V}_{k}=\text{tc{-}SVD}(\mathcal{A},k)$

6:$\mathcal{L}_{k}=\mathcal{U}^{T}_{k}\star_{c}\mathcal{A}$

7:$\mathcal{T}\leftarrow\text{test data}-\mathcal{M}$

8:$\mathcal{J}_{k}=\mathcal{U}^{T}_{k}\star_{c}\mathcal{T}$

9:Calculate $\|\mathcal{L}_{k}-\mathcal{J}_{k}^{\bar{i}}\|_{F}$ for
$\bar{i}=i_{1},\cdots,i_{N}$

We report the accuracy of both t-SVD and $\star_{c}{}\text{-SVD}$ for various
datasets and different values of $k$ in Table 4(b). The running times of these
methods on all datasets are shown in Figure 6. Our method demonstrated
significantly lower running times and better accuracy for lower values of $k$
than the t-SVD method, as indicated by Table 4(b) and Figure 6.

(a) Brain MRI

(b) CBCL-face

(c) Coil-100

(d) MNIST

(e) Yale B

Figure 6: The running time of classification based on $t$-SVD and
$\star_{c}$-SVD methods according to differennt reductions number $k$. Table
4: Results of apply methods for clustering and classification tasks

(a) k-means method with best NMI

Dataset Name | decompositin | k1 | k2 | NMI | time
---|---|---|---|---|---
Letters | tSVD | 3 | 2 | 0.377755 | 1.65931
tcSVD | 3 | 3 | 0.398108 | 1.10069
MNIST | tSVD | 5 | 21 | 0.416287 | 3.86368
tcSVD | 6 | 26 | 0.371089 | 2.06664
PIE_pose | tSVD | 2 | 29 | 0.909975 | 0.208724
tcSVD | 22 | 20 | 0.913545 | 0.208813
PenDigits | tSVD | 3 | 3 | 0.627107 | 1.14224
tcSVD | 3 | 2 | 0.644992 | 0.825843
USPS | tSVD | 5 | 13 | 0.370718 | 0.697890
tcSVD | 7 | 14 | 0.344233 | 0.343368

(b) Accuracy of classification on different dataset

Data Set | method | k | accuracy score | time
---|---|---|---|---
Brain MRI | tSVD | 49 | 0.803922 | 2.544043
tcSVD | 62 | 0.803922 | 1.235369
CBCL-face | tSVD | 18 | 0.965357 | 496.210606
tcSVD | 18 | 0.965357 | 146.935816
Coil-100 | tSVD | 2 | 0.983333 | 25.173541
tcSVD | 2 | 0.984722 | 8.707815
MNIST | tSVD | 8 | 0.972821 | 2146.879512
tcSVD | 9 | 0.972107 | 831.023561
Yale | tSVD | 41 | 0.772257 | 67.171898
tcSVD | 47 | 0.772257 | 80.1
Cifar | tSVD | 9 | 0.62 | 67.171898
tcSVD | 8 | 0.63 | 28.30.598
3D-MNIST | tSVD |  |  |
tcSVD |  |  |

##  6 Conclusion

In this paper, we presented a new tensor-tensor product,
$\star_{c}{}\text{-SVD}$, which is based on the block convolution operation
between two tensors. We demonstrated that this product provides a general
tensor decomposition method that extends the SVD decomposition to arbitrary
tensors, and we showed that the coefficient matrix in our linear system can be
diagonalized by the Discrete Cosine Transform (DCT), which is faster than the
Fast Fourier Transform. Our experimental results on both synthetic random
tensors and well-known datasets showed that our proposed method is faster and
more accurate than the traditional t-SVD method. Our $\star_{c}{}\text{-SVD}$
product has potential applications in various fields such as image processing,
signal processing, and machine learning. Future research can explore more
efficient algorithms to compute the $\star_{c}{}\text{-SVD}$ decomposition and
investigate its applications in other areas.

## References

  * Ai et al. (2018) Jianhang Ai, Shuli Ma, Huiqian Du, and Liping Fang.  Dynamic mri reconstruction using tensor-svd.  In _2018 14th IEEE International Conference on Signal Processing (ICSP)_ , pages 1114–1118. IEEE, 2018.
  * Bader and Kolda (2006) Brett W Bader and Tamara G Kolda.  Algorithm 862: Matlab tensor classes for fast algorithm prototyping.  _ACM Transactions on Mathematical Software (TOMS)_ , 32(4):635–653, 2006.
  * Bahri et al. (2018) Mehdi Bahri, Yannis Panagakis, and Stefanos Zafeiriou.  Robust kronecker component analysis.  _IEEE transactions on pattern analysis and machine intelligence_ , 41(10):2365–2379, 2018.
  * Bi and Wang (2019) Xiaojun Bi and Haibo Wang.  Early alzheimer’s disease diagnosis based on eeg spectral images using deep learning.  _Neural Networks_ , 114:119–135, 2019.
  * Cai et al. (2006) Deng Cai, Xiaofei He, Ji-Rong Wen, Jiawei Han, and Wei-Ying Ma.  Support tensor machines for text categorization.  Technical report, 2006.
  * Chakrabarty (2019) Navoneel Chakrabarty.  Brain MRI Images for Brain Tumor Detection.  https://www.kaggle.com/datasets/navoneel/brain-mri-images-for-brain-tumor-detection, 2019\.
  * Fan et al. (2020) Jicong Fan, Lijun Ding, Chengrun Yang, and Madeleine Udell.  Low-rank tensor recovery with euclidean-norm-induced schatten-p quasi-norm regularization.  _arXiv preprint arXiv:2012.03436_ , 2020.
  * Goodfellow et al. (2016) Ian J. Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep Learning_.  MIT Press, Cambridge, MA, USA, 2016.  http://www.deeplearningbook.org.
  * Han and Kan (2019) Yue Han and Jiangming Kan.  Blind color-image deblurring based on color image gradients.  _Signal Processing_ , 155:14–24, 2019.
  * Hao et al. (2013) Ning Hao, Misha E Kilmer, Karen Braman, and Randy C Hoover.  Facial recognition using tensor-tensor decompositions.  _SIAM Journal on Imaging Sciences_ , 6(1):437–463, 2013.
  * Kilmer and Martin (2011) Misha E Kilmer and Carla D Martin.  Factorization strategies for third-order tensors.  _Linear Algebra and its Applications_ , 435(3):641–658, 2011.
  * Kolda and Bader (2009) Tamara G Kolda and Brett W Bader.  Tensor decompositions and applications.  _SIAM review_ , 51(3):455–500, 2009.
  * Liang (2007) Faming Liang.  Use of svd-based probit transformation in clustering gene expression profiles.  _Computational Statistics & Data Analysis_, 51(12):6355–6366, 2007.
  * Liu et al. (2010) Yang Liu, Yan Liu, and Keith CC Chan.  Tensor distance based multilinear locality-preserved maximum information embedding.  _IEEE Transactions on neural networks_ , 21(11):1848–1854, 2010.
  * Lou and Cheung (2019) Jian Lou and Yiu-Ming Cheung.  Robust low-rank tensor minimization via a new tensor spectral $k$-support norm.  _IEEE Transactions on Image Processing_ , 29:2314–2327, 2019.
  * Lu et al. (2019) Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, and Shuicheng Yan.  Tensor robust principal component analysis with a new tensor nuclear norm.  _IEEE transactions on pattern analysis and machine intelligence_ , 42(4):925–938, 2019.
  * Lu et al. (2008) Haiping Lu, Konstantinos N Plataniotis, and Anastasios N Venetsanopoulos.  Mpca: Multilinear principal component analysis of tensor objects.  _IEEE transactions on Neural Networks_ , 19(1):18–39, 2008.
  * Martin et al. (2013) Carla D Martin, Richard Shafer, and Betsy LaRue.  An order-p tensor factorization with applications in imaging.  _SIAM Journal on Scientific Computing_ , 35(1):A474–A490, 2013.
  * Mohan et al. (2020) K Aditya Mohan, Robert M Panas, and Jefferson A Cuadra.  Saber: A systems approach to blur estimation and reduction in x-ray imaging.  _IEEE Transactions on Image Processing_ , 29:7751–7764, 2020.
  * Nene et al. (1988) S Nene, S Nayar, Hiroshi Murase, et al.  Columbia object image library (coil 100) 1996.  _Columbia University_ , 1(2):3, 1988.
  * Ng et al. (1999) Michael K Ng, Raymond H Chan, and Wun-Cheung Tang.  A fast algorithm for deblurring models with neumann boundary conditions.  _SIAM Journal on Scientific Computing_ , 21(3):851–866, 1999.
  * Noroozi and Rezghi (2020) Ali Noroozi and Mansoor Rezghi.  A tensor-based framework for rs-fmri classification and functional connectivity construction.  _Frontiers in Neuroinformatics_ , 14, 2020.
  * Rezghi (2017) Mansoor Rezghi.  A novel fast tensor-based preconditioner for image restoration.  _IEEE Transactions on Image Processing_ , 26(9):4499–4508, 2017.
  * Rezghi and Amirmazlaghani (2019) Mansoor Rezghi and Maryam Amirmazlaghani.  Even-order toeplitz tensor: framework for multidimensional structured linear systems.  _Computational and Applied Mathematics_ , 38(3):1–24, 2019.
  * Rezghi and Elden (2011) Mansoor Rezghi and Lars Elden.  Diagonalization of tensors with circulant structure.  _Linear Algebra and its Applications_ , 435(3):422–447, 2011.
  * Rezghi et al. (2014) Mansoor Rezghi, S Mohammad Hosseini, and Lars Elden.  Best kronecker product approximation of the blurring operator in three dimensional image restoration problems.  _SIAM Journal on Matrix Analysis and Applications_ , 35(3):1086–1104, 2014.
  * Selvan and Ramakrishnan (2007) Srinivasan Selvan and Srinivasan Ramakrishnan.  Svd-based modeling for image texture classification using wavelet transformation.  _IEEE transactions on image processing_ , 16(11):2688–2696, 2007.
  * Shen and Sethi (1996) Bo Shen and Ishwar K Sethi.  Convolution-based edge detection for image/video in block dct domain.  _Journal of Visual Communication and Image Representation_ , 7(4):411–423, 1996.
  * Wang et al. (2020) Andong Wang, Zhong Jin, and Guoqing Tang.  Robust tensor decomposition via t-svd: Near-optimal statistical guarantee and scalable algorithms.  _Signal Processing_ , 167:107319, 2020.
  * Wang and Zhu (2017) Yongchang Wang and Ligu Zhu.  Research and implementation of svd in machine learning.  In _2017 IEEE/ACIS 16th International Conference on Computer and Information Science (ICIS)_ , pages 471–475. IEEE, 2017.
  * Wen et al. (2018) Changbao Wen, Pengli Liu, Wenbo Ma, Zhirong Jian, Changheng Lv, Jitong Hong, and Xiaowen Shi.  Edge detection with feature re-extraction deep convolutional neural network.  _Journal of Visual Communication and Image Representation_ , 57:84–90, 2018.
  * Wu et al. (2022) Zhebin Wu, Lin Shu, Ziyue Xu, Yaomin Chang, Chuan Chen, and Zibin Zheng.  Robust tensor graph convolutional networks via t-svd based graph augmentation.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , pages 2090–2099, 2022.
  * Xie et al. (2017) Qi Xie, Qian Zhao, Deyu Meng, and Zongben Xu.  Kronecker-basis-representation based tensor sparsity and its applications to tensor recovery.  _IEEE transactions on pattern analysis and machine intelligence_ , 40(8):1888–1902, 2017.
  * Zaki et al. (2014) Mohammed J Zaki, Wagner Meira Jr, and Wagner Meira.  _Data mining and analysis: fundamental concepts and algorithms_.  Cambridge University Press, 2014.
  * Zhang et al. (2019) Fangyan Zhang, Ting Luo, Gangyi Jiang, Mei Yu, Haiyong Xu, and Wujie Zhou.  A novel robust color image watermarking method using rgb correlations.  _Multimedia Tools and Applications_ , 78(14):20133–20155, 2019.
  * Zhang and Aeron (2016) Zemin Zhang and Shuchin Aeron.  Exact tensor completion using t-svd.  _IEEE Transactions on Signal Processing_ , 65(6):1511–1526, 2016.