# Spectral computation with third-order tensors
using the t-product

A. El Hachimi22footnotemark: 2 Mohammed VI Polytechnic University, Green City,
Morocco. K. Jbilou11footnotemark: 1 Université du Littoral Cote d’Opale, LMPA,
50 rue F. Buisson, 62228 Calais-Cedex, France. A. Ratnani11footnotemark: 1 L.
Reichel Department of Mathematical Sciences, Kent State University, Kent, OH
44242, USA.

###### Abstract

The tensor t-product, introduced by Kilmer and Martin [26], is a powerful tool
for the analysis of and computation with third-order tensors. This paper
introduces eigentubes and eigenslices of third-order tensors under the
t-product. The eigentubes and eigenslices are analogues of eigenvalues and
eigenvectors for matrices. Properties of eigentubes and eigenslices are
investigated and numerical methods for their computation are described. The
methods include the tensor power method, tensor subspace iteration, and the
tensor QR algorithm. Computed examples illustrate the performance of these
methods.

###### keywords:

tensor, t-product, eigentube, eigenslice, tensor power method, tensor subspace
iteration, tensor QR algorithm.

##  1 Introduction

Tensors are high-dimensional generalizations of matrices. They find many
applications in science and engineering including in image processing, data
mining, computer vision, network analysis, and the solution of partial
differential equations; see [2, 3, 4, 5, 6, 7, 8, 13, 19, 21, 30] and
references therein. Several different tensor products have been proposed in
the literature. The $n$-mode product is one of the most commonly used
products; it defines the product of a tensor and a matrix of appropriate
sizes; see [3, 14]. The CP and Tucker tensor decompositions use this product;
see [3, 9]. The oldest tensor product is probably the Einstein product [11];
it has recently been applied to color image and video processing [17]. The
newest tensor product is the t-product for third-order tensors, which was
proposed by Kilmer et al. [25, 26]. This product has found many applications
and has been generalized in several ways; see [1, 2, 6, 7, 15, 16, 18, 20, 28,
30, 31]. The t-product allows natural generalizations of many matrix
factorizations including the singular value decomposition, and the QR and
Choleski factorizations to third-order tensors; see [25, 26, 32].

Several notions of eigenvalues for a tensor have been described in the
literature. They include the C-eigenvalues, H-eigenvalues, and Z-eigenvalues;
see [12, 29]. The definitions depend on the tensor product used. The
eigenvalues in these definitions are scalars. We will use the t-product and
introduce eigentubes and eigenslices, which are analogues for third-order
tensors of eigenvalues and eigenvectors for matrices, respectively. It is the
purpose of this paper to discuss some properties of eigentubes and
eigenslices, and describe algorithms for their computation.

The organization of this paper is as follows: Sections 2 reviews properties of
the t-product, Section 3 describes some tensor decompositions, and Section 4
discusses some properties of eigentubes and eigenslices. Numerical methods for
computing a few or all eigentubes and associated eigenslices of a tensor are
presented in Section 5. A few computed examples are presented in Section 6,
and Section 7 contains concluding remarks.

##  2 The t-product for third order tensors

This section reviews definitions and results by Kilmer et al. [25, 26] and
uses notation from there, as well as from Kolda and Bader [3]. Consider the
third-order tensor $\mathscr{A}=[\mathscr{A}_{i,j,k}]\in\mathbb{C}^{\ell\times
p\times n}$. A _slice_ of $\mathscr{A}$ is a 2D section obtained by fixing any
one of the indices. Using MATLAB-type notation, $\mathscr{A}_{i,:,:}$,
$\mathscr{A}_{:,j,:}$, and $\mathscr{A}_{:,:,k}$ stand for the $i$th
horizontal, $j$th lateral, and $k$th frontal slices of $\mathscr{A}$,
respectively. We also denote the $j$th lateral slice by
$\vec{\mathscr{A}}_{j}$. It is a tensor and is referred to as a _tensor
column_. Sometimes it is convenient to identify $\vec{\mathscr{A}}_{j}$ with a
matrix. The $k$th frontal slice, $\mathscr{A}_{:,:,k}$ is also denoted by
$\mathscr{A}^{(k)}$ and is a matrix. A _fiber_ of a third order tensor
$\mathscr{A}$ is a 1D section obtained by fixing any two of the indices. Thus,
$\mathscr{A}_{:,j,k}$, $\mathscr{A}_{i,:,k}$, and $\mathscr{A}_{i,j,:}$ denote
mode-1, mode-2, and mode-3 fibers (tubes), respectively. We will use the
notation $\mathbb{K}^{\ell\times p}_{n}=\mathbb{C}^{\ell\times p\times n}$ for
the space of third-order tensors,
$\mathbb{K}^{\ell}_{n}=\mathbb{C}^{\ell\times 1\times n}$ stands for the space
of lateral slices, and $\mathbb{K}_{n}=\mathbb{C}^{1\times 1\times n}$ denotes
the space of tubes. Many of the tensors considered will be _square_ , i.e.,
$\ell=p$.

The inner product of two third-order tensors
$\mathscr{A},\mathscr{B}\in\mathbb{K}^{\ell\times p}_{n}$ is given by

$\langle\mathscr{A},\mathscr{B}\rangle=\sum_{i,j,k=1}^{\ell,p,n}\mathscr{A}_{i,j,k}\bar{\mathscr{B}}_{i,j,k},$

where the bar denotes complex conjugation, and the Frobenius norm of
$\mathscr{A}$ is defined as

$\left\|\mathscr{A}\right\|_{F}=\langle\mathscr{A},\mathscr{A}\rangle^{1/2}.$

We note that a third-order tensor $\mathscr{A}\in\mathbb{K}^{\ell\times
p}_{n}$ can be represented as

$\mathscr{A}=\left[\vec{\mathscr{A}}_{1},\vec{\mathscr{A}}_{2},\ldots,\vec{\mathscr{A}}_{p}\right].$

The Discrete Fourier Transform (DFT) is helpful for the efficient evaluation
of the t-product of two tensors. The DFT of a vector $v\in\mathbb{C}^{n}$ is
given by

$\widehat{v}=F_{n}v\in\mathbb{C}^{n},$ (1)

where $F_{n}$ denotes the DFT matrix defined as

$F_{n}=\left[\left(e^{\frac{2i\pi}{n}}\right)^{(k-1)(j-1)}\right]_{k=1:n,j=1:n}\in\mathbb{C}^{n\times
n}.$

While the matrix $F_{n}$ is not unitary, the scaled matrix $F_{n}/\sqrt{n}$
is. The computation of the vector $\widehat{v}$ by straightforward evaluation
of the matrix-vector product in the right-hand side of (1) requires $O(n^{2})$
arithmetic floating point operations (flops). It is well known that this flop
count is reduced to $O(n\log(n))$ when using the fast Fourier transform (FFT).
This can be done in MATLAB with the command $\widehat{v}={\tt fft}(v)$.

Let $\widehat{\mathscr{A}}\in\mathbb{K}^{\ell\times p}_{n}$ denote the tensor
obtained by applying the DFT along the third dimension of the tensor
$\mathscr{A}\in\mathbb{R}^{\ell\times p\times n}$. Thus, we evaluate the DFT
of each tube of $\mathscr{A}$; this can be done in MATLAB with the command

$\widehat{\mathscr{A}}={\tt fft}\left(\mathscr{A},[\,],3\right).$

To transform $\widehat{\mathscr{A}}$ back to $\mathscr{A}$, we use the MATLAB
command

$\mathscr{A}={\tt ifft}\left(\widehat{\mathscr{A}},[\,],3\right).$

For $\mathscr{A},\mathscr{B}\in\mathbb{K}^{\ell\times p}_{n}$, we have

$\left\|\mathscr{A}\right\|_{F}=\dfrac{1}{\sqrt{n}}\|\widehat{\mathscr{A}}\|_{F},\quad\langle\mathscr{A},\mathscr{B}\rangle=\dfrac{1}{n}\langle\widehat{\mathscr{A}},\widehat{\mathscr{B}}\rangle.$

The following definitions are required below. For
$\mathscr{A}\in\mathbb{K}^{\ell\times p}_{n}$, we define the associated block
diagonal matrix

${\tt bdiag}\left(\mathscr{A}\right)=\begin{pmatrix}\mathscr{A}^{(1)}&&&&\\\
&\mathscr{A}^{(2)}&&&\\\ &&\mathscr{A}^{(3)}&&\\\ &&&\ddots&\\\
&&&&\mathscr{A}^{(n)}\end{pmatrix}\in\mathbb{C}^{\ell n\times pn}.$

Also introduce the block circulant matrix

${\tt
bcirc}\left(\mathscr{A}\right)=\begin{pmatrix}\mathscr{A}^{(1)}&\mathscr{A}^{(n)}&\mathscr{A}^{(n-1)}&\dots&\mathscr{A}^{(2)}\\\
\mathscr{A}^{(2)}&\mathscr{A}^{(1)}&\mathscr{A}^{(n)}&\dots&\mathscr{A}^{(3)}\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\
\mathscr{A}^{(n-1)}&\mathscr{A}^{(n-2)}&\dots&\mathscr{A}^{(1)}&\mathscr{A}^{(n)}\\\
\mathscr{A}^{(n)}&\mathscr{A}^{(n-1)}&\dots&\mathscr{A}^{(2)}&\mathscr{A}^{(1)}\end{pmatrix}\in\mathbb{C}^{\ell
n\times pn}.$

The operators ${\tt unfold}$ and ${\tt fold}$ are defined as

${\tt unfold}\left(\mathscr{A}\right)=\begin{pmatrix}\mathscr{A}^{(1)}\\\
\mathscr{A}^{(2)}\\\ \vdots\\\
\mathscr{A}^{(n)}\end{pmatrix}\in\mathbb{C}^{\ell n\times
p}\text{\leavevmode\nobreak\ \leavevmode\nobreak\ and\leavevmode\nobreak\
\leavevmode\nobreak\ }{\tt fold}({\tt
unfold}\left(\mathscr{A}\right))=\mathscr{A}.$

Thus, ${\tt unfold}$ transforms the tensor
$\mathscr{A}\in\mathbb{K}^{p\times\ell}_{n}$ into a matrix and ${\tt fold}$ is
the inverse operator.

A block circulant matrix can be block diagonalized by using the DFT. Kilmer et
al. [25] use this property to establish that for
$\mathscr{A}\in\mathbb{K}^{\ell\times p}_{n}$, we have

$\left(F_{n}\otimes I_{\ell}\right){\tt
bcirc}\left(\mathscr{A}\right)\left(F_{n}^{H}\otimes I_{p}\right)={\tt
bdiag}(\widehat{\mathscr{A}}),$

where $\otimes$ stands for the Kronecker product. The following definition is
due to Kilmer et al. [25].

######  Definition 1.

Let $\mathscr{A}\in\mathbb{K}^{\ell\times q}_{n}$ and
$\mathscr{B}\in\mathbb{K}^{q\times p}_{n}$. Then the t-product of
$\mathscr{A}$ and $\mathscr{B}$ is defined as

$\mathscr{A}*\mathscr{B}={\tt fold}\left({\tt
bcirc}\left(\mathscr{A}\right){\tt
unfold}\left(\mathscr{B}\right)\right)\in\mathbb{K}^{\ell\times p}_{n}.$ (2)

The evaluation of the t-product by using the above definition is quite costly
unless the tensors $\mathscr{A}$ and $\mathscr{B}$ are very sparse. Kilmer et
al. [25] therefore propose to evaluate the t-product (2) with the aid of the
FFT. The following result makes this possible.

######  Proposition 1.

([25]) Let $\mathscr{A}\in\mathbb{K}^{\ell\times q}_{n}$ and
$\mathscr{B}\in\mathbb{K}^{q\times p}_{n}$. Then the tensor
$\mathscr{C}=\mathscr{A}*\mathscr{B}$ can be determined from

${\tt bdiag}(\widehat{\mathscr{C}})={\tt bdiag}(\widehat{\mathscr{A}})\,{\tt
bdiag}(\widehat{\mathscr{B}}).$

We briefly consider the special case of evaluating the t-product of real
tensors $\mathscr{A}\in\mathbb{R}^{\ell\times q\times n}$ and
$\mathscr{B}\in\mathbb{R}^{q\times p\times n}$. It is well known that for
$v\in\mathbb{R}^{n}$, the vector $\widehat{v}$ satisfies

$\widehat{v}_{1}\in\mathbb{R}\mbox{\leavevmode\nobreak\ \leavevmode\nobreak\
and\leavevmode\nobreak\ \leavevmode\nobreak\ }{\tt
conj}\left(\widehat{v}_{j}\right)=\widehat{v}_{n-i+1}\mbox{\leavevmode\nobreak\
\leavevmode\nobreak\ for\leavevmode\nobreak\ \leavevmode\nobreak\
}i=1,\ldots,\left[\dfrac{n+1}{2}\right],$ (3)

where ${\tt conj}$ denotes the complex conjugation operator and
$\left[(n+1)/2\right]$ stands for the integer part of $(n+1)/2$. A vector that
satisfies (3) is said to be conjugate-even. Moreover, if the $n$-vector
$\tilde{v}$ is real and conjugate-even, then $v=F_{n}^{H}\tilde{v}$ is a real
conjugate-even vector, where the superscript H denotes transposition and
complex conjugation; see, e.g., [24, Chapter 15] for many properties of the
DFT, as well as [33].

Let the operator ${\tt vec}$ denote the vectorization of a tube. We say that
the tube $\bm{a}\in\mathbb{C}^{n}$ is real conjugate-even, if the vector
$a={\tt vec}(\bm{a})$ is real conjugate-even. By exploiting the symmetry of
the DFT, it follows that for real third-order tensors
$\mathscr{A}\in\mathbb{R}^{\ell\times p\times n}$, we have

$\widehat{\mathscr{A}}^{(1)}\in\mathbb{R}^{\ell\times
p}\mbox{\leavevmode\nobreak\ \leavevmode\nobreak\ and\leavevmode\nobreak\
\leavevmode\nobreak\
}\widehat{\mathscr{A}}^{(i)}=\widehat{\mathscr{A}}^{(n-i+2)},\;i=2,3,\ldots,\left[\dfrac{n-1}{2}\right].$

Algorithm 1 exploits the symmetry properties of the DFT when evaluating the
t-product of real tensors.

Algorithm 1 t-product of real third-order tensors

Input: $\mathscr{A}\in\mathbb{R}^{\ell\times q\times n}$,
$\mathscr{B}\in\mathbb{R}^{q\times p\times n}$.
Output: $\mathscr{C}=\mathscr{A}*\mathscr{B}\in\mathbb{R}^{\ell\times p\times
n}$.

1: Compute $\widehat{\mathscr{A}}={\tt fft}(\mathscr{A},[\,],3)$ and
$\widehat{\mathscr{B}}={\tt fft}(\mathscr{B},[\,],3)$

2: for $i=1,2\;\text{to}\;\left[\dfrac{n+1}{2}\right]$ do

3:
$\widehat{\mathscr{C}}^{(i)}=\widehat{\mathscr{A}}^{(i)}\widehat{\mathscr{B}}^{(i)}$

4: end for

5: for $i=\left[\dfrac{n+1}{2}\right]+1\;\text{to}\;n$ do

6: $\widehat{\mathscr{C}}^{(i)}={\tt conj}(\widehat{\mathscr{C}}^{(n-i+2)})$

7: end for

8: Compute $\mathscr{C}={\tt ifft}\left(\widehat{\mathscr{C}},[\,],3\right)$

We recall the main properties of the t-product that will be used in the
sequel. Proofs can be found in [25].

######  Proposition 2.

  1. (i)

The identity tensor under the t-product,
$\mathscr{I}_{\ell}\in\mathbb{K}^{\ell\times\ell}_{n}$, has the first frontal
slice equal to the identity matrix and the remaining frontal slices are zero
matrices.

  2. (ii)

The canonical lateral slice under the t-product,
$\vec{\mathscr{E}}_{j}\in\mathbb{K}^{\ell}_{n}$, where $1\leq j\leq\ell$, has
the $(j,1,1)$th entry equal to one, and all other entries zero.

  3. (iii)

The unit tube, $\bm{e}\in\mathbb{K}_{n}$, has the entry $(1,1,1)$ equal to
one, and all other entries zero.

  4. (iv)

The conjugate transpose, $\mathscr{A}^{H}\in\mathbb{K}^{p\times\ell}_{n}$, of
the tensor $\mathscr{A}\in\mathbb{K}^{\ell\times p}_{n}$ is obtained by first
transposing and conjugating each one of the frontal slices of $\mathscr{A}$,
and then reversing the order of the conjugated transposed frontal slices 2
through $n$. The tensor conjugate transpose has similar properties as the
matrix transpose. For instance, if $\mathscr{A}$ and $\mathscr{B}$ are tensors
such that $\mathscr{A}*\mathscr{B}$ and $\mathscr{B}^{H}*\mathscr{A}^{H}$ are
defined, then $(\mathscr{A}*\mathscr{B})^{H}=\mathscr{B}^{H}*\mathscr{A}^{H}$.

  5. (v)

A tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ is said to be normal if
$\mathscr{A}^{H}*\mathscr{A}=\mathscr{A}*\mathscr{A}^{H}$.

  6. (vi)

A third order tensor is said to be f-diagonal if its frontal slices in the
Fourier domain are diagonal matrices.

  7. (vii)

A third order tensor is said to be f-upper-triangular if its frontal slices in
the Fourier domain are upper triangular matrices.

  8. (viii)

The tensor $\mathscr{A}\in\mathbb{K}^{\ell\times\ell}_{n}$ is said to be
f-Hermitian if $\mathscr{A}^{H}=\mathscr{A}$. In order for $\mathscr{A}$ to be
f-Hermitian each frontal slice of $\widehat{\mathscr{A}}$ has to be a
Hermitian matrix.

  9. (ix)

A tensor $\mathscr{Q}\in\mathbb{K}^{\ell\times\ell}_{n}$ is said to be
f-orthogonal (or f-unitary) if
$\mathscr{Q}^{H}*\mathscr{Q}=\mathscr{Q}*\mathscr{Q}^{H}=\mathscr{I}_{\ell}$.

  10. (x)

A tensor $\mathscr{A}\in\mathbb{K}^{\ell\times\ell}_{n}$ is invertible if
there is a tensor $\mathscr{A}^{-1}\in\mathbb{K}^{\ell\times\ell}_{n}$ such
that
$\mathscr{A}^{-1}*\mathscr{A}=\mathscr{A}*\mathscr{A}^{-1}=\mathscr{I}_{\ell}$.
This definition implies that a third order tensor is invertible under the
t-product if and only if each frontal slice in the Fourier domain is
invertible.

  11. (xi)

Let $p$ be a positive integer and
$\mathscr{A}\in\mathbb{K}^{\ell\times\ell}_{n}$. Then
$\mathscr{A}^{p}=\mathscr{A}*\ldots*\mathscr{A}$. We define
$\mathscr{A}^{0}=\mathscr{I}_{\ell}$.

  12. (xii)

Let $\mathscr{A}\in\mathbb{K}^{\ell\times p}_{n}$. Then
$\mathscr{A}\not\equiv\textbf{0}$ means that $\widehat{\mathscr{A}}^{(i)}\neq
0$ for every $i=1,2,\ldots,n$.

In the following we will require the t-product of two tubes. This operation
has been defined in [25]. The definition suggests how the quotient of two
tubes can be defined.

######  Definition 3.

Let $\bm{a},\bm{b}\in\mathbb{K}_{n}$. Then

$\bm{a}*\bm{b}={\tt ifft}(\widehat{\bm{a}}\circ\widehat{\bm{b}},[],3),$

where $\circ$ denotes the entry-wise product of the vectors and, as usual,
$\widehat{\bm{a}}$ and $\widehat{\bm{b}}$ stand for the Fourier transform of
the tubes $\bm{a}$ and $\bm{b}$, respectively. Note that the tube product
commutes.

Let, in addition, all entries of $\widehat{\bm{b}}$ be nonvanishing. Then we
can define

$\frac{\bm{a}}{\bm{b}}={\tt ifft}(\widehat{\bm{a}}\div\widehat{\bm{b}},[],3),$

where $\div$ denotes entry-wise division.

We also will need to evaluate the product of a tensor and a tube, as well as
the quotient of a tensor and a tube.

######  Definition 4.

Let $\mathscr{A}\in\mathbb{K}^{\ell\times p}_{n}$ and let
$\bm{b}\in\mathbb{K}_{n}$. With the usual notation, we define the product
$\mathscr{C}=\mathscr{A}*\bm{b}\in\mathbb{K}^{\ell\times p}_{n}$ as

$\mathscr{C}={\tt ifft}(\widehat{\mathscr{C}},[],3),\mbox{\leavevmode\nobreak\
\leavevmode\nobreak\ where\leavevmode\nobreak\ \leavevmode\nobreak\
}\widehat{\mathscr{C}}^{(i)}=\widehat{\mathscr{A}}^{(i)}\widehat{\bm{b}}^{(i)},\quad
i=1,2,\ldots,n.$

We note that

$\mathscr{A}*\bm{b}=\bm{b}*\mathscr{A}.$ (4)

If, in addition, all entries of $\widehat{\bm{b}}$ are nonvanishing, then we
define the quotient $\mathscr{C}=\mathscr{A}/\bm{b}\in\mathbb{K}^{\ell\times
p}_{n}$ by $\mathscr{C}={\tt ifft}(\widehat{\mathscr{C}},[],3)$, where

$\widehat{\mathscr{C}}^{(i)}=\widehat{\mathscr{A}}^{(i)}/\widehat{\bm{b}}^{(i)},\quad
i=1,2,\dots,n.$

We recall that the lateral slices
$\vec{\mathscr{A}}_{j}\in\mathbb{K}^{\ell}_{n}$, $j=1,2,\ldots,p$, of the
tensor $\mathscr{A}\in\mathbb{K}^{\ell\times p}_{n}$ are third-order tensors.
Therefore, it follows from (4) that for any tube $\bm{b}\in\mathbb{K}_{n}$,

$\vec{\mathscr{A}}_{j}*\bm{b}=\bm{b}*\vec{\mathscr{A}}_{j}.$ (5)

We will use this property below.

It is convenient to introduce the following space.

######  Definition 5.

Let
$\mathbb{G}=\\{\vec{\mathscr{A}}_{1},\vec{\mathscr{A}}_{2},\ldots,\vec{\mathscr{A}}_{p}\\}\subset\mathbb{K}^{\ell}_{n}$
be the set of lateral slices of the tensor
$\mathscr{A}\in\mathbb{K}^{\ell\times p}_{n}$. Then the set of the t-linear
combinations of these slices is a lateral slice space given by

$\displaystyle\operatorname*{\text{span}_{t}}\left\\{\mathbb{G}\right\\}$
$\displaystyle=$
$\displaystyle\operatorname*{\text{span}_{t}}\left\\{\vec{\mathscr{A}}_{1},\vec{\mathscr{A}}_{2},\ldots,\vec{\mathscr{A}}_{p}\right\\}$
$\displaystyle=$
$\displaystyle\left\\{\vec{\mathscr{C}}\in\mathbb{K}^{\ell}_{n}:\leavevmode\nobreak\
\vec{\mathscr{C}}=\sum_{i=1}^{p}\vec{\mathscr{A}}_{i}*\bm{b}_{i},\mbox{\leavevmode\nobreak\
\leavevmode\nobreak\ where\leavevmode\nobreak\ \leavevmode\nobreak\
}\bm{b}_{i}\in\mathbb{K}^{n},\leavevmode\nobreak\ i=1,2,\ldots,p\right\\}.$

##  3 Tensor factorizations

Many matrix factorizations can be extended to third-order tensors under the
t-product. We will review two available factorizations and introduce a new
one, that will be used in the sequel.

######  Theorem 6.

(t-SVD) ([25]) Let $\mathscr{A}\in\mathbb{K}^{\ell\times p}_{n}$. Then, using
the t-product, $\mathscr{A}$ can be factored into three third-order tensors,

$\mathscr{A}=\mathscr{U}*\mathscr{S}*\mathscr{V}^{H},$ (6)

where $\mathscr{U}\in\mathbb{K}^{\ell\times\ell}_{n}$ and
$\mathscr{V}\in\mathbb{K}^{p\times p}_{n}$ are f-orthogonal tensors and
$\mathscr{S}\in\mathbb{K}^{\ell\times p}_{n}$ is an f-diagonal tensor. We
refer to the factorization (6) as the _singular tube decomposition_.

The tubes $\bm{s}_{i}=\mathscr{S}_{i,i,:}$ for $i=1,2,\ldots,\min\\{\ell,p\\}$
of the tensor $\mathscr{S}$ are referred to as singular tubes, whereas
$\vec{\mathscr{U}}_{j}=\mathscr{U}_{:,j,:}$ for $j=1,2,\ldots,\ell$ and
$\vec{\mathscr{V}}_{k}=\mathscr{V}_{:,k,:}$ for $k=1,2,\ldots,p$ are called
left and right singular (lateral) slices, respectively. The norm of the
singular tubes $\bm{s}_{i}$, given by
$\sigma_{i}=\left\|\bm{s}_{i}\right\|_{F}$ for
$i=1,2,\ldots,\min\\{\ell,p\\}$, are referred to as the singular values of the
tensor $\mathscr{A}$; they are enumerated in decreasing order. The singular
triplets
$\\{\bm{s}_{i},\vec{\mathscr{U}}_{i},\vec{\mathscr{V}}_{i}\\}_{i=1}^{\min\\{\ell,p\\}}$
satisfy

$\mathscr{A}*\vec{\mathscr{V}}_{i}=\vec{\mathscr{U}}_{i}*\bm{s}_{i},\leavevmode\nobreak\
\leavevmode\nobreak\
\mathscr{A}^{H}*\vec{\mathscr{U}}_{i}=\vec{\mathscr{V}}_{i}*\bm{s}_{i},\leavevmode\nobreak\
\leavevmode\nobreak\ 1=1,2,\ldots,\min\\{\ell,p\\}.$

We note that equation (6) can be written as

$\mathscr{A}=\sum_{i=1}^{\min\\{\ell,p\\}}\vec{\mathscr{U}}_{i}*\bm{s}_{i}*\vec{\mathscr{V}}_{i}^{H}=\sum_{i=1}^{\min\\{\ell,p\\}}\bm{s}_{i}*\vec{\mathscr{U}}_{i}*\vec{\mathscr{V}}_{i}^{H},$

where the last equality follows from (5).

Kilmer et al. [25] also describe the t-QR factorization of a tensor
$\mathscr{A}\in\mathbb{K}^{\ell\times p}_{n}$,

$\mathscr{A}=\mathscr{Q}*\mathscr{R},$

where $\mathscr{Q}\in\mathbb{K}^{\ell\times\ell}_{n}$ is an f-orthogonal
tensor and $\mathscr{R}\in\mathbb{K}^{\ell\times p}_{n}$ is an f-upper-
triangular tensor.

######  Theorem 7.

Let the third-order tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ be
invertible. Then LU factorization with partial pivoting can be applied in the
Fourier domain, resulting in the t-LU decomposition

$\mathscr{P}*\mathscr{A}=\mathscr{L}*\mathscr{U},$ (7)

where $\mathscr{P}\in\mathbb{K}^{p\times p}_{n}$ is the Fourier transform of
permutation matrices, $\mathscr{L}\in\mathbb{K}^{p\times p}_{n}$ is an f-unit-
lower triangular tensor, and $\mathscr{U}\in\mathbb{K}^{p\times p}_{n}$ is an
f-upper-triangular tensor.

###### Proof.

Let $\widehat{\mathscr{A}}={\tt fft}(\mathscr{A},[\,],3)$. Then, for
$i=1,\ldots,n$, we apply LU factorization with partial pivoting to the frontal
slices $\widehat{\mathscr{A}}^{(i)}$ of $\widehat{\mathscr{A}}$. This gives
the decompositions

$\widehat{P}^{(i)}\widehat{A}^{(i)}=\widehat{L}^{(i)}\widehat{U}^{(i)},\quad
i=1,2,\ldots,n,$

where $\widehat{P}^{(i)}$ is a permutation matrix, $\widehat{L}^{(i)}$ is a
unit lower triangular matrix, and $\widehat{U}^{(i)}$ is an upper triangular
matrix. These decompositions exist because the tensor $\mathscr{A}$ is
nonsingular. The matrices $\widehat{P}^{(i)}$, $\widehat{L}^{(i)}$, and
$\widehat{U}^{(i)}$ are frontal slices of the tensors $\widehat{P}$,
$\widehat{L}$, and $\widehat{U}$. The tensors in the decomposition (7) are
determined by

$\mathscr{P}={\tt
ifft}\left(\widehat{\mathscr{P}},[\,],3\right),\quad\mathscr{L}={\tt
ifft}\left(\widehat{\mathscr{L}},[\,],3\right),\quad\mathscr{U}={\tt
ifft}\left(\widehat{\mathscr{U}},[\,],3\right).$

∎

The following factorization generalizes the Hessenberg reduction for matrices.
It will be used below in the computation of tensor eigentubes and eigenslices.

######  Theorem 8.

The tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ is unitarily similar to
an f-upper-Hessenberg tensor, i.e.,

$\mathscr{H}=\mathscr{W}^{H}*\mathscr{A}*\mathscr{W},$

where $\mathscr{H}\in\mathbb{K}^{p\times p}_{n}$ is an f-upper-Hessenberg
tensor (all frontal slices in the Fourier domain are upper Hessenberg
matrices) and $\mathscr{W}\in\mathbb{K}^{p\times p}_{n}$ is an f-unitary
tensor.

###### Proof.

Let $\widehat{\mathscr{A}}={\tt fft}(\mathscr{A},[\,],3)$. Then, for
$i=1,\ldots,n$, the frontal slice $\widehat{\mathscr{A}}^{(i)}$ of
$\widehat{\mathscr{A}}$ is unitarily similar to a Hessenberg matrix $H_{i}$.
We have

$H_{i}=W_{i}^{H}\widehat{\mathscr{A}}^{(i)}W_{i},\quad i=1,2,\ldots,n,$

where the $H_{i}\in\mathbb{C}^{p\times p}$ are upper Hessenberg matrices and
the $W_{i}\in\mathbb{C}^{p\times p}$ are unitary matrices.

Define the tensors $\mathscr{H}^{\prime}$ and $\mathscr{W}^{\prime}$ as
follows:

$\mathscr{H}^{\prime(i)}=H_{i}{\rm\leavevmode\nobreak\ \leavevmode\nobreak\
and\leavevmode\nobreak\ \leavevmode\nobreak\
}\mathscr{W}^{\prime(i)}=W_{i},\quad i=1,2,\ldots,n.$

Then

$\mathscr{H}^{\prime(i)}=\left(\mathscr{W}^{\prime(i)}\right)^{H}\widehat{\mathscr{A}}^{(i)}\mathscr{W}^{\prime(i)},\quad
i=1,2,\ldots,n.$

Consequently, defining the tensors $\mathscr{H}={\tt
ifft}\left(\mathscr{H}^{\prime},[\,],3\right)$ and $\mathscr{W}={\tt
ifft}\left(\mathscr{W}^{\prime},[\,],3\right)$, we conclude that

$\mathscr{H}=\mathscr{W}^{H}*\mathscr{A}*\mathscr{W},$

where $\mathscr{H}$ is an f-Hessenberg tensor since each frontal slice is an
upper Hessenberg matrix in the Fourier domain; obviously the tensor
$\mathscr{W}$ is unitary, since its frontal slices in the Fourier domain are
unitary. ∎

Algorithm 2 provides details of the transformation of a tensor to f-upper-
Hessenberg form.

Algorithm 2 t-Hessenberg reduction (t-hess)

Input: $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$.
Output: Hessenberg tensor $\mathscr{H}\in\mathbb{K}^{p\times p}_{n}$ and
unitary tensor $\mathscr{W}\in\mathbb{K}^{p\times p}_{n}$.

1: $\widehat{\mathscr{A}}={\tt fft}\left(\mathscr{A},[\,],3\right)$.

2: for $i=1$ to $n$ do

3: $[\widehat{\mathscr{W}}^{(i)},\widehat{\mathscr{H}}^{(i)}]={\tt
hess}(\mathscr{A}^{(i)})$

4: end for

5: $\mathscr{W}={\tt ifft}\left(\widehat{\mathscr{W}},[\,],3\right)$,
$\mathscr{H}={\tt ifft}\left(\widehat{\mathscr{H}},[\,],3\right)$

The MATLAB function ${\tt hess}$ used in line $3$ of Algorithm 2 applies a
unitary similarity transformation $\widehat{\mathscr{W}}^{(i)}$ to the matrix
$\widehat{\mathscr{A}}^{(i)}$ to determine an upper Hessenberg matrix
$\widehat{\mathscr{H}}^{(i)}$. In the case of real tensors we can use the
symmetry property of the DFT.

Following Kilmer et al. [25], we introduce a bilinear form associated with the
t-product. For lateral slices
$\vec{\mathscr{X}},\vec{\mathscr{Y}}\in\mathbb{K}^{\ell}_{n}$, we define

$\langle\vec{\mathscr{X}},\vec{\mathscr{Y}}\rangle=\vec{\mathscr{X}}^{H}*\vec{\mathscr{Y}}\in\mathbb{K}_{n}.$

The value of this bilinear form is a tube and the quantity
$\langle\vec{\mathscr{X}},\vec{\mathscr{X}}\rangle$ is not necessarily real
and positive. The next lemma gives some properties of this bilinear form.

######  Lemma 9.

([25]) Let
$\vec{\mathscr{X}},\vec{\mathscr{Y}},\vec{\mathscr{Z}}\in\mathbb{K}^{p}_{n}$
and $\bm{a}\in\mathbb{K}_{n}$. Then the following properties hold:

  1. 1.

$\langle\vec{\mathscr{X}},\vec{\mathscr{Y}}+\vec{\mathscr{Z}}\rangle=\langle\vec{\mathscr{X}},\vec{\mathscr{Y}}\rangle+\langle\vec{\mathscr{X}},\vec{\mathscr{Z}}\rangle$,

  2. 2.

$\langle\vec{\mathscr{X}},\vec{\mathscr{Y}}*\bm{a}\rangle=\bm{a}*\langle\vec{\mathscr{X}},\vec{\mathscr{Y}}\rangle$,

  3. 3.

$\langle\bm{a}*\vec{\mathscr{X}},\vec{\mathscr{Y}}\rangle=\bm{a}^{H}*\langle\vec{\mathscr{X}},\vec{\mathscr{Y}}\rangle$,

  4. 4.

$\langle\vec{\mathscr{X}}.\vec{\mathscr{Y}}\rangle=\langle\vec{\mathscr{Y}},\vec{\mathscr{X}}\rangle^{H}$.

A sequence
$\left\\{\vec{\mathscr{X}}_{1},\vec{\mathscr{X}}_{2},\ldots,\vec{\mathscr{X}}_{p}\right\\}\subset\mathbb{K}^{\ell}_{n}$
of $p\geq 2$ lateral slices is said to be f-orthogonal if

$\langle\vec{\mathscr{X}}_{i},\vec{\mathscr{X}}_{j}\rangle=\vec{\mathscr{X}}_{i}^{H}*\vec{\mathscr{X}}_{j}=\left\\{\begin{array}[]{ll}\alpha_{i}\textbf{e}&\mbox{if
$i=j$},\;\;i,j=1,2,\ldots,p,\\\ \textbf{0}&\mbox{else},\end{array}\right.$

where $\bm{e}$ is the unit tube and $\alpha_{i}\in\mathbb{C}$. If
$\alpha_{i}=1$ for all $1\leq i\leq p$, then the sequence is said to be
f-orthonormal.

Let the lateral slice $\vec{\mathscr{Y}}\in\mathbb{K}^{\ell}_{n}$ be
nonvanishing. We then can normalize $\vec{\mathscr{Y}}$ in order to obtain a
slice $\vec{\mathscr{X}}\in\mathbb{K}^{\ell}_{n}$ with norm
$\|\vec{\mathscr{X}}\|=1$, i.e., $\vec{\mathscr{Y}}=\vec{\mathscr{X}}*\bm{a}$
with $\|\vec{\mathscr{Y}}\|=\|\bm{a}\|$, where

$\|\vec{\mathscr{Y}}\|=\dfrac{\|\langle\vec{\mathscr{Y}},\vec{\mathscr{Y}}\rangle\|_{F}}{\|\vec{\mathscr{Y}}\|_{F}}.$

##  4 Tensor eigenpairs based on the t-product

This section introduces tensor eigenpairs for third-order tensors defined with
the aid of the t-product.

######  Definition 10.

Let $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ and let
$\gamma_{1,i},\gamma_{2,i},\ldots,\gamma_{p,i}$ be the eigenvalues of
$\widehat{\mathscr{A}}^{(i)}$ for $i=1,2,\ldots,n$, ordered such as

$|\gamma_{j,i}|\geq|\gamma_{j+1,i}|,\quad j=1,2,\ldots,p-1.$

The tubes $\bm{\lambda}_{1},\bm{\lambda}_{2},\ldots,\bm{\lambda}_{p}$ defined
by

$\widehat{\bm{\lambda}}_{j}^{(i)}=\gamma_{j,i},\;i=1,2,\ldots,n,\;j=1,2,\ldots,p,$

are _eigentubes_ of $\mathscr{A}$. For a given eigentube $\bm{\lambda}$ of
$\mathscr{A}$, a nonvanishing lateral slice
$\vec{\mathscr{U}}\in\mathbb{K}^{p}_{n}$ such that

$\mathscr{A}*\vec{\mathscr{U}}=\bm{\lambda}*\vec{\mathscr{U}}$ (8)

is said to be an _eigenslice_ or _right eigenslice_ of $\mathscr{A}$
associated with $\bm{\lambda}$. Moreover, the set
$\\{\bm{\lambda},\vec{\mathscr{U}}\\}$ is referred to as an eigenpair of
$\mathscr{A}$.

Note that equations (8) and (5), imply that

$\mathscr{A}*\vec{\mathscr{U}}=\vec{\mathscr{U}}*\bm{\lambda}.$

We remark that when $n=1$, the third-order tensor reduces to a square matrix,
and the eigentubes and eigenslices become eigenvalues and eigenvectors,
respectively.

A tensor $\mathscr{A}\in\mathbb{K}_{n}^{p\times p}$ has $p$ eigentubes. Let
$\bm{\lambda}_{1},\bm{\lambda}_{2},\ldots,\bm{\lambda}_{p}$ be the eigentubes
of $\mathscr{A}$. Then

$\left\|\bm{\lambda}_{1}\right\|_{F}\geq\left\|\bm{\lambda}_{2}\right\|_{F}\geq\ldots\geq\left\|\bm{\lambda}_{p}\right\|_{F}.$

The set of all eigentubes of $\mathscr{A}$ is referred to as the _spectrum_ of
$\mathscr{A}$ and is denoted by $\bm{\Lambda}\left(\mathscr{A}\right)$. The
_spectral radius_ of $\mathscr{A}$ is defined as

$\rho\left(\mathscr{A}\right)=\max_{\bm{\lambda}\in\bm{\Lambda}\left(\mathscr{A}\right)}\left\|\bm{\lambda}\right\|_{F}.$

The eigenvalues of a matrix are the zeros of the characteristic polynomial for
the matrix. We will derive an analogous result for third-order tensors. To
this end, we require the definition of the determinant of a square third-order
tensor.

######  Definition 11.

Let $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$. The determinant of
$\mathscr{A}$ under the t-product is the tube

$\bm{\gamma}=\operatorname*{Det}\left(\mathscr{A}\right)\in\mathbb{K}_{n},$

which is defined by the inverse Fourier transformation of the tube
$\widehat{\bm{\gamma}}$ with
$\widehat{\bm{\gamma}}^{(i)}=\det\left(\widehat{\mathscr{A}}^{(i)}\right)$,
$i=1,2,\ldots,n$, where $\widehat{\mathscr{A}}={\tt fft}(\mathscr{A},[\,],3)$.

Thus, the determinant of a third-order tensor under the t-product is a
function

$\begin{split}\operatorname*{Det}:\mathbb{K}^{p\times
p}_{n}&\to\mathbb{K}_{n}\\\
\mathscr{A}&\mapsto\operatorname*{Det}\left(\mathscr{A}\right),\end{split}$

such that
$\widehat{\operatorname*{Det}\left(\mathscr{A}\right)}^{(i)}=\det\left(\widehat{\mathscr{A}}^{(i)}\right)$
for $i=1,2,\ldots,n$. This determinant has the following properties.

######  Proposition 12.

Let $\mathscr{A},\mathscr{B}\in\mathbb{K}^{p\times p}_{n}$ and let
$\bm{\alpha}\in\mathbb{K}_{n}$. Then

  1. (i)

$\operatorname*{Det}\left(\mathscr{A}*\mathscr{B}\right)=\operatorname*{Det}\left(\mathscr{B}*\mathscr{A}\right)$,

  2. (ii)

$\operatorname*{Det}\left(\mathscr{A}^{H}\right)=\left(\operatorname*{Det}\left(\mathscr{A}\right)\right)^{H}$,

  3. (iii)

$\operatorname*{Det}\left(\bm{\alpha}*\mathscr{A}\right)=\bm{\alpha}^{p}*\operatorname*{Det}\left(\mathscr{A}\right)$.

###### Proof.

  1. (i)

Let $\mathscr{C}=\mathscr{A}*\mathscr{B}$. Then
$\widehat{\mathscr{C}}^{(i)}=\widehat{\mathscr{A}}^{(i)}\widehat{\mathscr{B}}^{(i)}$
for $i=1,2,\dots,n$. Consider
$\bm{\gamma}=\operatorname*{Det}\left(\mathscr{A}*\mathscr{B}\right)$. Then

$\displaystyle\widehat{\bm{\gamma}}^{(i)}=\det\left(\widehat{\mathscr{C}}^{(i)}\right)$
$\displaystyle=$
$\displaystyle\det\left(\widehat{\mathscr{A}}^{(i)}\widehat{\mathscr{B}}^{(i)}\right)$
$\displaystyle=$
$\displaystyle\det\left(\widehat{\mathscr{B}}^{(i)}\widehat{\mathscr{A}}^{(i)}\right).$

We conclude that
$\operatorname*{Det}\left(\mathscr{A}*\mathscr{B}\right)=\operatorname*{Det}\left(\mathscr{B}*\mathscr{A}\right)$.

  2. (ii)

Let $\bm{\gamma}=\operatorname*{Det}\left(\mathscr{A}^{H}\right)$. Then

$\displaystyle\widehat{\bm{\gamma}}^{(i)}=\det\left(\widehat{\mathscr{A}^{H}}^{(i)}\right)=\det\left(\left(\widehat{\mathscr{A}}^{(i)}\right)^{H}\right)={\tt
conj}\left(\det\left(\widehat{\mathscr{A}}^{(i)}\right)\right).$

This shows that
$\operatorname*{Det}\left(\mathscr{A}^{H}\right)=\left(\operatorname*{Det}\left(\mathscr{A}\right)\right)^{H}$.

  3. (iii)

Let $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ and
$\bm{\alpha}\in\mathbb{K}_{n}$. Then

$\det\left(\widehat{\bm{\alpha}}^{(i)}\widehat{\mathscr{A}}^{(i)}\right)=\left(\widehat{\bm{\alpha}}^{(i)}\right)^{p}\det\left(\widehat{\mathscr{A}}^{(i)}\right).$

By the definition of the power of a third-order tensor, we obtain
$\operatorname*{Det}\left(\bm{\alpha}*\mathscr{A}\right)=\bm{\alpha}^{p}*\operatorname*{Det}\left(\mathscr{A}\right)$.

∎

Define the polynomial $\bm{P}$ of degree $s$ on the commutative ring
$\left(\mathbb{K}_{n},+,*\right)$ as follows:

$\bm{P}\left(\bm{x}\right)=\sum_{i=0}^{s}\bm{a}_{i}*\bm{x}^{i},$

where $\bm{a}_{i}\in\mathbb{K}_{n}$ for $i=0,1,\ldots,s$ and
$\bm{a}_{s}\not\equiv 0$. We remark that if $\bm{P}$ is a polynomial in
$\mathbb{K}_{n}$ of degree $s$, then each polynomial $\bm{P}^{(i)}$ defined by

$\bm{P}^{(i)}(\bm{x})=\sum_{j=0}^{s}\widehat{\bm{a}}_{j}^{(i)}\left(\widehat{\bm{x}}^{(i)}\right)^{j},\quad
i=1,2,\ldots,n,$

is of degree $s$.

######  Definition 13.

Let $\bm{P}$ be a polynomial in $\mathbb{K}_{n}$ of degree $s$. We say that
$\bm{\gamma}_{1},\bm{\gamma}_{2},\ldots,\bm{\gamma}_{s}$ are roots of
$\bm{P}$, i.e., they are solutions of $\bm{P}(\bm{x})=0$, if
$\widehat{\bm{\gamma}}_{1}^{(i)},\ldots,\widehat{\bm{\gamma}}_{s}^{(i)}$ are
roots of $\bm{P}^{(i)}$. We order the roots according to
$|\widehat{\bm{\gamma}}_{j}^{(i)}|\geq|\widehat{\bm{\gamma}}_{j+1}^{(i)}|$ for
$j=1,2,\ldots,s-1$.

It follows from Definition 13 that every polynomial in $\mathbb{K}_{n}$ of
degree $s$ has $s$ roots in $\mathbb{K}_{n}$.

######  Definition 14.

Let $\bm{P}$ be a polynomial of degree $s$ in $\mathbb{K}_{n}$. We say that a
root $\bm{\gamma}$ of $\bm{P}$ is of f-multiplicity

$m=\min_{1\leq i\leq n}\,{\rm mult}\left(\widehat{\bm{\gamma}}^{(i)}\right),$

where for each $i=1,2,\ldots,n$, ${\rm
mult}\left(\widehat{\bm{\gamma}}^{(i)}\right)$ denotes the multiplicity of the
root $\widehat{\bm{\gamma}}^{(i)}$.

######  Definition 15.

Let $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$. Then the characteristic
polynomial of $\mathscr{A}$ is given by

$\bm{P}_{\mathscr{A}}\left(\bm{x}\right)=\operatorname*{Det}\left(\mathscr{A}-\mathscr{I}_{p}*\bm{x}\right),\quad\bm{x}\in\mathbb{K}_{n}.$

We remark that the degree of the characteristic polynomial of the tensor
$\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ is $p$ since the degree of the
characteristic polynomial of each frontal slice of $\widehat{\mathscr{A}}$ is
$p$. Furthermore, the characteristic polynomial of $\mathscr{A}$ has $p$
roots.

######  Proposition 16.

An eigentube of the tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ is a
root of the characteristic polynomial $\bm{P}_{\mathscr{A}}$ of $\mathscr{A}$.

###### Proof.

Let $\bm{\lambda}$ be an eigentube of $\mathscr{A}$. Then
$\widehat{\bm{\lambda}}^{(i)}$ is an eigenvalue of
$\widehat{\mathscr{A}}^{(i)}$ for $i=1,2,\ldots,n$. Moreover,
$\widehat{\bm{\lambda}}^{(i)}$ is a root of the characteristic polynomial of
$\widehat{\mathscr{A}}^{(i)}$ for $i=1,2,\ldots,n$. Therefore
$\bm{P}_{\mathscr{A}}\left(\bm{\lambda}\right)=\operatorname*{Det}\left(\mathscr{A}-\mathscr{I}_{p}*\bm{\lambda}\right)=\bm{0}$.
∎

Note that the tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ has at most
$p$ distinct eigentubes.

######  Proposition 17.

Let $\bm{\lambda}$ be an eigentube of $\mathscr{A}\in\mathbb{K}^{p\times
p}_{n}$. Then $\bm{\lambda}^{H}$ is an eigentube of $\mathscr{A}^{H}$.

###### Proof.

This result follows from the observation that an eigentube is a root of the
characteristic polynomial of $\mathscr{A}$, and by using Proposition 12. ∎

Let $\bm{\lambda}$ be an eigentube of $\mathscr{A}\in\mathbb{K}^{p\times
p}_{n}$. The slice $\vec{\mathscr{V}}\in\mathbb{K}^{p}_{n}$ such that

$\mathscr{A}^{H}*\vec{\mathscr{V}}=\bm{\lambda}^{H}*\vec{\mathscr{V}}$

is called a _left eigenslice_ of $\mathscr{A}$ associated with $\bm{\lambda}$.

We turn to the linear independence of lateral slices. Let
$\\{\vec{\mathscr{V}}_{i}\\}_{i=1}^{s}\subset\mathbb{K}^{p}_{n}$ be a set of
lateral slices. This set is t-linearly independent if and only if

$\sum_{i=1}^{s}\bm{a}_{i}*\vec{\mathscr{V}}_{i}=\bm{0}\Longrightarrow\bm{a}_{i}=\bm{0},\quad
i=1,2,\ldots,s.$

It is clear that the slices
$\vec{\mathscr{V}}_{1},\ldots,\vec{\mathscr{V}}_{s}$ in $\mathbb{K}_{n}^{p}$
are t-linearly independent if and only if the vectors
$\vec{\widehat{\mathscr{V}}}_{1}^{(j)},\ldots,\vec{\widehat{\mathscr{V}}}_{s}^{(j)}$
are linearly independent for $j=1,2,\ldots,n$. This leads to the following
result.

######  Proposition 18.

A tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ is invertible under the
t-product if it has $p$ t-linearly independent lateral slices.

We are in a position to define f-diagonalization of a third-order tensor.

######  Definition 19.

A third-order tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ is said to be
f-diagonalizable under the t-product if and only if it is similar to an
f-diagonal tensor, i.e., if and only if

$\mathscr{A}=\mathscr{X}*\mathscr{D}*\mathscr{X}^{-1}$

for some invertible tensor $\mathscr{X}\in\mathbb{K}^{p\times p}_{n}$ and an
f-diagonal tensor $\mathscr{D}$ formed by the eigentubes.

######  Proposition 20.

A tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ is f-diagonalizable if and
only if it has $p$ linearly independent eigenslices.

######  Proposition 21.

Let $\vec{\mathscr{U}}$ be an eigenslice of $\mathscr{A}^{H}*\mathscr{A}$
associated with the eigentube $\bm{\lambda}$. Then
$\mathscr{A}*\vec{\mathscr{U}}$ is an eigentube of
$\mathscr{A}*\mathscr{A}^{H}$ associated to $\bm{\lambda}$.

###### Proof.

We have
$\mathscr{A}^{H}*\mathscr{A}*\vec{\mathscr{U}}=\vec{\mathscr{U}}*\bm{\lambda}$.
Therefore,
$\mathscr{A}*\mathscr{A}^{H}*\mathscr{A}*\vec{\mathscr{U}}=\mathscr{A}*\vec{\mathscr{U}}*\bm{\lambda}$.
∎

######  Theorem 22.

Let the tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ be f-Hermitian. Then
all eigentubes $\bm{\lambda}$ of $\mathscr{A}$ are real.

###### Proof.

Let $\\{\bm{\lambda},\vec{\mathscr{U}}\\}$ be an eigenpair of $\mathscr{A}$.
Then

$\bm{\lambda}=\dfrac{\langle\vec{\mathscr{U}},\mathscr{A}*\vec{\mathscr{U}}\rangle}{\langle\vec{\mathscr{U}},\vec{\mathscr{U}}\rangle}=\dfrac{\langle\mathscr{A}^{H}*\vec{\mathscr{U}},\vec{\mathscr{U}}\rangle}{\langle\vec{\mathscr{U}},\vec{\mathscr{U}}\rangle}=\bm{\lambda}^{H}.$

Since $\mathscr{A}$ is f-Hermitian, we have that each frontal slice of
$\widehat{\mathscr{A}}$ is a Hermitian matrix. Thus the eigenvalues of each
frontal slice of $\widehat{\mathscr{A}}$ are real. Each eigentube of
$\mathscr{A}$ is given by $\bm{\lambda}={\tt
ifft}(\widehat{\bm{\lambda}},[\,],3)$, where $\widehat{\bm{\lambda}}$ is a
real conjugate-even tube. Consequently, $\bm{\lambda}$ is a real conjugate-
even tube. ∎

Similarly as for matrices, we can relate eigentubes to tensor singular values.
Let $\mathscr{A}\in\mathbb{K}^{n\times m}_{p}$ be a third-order tensor with
tubal rank $r>0$. Consider the analogue of the singular tube decomposition (6)
of $\mathscr{A}$ with the singular tubes are ordered according to

$\left\|\bm{s}_{1}\right\|_{F}\geq\left\|\bm{s}_{2}\right\|_{F}\geq\ldots\geq\left\|\bm{s}_{r}\right\|_{F}\geq\|\bm{s}_{r+1}\|_{F}=\ldots=\|\bm{s}_{\min\\{m,n\\}}\|_{F}=0.$

Then

$\begin{array}[]{rcll}\mathscr{A}*\vec{\mathscr{V}}_{i}&=&\vec{\mathscr{U}}_{i}*\bm{s}_{i},\;i=1,2,\ldots,r,&\mathscr{A}*\vec{\mathscr{V}}_{i}=0,\;i=r+1,r+2,\ldots,m,\\\
\mathscr{A}^{H}*\vec{\mathscr{U}}_{i}&=&\vec{\mathscr{V}}_{i}*\bm{s}_{i},\;i=1,2,\ldots,r,&\mathscr{A}^{H}*\vec{\mathscr{U}}_{i}=0,\;i=r+1,r+2,\ldots,n.\end{array}$

This implies that $\vec{\mathscr{V}}_{1},\ldots,\vec{\mathscr{V}}_{m}$ are
eigenslices of $\mathscr{A}^{H}*\mathscr{A}$,
$\vec{\mathscr{U}}_{1},\ldots,\vec{\mathscr{U}}_{m}$ are eigenslices of
$\mathscr{A}*\mathscr{A}^{H}$, and $\bm{s}_{i}^{2}$, $i=1,2,\ldots,r$, are
nonzero eigentubes of $\mathscr{A}^{H}*\mathscr{A}$ and
$\mathscr{A}*\mathscr{A}^{H}$.

Numerical methods for spectral factorization of a real nonsymmetric matrix use
the real Schur form. We therefore are interested in the analogous
factorization of third-order tensors.

######  Theorem 23 (Real t-Schur decomposition).

Let $\mathscr{A}\in\mathbb{R}^{p\times p\times n}$ be a real third-order
tensor. There is a real f-orthogonal tensor $\mathscr{Q}\in\mathbb{R}^{p\times
p\times n}$ such that

$\mathscr{Q}*\mathscr{A}*\mathscr{Q}^{H}=\mathscr{R}=\begin{pmatrix}\mathscr{R}_{1,1}&\mathscr{R}_{1,2}&\dots&\dots&\mathscr{R}_{1,m}\\\
0&\mathscr{R}_{2,2}&\mathscr{R}_{2,2}&\dots&\mathscr{R}_{2,m}\\\
0&\dots&\ddots&\dots&\vdots\\\ \vdots&\dots&&&\vdots\\\
0&\vdots&&&\mathscr{R}_{m,m}\end{pmatrix}\in\mathbb{R}^{p\times p\times n},$

where the $\mathscr{R}_{i,i}$ are tensors of size $1\times 1\times n$ or
$2\times 2\times n$. The tensor $\mathscr{R}$ is _f-quasi-triangular_.

###### Proof.

The factorization follows from the real Schur factorization of the matrices in
each frontal slice of the tensor $\widehat{\mathscr{A}}$, and that the first
frontal slice of $\widehat{\mathscr{A}}$ is real, because
$\widehat{\mathscr{A}}^{(1)}=\dfrac{1}{\sqrt{n}}\mathscr{A}^{(i)}$. ∎

For $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$, let

$r_{i}=\dim\left(\operatorname*{\text{Null}}\left(\widehat{\mathscr{A}}^{(i)}\right)\right),\;\;i=1,2,\ldots,n,\quad
r=\displaystyle{\min_{1\leq i\leq n}}r_{i}.$

######  Definition 24.

Let $\mathscr{A}\in\mathbb{K}^{\ell\times p}_{n}$. The range of $\mathscr{A}$
is the t-span of the $p$ lateral slices of $\mathscr{A}$, i.e.,

$\mathop{\operator@font
Range}\nolimits\left(\mathscr{A}\right)=\left\\{\mathscr{A}*\vec{\mathscr{X}}:\,\vec{\mathscr{X}}\in\mathbb{K}^{p}_{n}\right\\},$

and the null space of $\mathscr{A}$ is defined as

$\displaystyle\operatorname*{\text{Null}_{t}}\left(\mathscr{A}\right)=$
$\displaystyle\left\\{\vec{\mathscr{X}}_{1},\ldots,\vec{\mathscr{X}}_{r}\in\mathbb{K}_{n}^{p}:\,\widehat{\vec{\mathscr{X}}}_{j}^{(i)}\in\operatorname*{\text{Null}}\left(\widehat{\mathscr{A}}^{(i)}\right)\;\text{for}\leavevmode\nobreak\
i=1,2,\ldots,n,\right.$
$\displaystyle\left.\quad\text{with}\;\|\widehat{\vec{\mathscr{X}}}_{j}^{(i)}\|_{F}\geq\|\widehat{\vec{\mathscr{X}}}_{j+1}^{(i)}\|_{F},\,j=1,2,\ldots,r_{i}\right\\}.$

It is clear from Definition 24 that if
$\vec{\mathscr{X}}\in\mathbb{K}^{p}_{n}$ is in the null space of a tensor
$\mathscr{A}\in\mathbb{K}_{n}^{p\times p}$, then
$\mathscr{A}*\vec{\mathscr{X}}=0$.

We introduce some definitions about eigentubes.

######  Definition 25.

Let $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$.

  * •

An eigentube $\bm{\lambda}$ of $\mathscr{A}$ is said to have algebraic
f-multiplicity $m$ if it is a root of f-multiplicity $m$ of the characteristic
polynomial.

  * •

Let $\bm{\lambda}$ be an eigentube of $\mathscr{A}$, and let $m_{i}$ be the
geometric multiplicity of $\widehat{\bm{\lambda}}^{(i)}$ for $i=1,2,\ldots,n$.
Then we refer to $m=\min_{1\leq i\leq n}m_{i}$ as the geometric f-multiplicity
of $\bm{\lambda}$.

  * •

An eigentube $\bm{\lambda}$ is said to be f-simple (f-semi-simple) if for each
$1\leq i\leq n$, the eigenvalue $\widehat{\bm{\lambda}}^{(i)}$ of
$\widehat{\mathscr{A}}^{(i)}$ is simple (semi-simple).

######  Proposition 26.

Let $\bm{\lambda}$ be an eigentube of $\mathscr{A}\in\mathbb{K}^{p\times
p}_{n}$ with geometric f-multiplicity $m$. Then
$m=\operatorname*{\dim_{t}}\left(\operatorname*{\text{Null}_{t}}\left(\mathscr{A}-\bm{\lambda}*\mathscr{I}_{p}\right)\right)$.

###### Proof.

Let $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ and

$m_{i}=\dim\left(\operatorname*{\text{Null}}\left(\widehat{\mathscr{A}}^{(i)}-\widehat{\bm{\lambda}}^{(i)}I\right)\right),\quad
i=1,2,\ldots,n.$

Since $\bm{\lambda}$ has geometric multiplicity $m$, we have $m=\min_{1\leq
i\leq n}m_{i}$, and the result follows. ∎

######  Definition 27.

Assume that the tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ has $\ell$
distinct eigentubes
$\bm{\lambda}_{1},\bm{\lambda}_{2},\ldots,\bm{\lambda}_{\ell}$. The index of
$\bm{\lambda}_{i}$ is the smallest integer such that

$\operatorname*{\text{Null}_{t}}\left(\mathscr{A}-\bm{\lambda}_{i}*\mathscr{I}_{p}\right)^{\ell_{i}}=\operatorname*{\text{Null}_{t}}\left(\mathscr{A}-\bm{\lambda}_{i}*\mathscr{I}_{p}\right)^{k},\;\;\forall
k\geq\ell_{i}.$

Let $\ell_{i}$ be the index of the eigentube $\bm{\lambda}_{i}$ of
$\mathscr{A}$. Then $\ell_{i}$ is the maximum index of the eigenvalues
$\widehat{\bm{\lambda}}_{i}^{(j)}$ of the matrix $\widehat{\mathscr{A}}^{(j)}$
for $j=1,2,\ldots,n$. Note that if $\bm{\lambda}_{i}$ is an f-semi-simple
eigentube of $\mathscr{A}$, then $\ell_{i}=1$.

######  Proposition 28.

Let $\vec{\mathscr{X}}\in\mathbb{K}^{p}_{n}$. Then $\vec{\mathscr{X}}$ can be
represented as

$\vec{\mathscr{X}}=\sum_{i=1}^{\ell}\vec{\mathscr{X}}_{i},$

where
$\vec{\mathscr{X}}_{i}\in\operatorname*{\text{Null}_{t}}\left(\mathscr{A}-\bm{\lambda}_{i}*\mathscr{I}_{p}\right)^{\ell_{i}}$
and $\ell_{i}$ is the index of $\bm{\lambda}_{i}$ for $i=1,\ldots,\ell$.

###### Proof.

Let $\vec{\mathscr{X}}\in\mathbb{K}^{p}_{n}$ and let
$\widehat{\vec{\mathscr{X}}}$ denote the associated tensor in the Fourier
domain. The frontal slices $\widehat{\vec{\mathscr{X}}}^{(k)}$,
$k=1,2,\ldots,n$, of $\widehat{\vec{\mathscr{X}}}$ live in $\mathbb{C}^{p}$.
There is a unique

$x_{j,k}\in\operatorname*{\text{Null}}\left(\widehat{\mathscr{A}}^{(k)}-\widehat{\bm{\lambda}}_{j}^{(k)}I\right)^{\ell_{i}}$

such that

$\widehat{\vec{\mathscr{X}}}^{(k)}=\sum_{j=1}^{\ell}x_{j,k}.$

The sequences
$\\{x_{1,1},\ldots,x_{\ell,1}\\},\;\ldots,\;\\{x_{1,n},\ldots,x_{\ell,n}\\}$
determine the sequence of lateral slices
$\\{\vec{\mathscr{X}}_{1},\ldots,\vec{\mathscr{X}}_{\ell}\\}$, such that

$\vec{\mathscr{X}}=\sum_{j=1}^{\ell}\vec{\mathscr{X}}_{j},$

with
$\vec{\mathscr{X}}_{j}\in\operatorname*{\text{Null}_{t}}\left(\mathscr{A}-\bm{\lambda}_{i}*\mathscr{I}_{p}\right)^{\ell_{i}}$.
∎

##  5 Methods for eigenpair computation of third-order tensors

This section describes several methods for computing one or several eigenpairs
of third-order tensors.

###  5.1 Single lateral slice iteration

The power method is one of the oldest and simplest techniques for computing
the eigenvalue of largest magnitude and an associated eigenvector of a square
matrix; see, e.g., [22]. It is also known as von Mises iteration [35].
Presently, this method finds applications to page-rank computations; see [5,
10]. We describe a t-power method for computing the eigenslice of largest
magnitude of a third-order tensor, and discuss some of its properties. These
properties are well known in matrix computations. Kilmer et al. [25] present
an algorithm that is slightly different from the t-power method described
below, however, without defining eigentubes and eigenslices.

###  5.2 The t-power method

This method determines a sequence of lateral slices
$\mathscr{A}^{k}*\vec{\mathscr{V}}_{0}$, $k=1,2,\ldots\leavevmode\nobreak\ $,
suitably scaled, where $\vec{\mathscr{V}}_{0}\in\mathbb{K}^{p}_{n}$. Under
suitable conditions on $\mathscr{A}$ and $\vec{\mathscr{V}}_{0}$ (see below),
the sequence generated converges to an eigenslice associated with the
eigentube of largest norm. Here and below “norm” refers to the Frobenius norm.
The main advantage of the t-power method, when compared with other methods for
computing eigenpairs, is the fairly small amount of computer memory required.
Algorithm 3 describes the computations with the t-power method.

Algorithm 3 The t-power method

Input: $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$,
$\vec{\mathscr{V}}_{0}\in\mathbb{K}^{p}_{n}$ nonzero.
Output: An eigenpair $\left\\{\bm{\lambda},\vec{\mathscr{U}}\right\\}$ of
$\mathscr{A}$, where $\bm{\lambda}$ is the eigentube of largest norm.

1: for $k=1,2,\ldots\leavevmode\nobreak\ $ until convergence do

2: $\bm{\alpha}_{k}=\text{t-}\max(\mathscr{A}*\vec{\mathscr{V}}_{k-1})$

3:
$\vec{\mathscr{V}}_{k}=(\mathscr{A}*\vec{\mathscr{V}}_{k-1})/\bm{\alpha}_{k}$

4: end for

5: $\vec{\mathscr{U}}=\vec{\mathscr{V}}_{k}$, $\bm{\lambda}=\bm{\alpha}_{k}$

The function $\text{t-}\max\leavevmode\nobreak\ $ of a lateral slice in line
$2$ of Algorithm 3 returns the tube of largest norm of all tubes in the
lateral slice. The stopping criterion will be discussed in Section 6. The
following result generalizes the classical convergence result for the matrix
power method to the t-power method. The proof is analogous to the matrix case
and therefore is omitted.

######  Theorem 29.

Let $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}\,$ have only one eigentube,
$\bm{\lambda}_{1}$, of largest norm. The initial lateral slice
$\vec{\mathscr{V}}_{0}$ for the t-power method either has no tube in the
invariant subspace associated with $\bm{\lambda}_{1}$, or the sequence
$\vec{\mathscr{V}}_{k}$, $k=1,2,\ldots\leavevmode\nobreak\ $, generated by
Algorithm 3 converges to an eigenslice associated with $\bm{\lambda}_{1}$, and
the sequence $\bm{\alpha}_{k}$, $k=1,2,\ldots\leavevmode\nobreak\ $, converges
to $\bm{\lambda}_{1}$.

######  Theorem 30.

Let $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ have $p$ distinct eigentubes
$\bm{\lambda}_{1},\bm{\lambda}_{2},\ldots,\bm{\lambda}_{p}$ ordered
increasingly, i.e.,
$\left\|\bm{\lambda}_{1}\right\|_{F}>\left\|\bm{\lambda}_{2}\right\|_{F}\geq\ldots\geq\left\|\bm{\lambda}_{p}\right\|_{F}$.
Let the lateral slice $\vec{\mathscr{V}}_{0}$ have a component in the
invariant subspace associated to $\bm{\lambda}_{1}$. Then the sequence
$\vec{\mathscr{V}}_{k}$, $k=1,2,\ldots\leavevmode\nobreak\ $, generated by
Algorithm 3 converges to an eigenslice associated with the eigentube
$\bm{\lambda}_{1}$.

###### Proof.

By Proposition 28, we have

$\vec{\mathscr{V}}_{0}=\sum_{i=1}^{p}\bm{c}_{i}*\vec{\mathscr{X}}_{i},$

where
$\vec{\mathscr{X}}_{i}\in\operatorname*{\text{Null}_{t}}\left(\mathscr{A}-\bm{\lambda}_{i}*\mathscr{I}_{p}\right)$.
Since $\vec{\mathscr{V}}_{0}$ has a component in the invariant subspace
associated with $\bm{\lambda}_{1}$, it follows that $\bm{c}_{1}\neq 0$.

We are interested in the space spanned by $\vec{\mathscr{V}}_{k}$. This space
is independent of the scaling factors $\bm{\alpha}_{k}\neq\bm{0}$ in Algorithm
3. Therefore we may assume in this proof may ignore the $\bm{\alpha}_{k}$ for
all $k$. We then have for $k=1,2,\ldots\leavevmode\nobreak\ $ that

$\vec{\mathscr{V}}_{k}=\mathscr{A}^{k}*\vec{\mathscr{V}}_{0}=\sum_{i=1}^{p}\bm{c}_{i}*\bm{\lambda}_{i}^{k}*\vec{\mathscr{X}}_{i}=\bm{c}_{1}*\bm{\lambda}_{1}^{k}*\vec{\mathscr{X}}_{1}+\sum_{i=2}^{p}\left(\dfrac{\bm{\lambda}_{i}}{\bm{\lambda}_{1}}\right)^{k}*\bm{c}_{i}*\vec{\mathscr{X}}_{i}.$

Therefore

$\begin{split}\left\|\vec{\mathscr{V}}_{k}-\bm{c}_{1}*\bm{\lambda}_{1}^{k}*\vec{\mathscr{X}}_{1}\right\|_{F}=\left\|\sum_{i=2}^{p}\left(\dfrac{\bm{\lambda}_{i}}{\bm{\lambda}_{1}}\right)^{k}*\bm{c}_{i}*\vec{\mathscr{X}}_{i}\right\|_{F}&\leq\sum_{i=2}^{p}\left\|\left(\dfrac{\bm{\lambda}_{i}}{\bm{\lambda}_{1}}\right)^{k}*\bm{c}_{i}*\vec{\mathscr{X}}_{i}\right\|_{F}\\\
&\leq\sum_{i=2}^{p}\left\|\dfrac{\bm{\lambda}_{i}}{\bm{\lambda}_{1}}\right\|_{F}^{k}\left\|\bm{c}_{i}*\vec{\mathscr{V}}_{i}\right\|_{F}.\end{split}$

Since
$\left\|\bm{\lambda}_{i}\right\|_{F}<\left\|\bm{\lambda}_{1}\right\|_{F}$ for
all $i>1$, the sum in the right-hand side converges to zero as $k$ increases.
It follows that

$\lim_{k\to+\infty}\vec{\mathscr{V}}_{k}=\lim_{k\to+\infty}\bm{c}_{1}*\bm{\lambda}_{1}^{k}*\vec{\mathscr{X}}_{1}.$

This shows the theorem. ∎

We can see from the proof of Theorem 30, that the rate of convergence is
larger, the smaller the quotients
$\left\|\bm{\lambda}_{i}\right\|_{F}/\left\|\bm{\lambda}_{1}\right\|_{F}$ are
for $i=2,\ldots,p$.

The rate of convergence of the t-power method may be improved by applying the
method to the shifted tensor $\mathscr{A}+\bm{\sigma}*\mathscr{I}_{p}$ for a
suitable shift $\bm{\sigma}$, instead of applying the method to $\mathscr{A}$.
This follows from the proof of Theorem 30. We omit the details.

###  5.3 The inverse t-power method

In its simplest form this method can be applied to compute an eigenslice
associated with the eigentube of smallest norm. Then the method is obtained by
applying the t-power method to the tensor $\mathscr{A}^{-1}$. This yields the
sequence

$\vec{\mathscr{V}}_{k}=(\mathscr{A}^{-1}*\vec{\mathscr{V}}_{k-1})/\bm{\alpha}_{k},\quad
k=1,2,\ldots\leavevmode\nobreak\ ,$

of lateral slices, where $\vec{\mathscr{V}}_{0}$ is an initial user-supplied
slice. The sequence converges to the lateral slice associated with the
eigentube of largest norm of $\mathscr{A}^{-1}$, if this eigentube is unique
and if $\vec{\mathscr{V}}_{0}$ contains a component of this slice. Since the
eigentubes of $\mathscr{A}$ are the inverse of the eigentubes of
$\mathscr{A}^{-1}$, we obtain converge to the lateral slice associated with
the eigentube of smallest norm of $\mathscr{A}$. Algorithm 4 describes a
shifted version that can be used to determine an eigenslice associated with
the eigentube that is closest to $\bm{\sigma}$, if this eigentube is unique
and the initial slice $\vec{\mathscr{V}}_{0}$ contains a component of this
eigenslice.

Algorithm 4 The shifted inverse t-power method

Input: $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$,
$\vec{\mathscr{V}}_{0}\in\mathbb{K}^{p}_{n}$, and
$\bm{\sigma}\in\mathbb{K}_{n}$.
Output: The eigenpair $\\{\bm{\lambda},\vec{\mathscr{U}}\\}$ of $\mathscr{A}$,
where $\bm{\lambda}$ is the eigentube closest to $\bm{\sigma}$.

1: for $k=1,2,\ldots\leavevmode\nobreak\ $ until convergence do

2: Evaluate
$\vec{\mathscr{W}}=\left(\mathscr{A}-\bm{\sigma}*\mathscr{I}_{p}\right)^{-1}*\vec{\mathscr{V}}_{k-1}$

3: $\bm{\alpha}_{k}=\text{t-}\max(\vec{\mathscr{W}})$

4: $\vec{\mathscr{V}}_{k}=\vec{\mathscr{W}}/\bm{\alpha}_{k}$

5: end for

6: $\vec{\mathscr{U}}=\vec{\mathscr{V}}_{k}$,
$\bm{\lambda}=\dfrac{\bm{e}}{\bm{\alpha}_{k}+\bm{\sigma}}$

The evaluation of $\vec{\mathscr{W}}$ in line 2 of Algorithm 4 can be carried
out, e.g., by using a t-QR, t-LU, or t-Choleski factorization of
$\mathscr{A}-\bm{\sigma}*\mathscr{I}_{p}$; the t-Choleski factorization is
described in [32].

###  5.4 Deflation

Deflation is a well known technique in matrix computation. It makes it
possible to use the power method to compute more eigenpairs of a matrix than
the pair associated with the eigenvalue of largest magnitude. This section
describes how deflation can be used together with the t-power method.

Let the tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ have a unique
eigentube $\bm{\lambda}_{1}$ of largest norm, and let $\vec{\mathscr{U}}_{1}$
be an associated eigenslice. Assume that the eigenpair
$\\{\bm{\lambda}_{1},\vec{\mathscr{U}}_{1}\\}$ has been computed, e.g., by the
t-tensor power method. The idea behind deflation is to apply Algorithm 3 to
the tensor

$\mathscr{A}_{1}=\mathscr{A}-\bm{\sigma}*\vec{\mathscr{U}}_{1}*\vec{\mathscr{V}}^{H},$
(9)

where $\vec{\mathscr{V}}\in\mathbb{K}^{p}_{n}$ is an arbitrary lateral slice
such that $\vec{\mathscr{V}}^{H}*\vec{\mathscr{U}}_{1}=\bm{e}$, and
$\bm{\sigma}\in\mathbb{K}_{n}$ is an appropriate shift. The tensor
$\mathscr{A}_{1}$ has the same eigentubes as $\mathscr{A}$ except for
$\bm{\lambda}_{1}$, which is transformed to $\bm{\lambda}_{1}-\bm{\sigma}$, as
is shown in the next theorem.

######  Theorem 31.

Let $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ have the eigenpairs
$\\{\bm{\lambda}_{i},\vec{\mathscr{U}}_{i}\\}_{i=1}^{\ell}$, and let the tube
$\bm{\sigma}\in\mathbb{K}_{n}$ be such that
$\bm{\lambda}_{i}\neq\bm{\lambda}_{1}-\bm{\sigma}$, $i=1,2,\ldots,\ell$. Then
the tensor $\mathscr{A}_{1}$, defined by (9), has the eigenpairs

$\\{(\bm{\lambda}_{1}-\bm{\sigma},\vec{\mathscr{U}}_{1}),(\bm{\lambda}_{i},\vec{\mathscr{U}}_{i}+\bm{\gamma}_{i}*\vec{\mathscr{U}}_{1})_{i=2}^{\ell}\\},$

with

$\bm{\gamma}_{i}=\dfrac{\bm{\sigma}*\vec{\mathscr{V}}^{H}*\vec{\mathscr{U}}_{i}}{\bm{\sigma}-(\bm{\lambda}_{1}-\bm{\lambda}_{i})},\quad
i=2,3,\ldots,\ell.$

###### Proof.

First note that $\bm{\lambda}_{i}\neq\bm{\lambda}_{1}-\bm{\sigma}$ means that

$\widehat{\bm{\lambda}}_{i}^{(j)}\neq\widehat{\bm{\lambda}}_{1}^{(j)}-\widehat{\bm{\sigma}}^{(j)},\quad
1\leq j\leq n.$

Let $\bm{\sigma}$ be such that
$\bm{\lambda}_{i}\neq\bm{\lambda}_{1}-\bm{\sigma}$. We will show that
$\\{\bm{\lambda}_{1}-\bm{\sigma},\vec{\mathscr{U}}_{1}\\}$ is an eigenpair of
$\mathscr{A}_{1}$ and that the deflation procedure preserves the eigentubes
$\bm{\lambda}_{2},\bm{\lambda}_{3},\ldots,\bm{\lambda}_{\ell}$. We have

$\begin{split}\mathscr{A}_{1}*\vec{\mathscr{U}}_{1}=\left(\mathscr{A}-\bm{\sigma}*\vec{\mathscr{U}}_{1}*\vec{\mathscr{V}}^{H}\right)*\vec{\mathscr{U}}_{1}&=\mathscr{A}*\vec{\mathscr{U}}_{1}-\bm{\sigma}*\vec{\mathscr{U}}_{1}*\vec{\mathscr{V}}^{H}*\vec{\mathscr{U}}_{1}\\\
&=\bm{\lambda}_{1}*\vec{\mathscr{U}}_{1}-\bm{\sigma}*\vec{\mathscr{U}}_{1}\\\
&=\left(\bm{\lambda}_{1}-\bm{\sigma}\right)*\vec{\mathscr{U}}_{1}.\end{split}$

On the other hand, let $\vec{\mathscr{W}}_{j}$ be the left eigenslice
associated with $\bm{\lambda}_{j}$ for $j=2,3,\ldots,\ell$. Then we have

$\mathscr{A}^{H}*\vec{\mathscr{W}}_{j}=\bm{\lambda_{j}}*\vec{\mathscr{W}}_{j},$

and since $\\{\vec{\mathscr{W}}_{j}\\}_{j=2}^{\ell}$ are f-orthogonal to
$\vec{\mathscr{U}}_{1}$, we get

$\begin{split}\mathscr{A}_{1}^{H}*\vec{\mathscr{W}}_{j}=\left(\mathscr{A}-\bm{\sigma}*\vec{\mathscr{U}}_{1}*\vec{\mathscr{V}}^{H}\right)^{H}*\vec{\mathscr{W}}_{j}&=\left(\mathscr{A}^{H}-\bm{\sigma}^{H}*\vec{\mathscr{V}}*\vec{\mathscr{U}}_{1}^{H}\right)*\vec{\mathscr{W}}_{j}\\\
&=\bm{\lambda}_{j}*\vec{\mathscr{W}}_{j},\quad j=2,3,\ldots,\ell.\end{split}$

Thus, deflation preserves the left eigenslices
$\vec{\mathscr{W}}_{2},\vec{\mathscr{W}}_{3},\ldots,\vec{\mathscr{W}}_{\ell}$
and the eigentubes
$\bm{\lambda}_{2},\bm{\lambda}_{3},\ldots,\bm{\lambda}_{\ell}$.

Since $\bm{\lambda}_{2},\bm{\lambda}_{3},\ldots,\bm{\lambda}_{\ell}$ are
eigentubes of $\mathscr{A}_{1}$, we will now construct eigenslices associated
with these eigentubes. Let for $i=2,3,\ldots,\ell$,

$\check{\vec{\mathscr{U}}}_{i}=\vec{\mathscr{U}}_{i}-\bm{\gamma}_{i}*\vec{\mathscr{U}}_{1}.$

Since
$\mathscr{A}_{1}*\check{\vec{\mathscr{U}}}_{i}=\bm{\lambda}_{i}*\check{\vec{\mathscr{U}}}_{i}$,
it follows that $\bm{\gamma}_{i}$ is given by

$\bm{\gamma}_{i}=\dfrac{\bm{\sigma}*\vec{\mathscr{V}}^{H}*\vec{\mathscr{U}}_{i}}{\bm{\sigma}-\left(\bm{\lambda}_{1}-\bm{\lambda}_{i}\right)},\quad
i=2,3,\ldots,\ell,$

and $\bm{\gamma}_{1}=0$ such that
$\bm{\sigma}\neq\bm{\lambda}_{1}-\bm{\lambda}_{i}$. ∎

Deflation techniques for matrices have been discussed in several works, see,
e.g., Saad [34, Chapter 4.2], and the choice of the analogue of the slice
$\vec{\mathscr{V}}$ has received some attention. Analyses for the matrix case
suggest that we let $\vec{\mathscr{V}}=\vec{\mathscr{W}}_{1}$, where
$\vec{\mathscr{W}}_{1}$ is the left eigenslice of $\mathscr{A}$, or
$\vec{\mathscr{V}}=\vec{\mathscr{U}}_{1}$. The latter choice preserves the
t-Schur lateral slices.

######  Proposition 32.

Let $\vec{\mathscr{U}}_{1}$ be an eigenslice of $\mathscr{A}$ of norm $1$
associated with $\bm{\lambda}_{1}$ and let
$\mathscr{A}_{1}=\mathscr{A}-\bm{\sigma}*\vec{\mathscr{U}}_{1}*\vec{\mathscr{U}}_{1}^{H}$.
Then the eigentubes of $\mathscr{A}_{1}$ are
$\widetilde{\bm{\lambda}}_{1}=\bm{\lambda}_{1}-\bm{\sigma}$ and
$\widetilde{\bm{\lambda}}_{j}=\bm{\lambda}_{j}$, $j=2,3,\ldots,\ell$.
Moreover, the t-Schur lateral slices associated with
$\widetilde{\bm{\lambda}}_{j}$, $j=1,2,\ldots,\ell$ are identical with those
of $\mathscr{A}$.

###### Proof.

Let $\mathscr{A}*\mathscr{U}=\mathscr{U}*\mathscr{R}$ be the t-Schur
factorization of the tensor $\mathscr{A}$, where
$\mathscr{U}\in\mathbb{K}^{p\times p}_{n}$ is an f-orthogonal tensor and
$\mathscr{R}\in\mathbb{K}^{p\times p}_{n}$ is an upper f-triangular tensor.
Thus,

$\mathscr{A}_{1}*\mathscr{U}=\left(\mathscr{A}-\vec{\mathscr{U}}_{1}*\vec{\mathscr{U}}_{1}^{H}\right)*\mathscr{U}=\mathscr{U}*\mathscr{R}-\bm{\sigma}*\vec{\mathscr{U}}_{1}*\vec{\mathscr{E}}_{1}^{H}=\mathscr{U}*\left(\mathscr{R}-\bm{\sigma}*\vec{\mathscr{E}}_{1}*\vec{\mathscr{E}}_{1}^{H}\right),$

which is the desired result since
$\mathscr{R}-\bm{\sigma}*\vec{\mathscr{E}}_{1}*\vec{\mathscr{E}}_{1}^{H}$ is
an upper f-triangular tensor. ∎

Deflation can be applied multiple times using several vectors. For the matrix
case this is described in, e.g., [34, Chapter 4.2.3]. The techniques can be
adapted to the tensor case. We omit the details.

###  5.5 The tensor subspace iteration method

Subspace iteration is a powerful technique for computing a few eigenpairs with
the largest eigenvalues of a large matrix; see, e.g., [27, 34]. This section
describes the application of subspace iteration to the computation of a few
eigenpairs with the largest eigentubes of a large tensor
$\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$. The method is described by
Algorithm 5.

Algorithm 5 t-subspace iteration

Input: $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$,
$\mathscr{X}_{0}\in\mathbb{K}^{p\times s}_{n}$, integer $q>0$.
Output: Upper f-triangular tensor $\mathscr{R}\in\mathbb{K}^{s\times s}_{n}$
and an f-unitary tensor $\mathscr{U}\in\mathbb{K}^{p\times s}_{n}$ such that
$\mathscr{R}=\mathscr{U}^{H}*\mathscr{A}*\mathscr{U}$ contains the first $s$
eigentubes on its diagonal.

1: for $k=1,2,\ldots\leavevmode\nobreak\ $ until convergence do

2: $\mathscr{X}_{k}=\mathscr{A}^{q}*\mathscr{X}_{k-1}$

3: $\mathscr{X}_{k}=\mathscr{Q}_{k}*\mathscr{R}_{k}$

4: $\mathscr{X}_{k}=\mathscr{Q}_{k}$

5: end for

6: $\mathscr{U}=\mathscr{X}_{k}$,
$\mathscr{R}=\mathscr{U}^{H}*\mathscr{A}*\mathscr{U}$

The positive integer $q$ in line 2 of Algorithm 5 determines the number of
products with the tensor $\mathscr{A}$ in each iteration. A value $q>1$
reduces the number of t-QR factorizations required to achieve a given power of
$\mathscr{A}$ and, therefore, may speed up the computations. The t-QR
factorization of the tensor ${\mathscr{X}}_{k}\in\mathbb{K}^{p\times s}_{n}$
is computed in line 3 of Algorithm 5. The frontal slices of the tensor
${\mathscr{X}}_{k}\in\mathbb{K}^{p\times s}_{n}$ converge to the desired
eigenslices under suitable conditions described in the following theorem.

######  Theorem 33.

Let the eigentubes $\bm{\lambda}_{1},\bm{\lambda}_{2},\ldots,\bm{\lambda}_{n}$
of the tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$ satisfy

$\|\bm{\lambda}_{1}\|>\|\bm{\lambda}_{2}\|>\ldots>\|\bm{\lambda}_{m}\|>\|\bm{\lambda}_{m+1}\|\geq\|\bm{\lambda}_{m+2}\|\geq\ldots\geq\|\bm{\lambda}_{n}\|.$

Introduce
$\mathscr{Q}=[\vec{\mathscr{Q}}_{1},\ldots,\vec{\mathscr{Q}}_{m}]\in\mathbb{K}^{p\times
m}_{n}$, where $\vec{\mathscr{Q}}_{i}$ is the t-Schur lateral slice associated
with $\bm{\lambda}_{i}$, $1\leq i\leq m$, and let $\mathscr{P}_{i}$ denote the
spectral projector-tensor associated with
$\bm{\lambda}_{1},\ldots,\bm{\lambda}_{m}$, and let the initial iterate be
$\mathscr{X}_{0}=[\vec{\mathscr{X}}_{1},\ldots,\vec{\mathscr{X}}_{m}]\in\mathbb{K}^{p\times
m}_{n}$. Assume that

${\rm
rank}\left(\mathscr{P}_{i}*\left[\vec{\mathscr{X}}_{1},\ldots,\vec{\mathscr{X}}_{i}\right]\right)=i,\quad
i=1,2,\ldots,m.$

Then the the $\operatorname*{\text{span}_{t}}$ of the $i^{th}$ lateral slice
$\vec{\mathscr{X}}_{k,i}$ of $\mathscr{X}_{k}$ generated by Algorithm 5
converges to $\operatorname*{\text{span}_{t}}\\{\vec{\mathscr{Q}_{i}}\\}$.

###### Proof.

The proof is analogous to the matrix case; see Saad [34, Theorem 5.1] for the
latter. ∎

We remark that subspace iteration for matrices can be enhanced in a variety of
ways, e.g., by including projections and deflation; see Saad [34, Theorem
5.1]. Algorithm 5 can be enhanced similarly.

###  5.6 The t-QR algorithm for tensors

The QR algorithm is the default method for computing all eigenpairs of a
matrix of small to moderate size. A fairly recent discussion of the QR
algorithm for matrices with references is provided in, e.g., [23]. This
section describes an extension to the computation of eigenpairs of third-order
tensors. This extension is referred to as the t-QR algorithm.

The default QR algorithm used for matrix computation is fairly complicated: it
uses implicit shifts, and double shifts for real nonsymmetric matrices. In the
interest of brevity, we only discuss a basic version of the t-QR algorithm.
Details of a more efficient implementation that uses implicit and double
shifts will be described elsewhere.

The unshifted t-QR algorithm described by Algorithm 6 is not applied in
practice due to its slow convergence. Our interest in the algorithm stems from
that it is quite straightforward to show properties of the tensors it
computes. Analogous properties can be shown for the tensors determined by the
shifted algorithm discussed below.

Algorithm 6 The unshifted t-QR algorithm

Input: $\mathscr{A}_{0}=\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$.
Output: The eigentubes of $\mathscr{A}$.

1: for $k=1$ until the convergence do

2: Compute $\mathscr{A}_{k}=\mathscr{Q}_{k}*\mathscr{R}_{k}$

3: Compute $\mathscr{A}_{k+1}=\mathscr{R}_{k}*\mathscr{Q}_{k}$

4: end for

######  Proposition 34.

Let $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$. Then the tensors
$\mathscr{A}_{1},\mathscr{A}_{2},\ldots\leavevmode\nobreak\ $ generated by
Algorithm 6 satisfy

$\mathscr{A}_{k+1}=\left(\mathscr{Q}_{1}*\mathscr{Q}_{2}*\ldots*\mathscr{Q}_{k}\right)^{H}*\mathscr{A}*\left(\mathscr{Q}_{1}*\mathscr{Q}_{2}*\ldots*\mathscr{Q}_{k}\right).$
(10)

Moreover,

$\mathscr{A}^{k}=\left(\mathscr{Q}_{1}*\mathscr{Q}_{2}*\ldots*\mathscr{Q}_{k}\right)*\left(\mathscr{R}_{k}*\mathscr{R}_{k-1}*\ldots*\mathscr{R}_{1}\right),$
(11)

where the sequences $\\{\mathscr{Q}_{i}\\}_{i=1}^{k}$ and
$\\{\mathscr{R}_{i}\\}_{i=1}^{k}$ are defined by the t-QR factorization in
line 2 of Algorithm 6.

###### Proof.

Let $k\geq 1$. Then

$\begin{split}\mathscr{A}_{k+1}=\mathscr{R}_{k}*\mathscr{Q}_{k}&=\mathscr{Q}_{k}^{H}*\mathscr{Q}_{k}*\mathscr{R}_{k}*\mathscr{Q}_{k}=\mathscr{Q}_{k}^{H}*\mathscr{A}_{k}*\mathscr{Q}_{k}\\\
&=\mathscr{Q}_{k}^{H}*\mathscr{R}_{k-1}*\mathscr{Q}_{k-1}*\mathscr{Q}_{k}\\\
&=\mathscr{Q}_{k}^{H}*\mathscr{Q}_{k-1}^{H}*\mathscr{A}_{k-2}*\mathscr{Q}_{k-1}*\mathscr{Q}_{k}\\\
&=\left(\mathscr{Q}_{1}*\mathscr{Q}_{2}*\ldots*\mathscr{Q}_{k}\right)^{H}\mathscr{A}\left(\mathscr{Q}_{1}*\mathscr{Q}_{2}*\ldots*\mathscr{Q}_{k}\right),\end{split}$

which gives (10). On the other hand,

$\begin{split}\mathscr{A}^{k}&=\mathscr{Q}_{1}*\mathscr{R}_{1}*\ldots*\mathscr{Q}_{1}*\mathscr{R}_{1}\\\
&=\mathscr{Q}_{1}*\mathscr{Q}_{2}*\mathscr{R}_{2}*\ldots*\mathscr{Q}_{2}*\mathscr{R}_{2}*\mathscr{R}_{1}\\\
&=\left(\mathscr{Q}_{1}*\ldots*\mathscr{Q}_{k}\right)*\left(\mathscr{R}_{k}*\ldots*\mathscr{R}_{1}\right),\end{split}$

which shows (11). ∎

Eq. (10) shows that the tensor $\mathscr{A}_{k+1}\ $ is similar to
$\mathscr{A}$, while relation (11) provides a t-QR factorization of the tensor
$\mathscr{A}^{k}$. Letting

$\breve{\mathscr{Q}}_{k}=\mathscr{Q}_{1}*\mathscr{Q}_{2}*\ldots*\mathscr{Q}_{k}\;\text{and
}\;\breve{\mathscr{R}}_{k}=\mathscr{R}_{k}*\mathscr{R}_{k-1}*\ldots*\mathscr{R}_{1},$
(12)

we obtain

$\mathscr{A}_{k+1}=\breve{\mathscr{Q}}_{k}^{H}*\mathscr{A}_{k}*\breve{\mathscr{Q}}_{k}.$

Thus, the tensor $\mathscr{A}_{k+1}\ $ is f-unitarily similar to
$\mathscr{A}_{k}$.

The following result is concerned with the convergence of Algorithm 6.
Convergence is considered under special conditions, but can be shown under
less restrictive conditions as well.

######  Theorem 35.

Let $\mathscr{A}\in\mathbb{K}^{n\times n}_{p}$ be such that

$\mathscr{X}^{-1}*\mathscr{A}*\mathscr{X}=\bm{\Sigma}=\operatorname*{\text{t}-\mathop{\operator@font
diag}\nolimits}\left[\bm{\lambda}_{1},\bm{\lambda}_{2},\ldots,\bm{\lambda}_{n}\right],$

with

$\left\|\bm{\lambda}_{1}\right\|_{F}>\left\|\bm{\lambda}_{2}\right\|_{F}>\ldots>\left\|\bm{\lambda}_{n}\right\|_{F}>0,$
(13)

and assume that all entries of every tube $\bm{\lambda}_{k}$ are nonvanishing.
Let $\mathscr{X}^{-1}=\mathscr{L}*\mathscr{U}$ denote the t-LU factorization
of $\mathscr{X}^{-1}$, where $\mathscr{L}$ is a lower f-triangular tensor with
the elements e on its diagonal; we assume for notational simplicity that
pivoting is not required. Let $\mathscr{X}=\mathscr{Q}*\mathscr{R}$ be a t-QR
factorization. Then there is an invertible f-diagonal tensor
$\mathscr{D}_{k}$, such that $\breve{\mathscr{Q}}_{k}*\mathscr{D}_{k}^{-1}$
converges to $\mathscr{Q}$ as $k$ increases, where $\breve{\mathscr{Q}}_{k}$
is given by (12).

###### Proof.

We have

$\begin{split}\mathscr{A}^{k}=\mathscr{X}*\bm{\Sigma}^{k}*\mathscr{X}^{-1}&=\mathscr{Q}*\mathscr{R}*\bm{\Sigma}^{k}*\mathscr{L}*\mathscr{U}\\\
&=\mathscr{Q}*\mathscr{R}*\bm{\Sigma}^{k}*\mathscr{L}*\bm{\Sigma}^{-k}*\bm{\Sigma}^{k}*\mathscr{U},\end{split}$

and we note that the elements of
$\bm{\Sigma}^{k}*\mathscr{L}*\bm{\Sigma}^{-k}$ are given by

$\bm{\Sigma}^{k}*\mathscr{L}*\bm{\Sigma}^{-k}(i,j,:)=\begin{cases}\mathscr{L}(i,j,:)*\left(\bm{\lambda}_{i}/\bm{\lambda}_{j}\right)^{k}\;\;\text{if}\;i>j,\\\
\textbf{e}\;\;\text{if}\;i=j,\\\ \textbf{0}\;\;\text{otherwise}.\end{cases}$

Then by using the ordering (13) of the eigentubes, the tensor
$\bm{\Sigma}^{k}*\mathscr{L}*\bm{\Sigma}^{-k}$ converges to $\mathscr{I}$ as
$k$ increases. Thus, $\bm{\Sigma}^{k}*\mathscr{L}*\bm{\Sigma}^{-k}$ can be
written as $\mathscr{I}+\mathscr{E}_{k}$, where $\mathscr{E}_{k}\to\textbf{0}$
as $k$ increases.

Since $\mathscr{X}$ is invertible, $\mathscr{R}$ also is invertible. Therefore

$\begin{split}\mathscr{A}^{k}&=\mathscr{Q}*\mathscr{R}*\left(\mathscr{I}+\mathscr{E}_{k}\right)*\bm{\Sigma}^{k}*\mathscr{U}\\\
&=\mathscr{Q}*\left(\mathscr{I}+\mathscr{R}*\mathscr{E}_{k}*\mathscr{R}^{-1}\right)*\mathscr{R}*\bm{\Sigma}^{k}*\mathscr{U}.\end{split}$

Introduce the t-QR factorization
$\mathscr{Q}_{k}^{\prime}*\mathscr{R}^{\prime}_{k}=\mathscr{I}+\mathscr{R}*\bm{\Sigma}_{k}*\mathscr{R}^{-1}$.
Then

$\mathscr{A}^{k}=\mathscr{Q}*\mathscr{Q}_{k}^{\prime}*\mathscr{R}_{k}^{\prime}*\mathscr{R}*\bm{\Sigma}^{k}*\mathscr{U}.$

Let $\bm{\delta}_{1},\bm{\delta}_{2},\ldots,\bm{\delta}_{n}$ denote the
diagonal elements of the tensor
$\mathscr{R}_{k}^{\prime}*\mathscr{R}*\bm{\Sigma}^{k}*\mathscr{U}$. Since the
elements on the diagonals of the tensors $\mathscr{R}_{k}^{\prime}$,
$\mathscr{R}$, $\bm{\Sigma}^{k}$, and $\mathscr{U}$ are nonvanishing, it
follows that the tensor

$\mathscr{D}_{k}=\operatorname*{\text{t}-\mathop{\operator@font
diag}\nolimits}\left(\bm{\delta}_{1},\bm{\delta}_{2},\ldots,\bm{\delta}_{n}\right)\in\mathbb{K}^{n\times
n}_{p}$

is invertible. We therefore can write

$\mathscr{A}^{k}=\left(\mathscr{Q}*\mathscr{Q}_{k}^{\prime}*\mathscr{D}_{k}\right)*\left(\mathscr{D}_{k}^{-1}*\mathscr{R}_{k}^{\prime}*\mathscr{R}*\bm{\Sigma}^{k}*\mathscr{U}\right).$

Then, by using the properties of the t-QR factorization, we conclude that

$\breve{\mathscr{Q}}_{k}=\mathscr{Q}*\mathscr{Q}_{k}^{\prime}*\mathscr{D}_{k}.$

Moreover, since $\mathscr{Q}_{k}^{\prime}$ converges to $\mathscr{I}$ as $k$
increases, the tensor sequence

$\breve{\mathscr{Q}}_{k}*\mathscr{D}_{k}^{-1}=\mathscr{Q}*\mathscr{Q}_{k}^{\prime},\quad
k=1,2,\ldots\leavevmode\nobreak\ ,$

converges to $\mathscr{Q}$.

Since the lateral slices of the tensor $\mathscr{Q}$ are the t-Schur lateral
slices of $\mathscr{A}$, it follows that the scaled t-Schur lateral slices of
$\mathscr{A}_{k}$ ($\breve{\mathscr{Q}}_{k}$) with elements in
$\mathbb{K}_{p}$ converge to the lateral slices of $\mathscr{A}$
($\mathscr{Q}$) as $k$ increases. Consequently,
$\mathscr{A}_{k}=\breve{\mathscr{Q}}_{k}^{H}*\mathscr{A}*\breve{\mathscr{Q}}_{k}$
converges to the upper f-triangular tensor related to the t-Schur lateral
slices. ∎

The rate of convergence of Algorithm 6 can be accelerated by introducing
shifts, i.e., by replacing lines 2 and 3 of the algorithm by
$\mathscr{A}_{k}-\bm{\sigma}_{k}*\mathscr{I}_{p}=\mathscr{Q}_{k}*\mathscr{R}_{k}$
and
$\mathscr{A}_{k+1}=\mathscr{R}_{k}*\mathscr{Q}_{k}+\bm{\sigma}_{k}*\mathscr{I}_{p}$,
respectively, for suitable tubal shifts $\bm{\sigma}_{k}$. Moreover, the
computational cost of each iteration can be reduced by first transforming
$\mathscr{A}_{0}$ to f-upper-Hessenberg form. These modifications are
described by Algorithm 7.

Algorithm 7 A shifted t-QR algorithm with f-Hessenberg reduction

Input: $\mathscr{A}_{0}=\mathscr{A}\in\mathbb{R}^{p\times p}_{n}$, a shift
tube $\bm{\sigma}\in\mathbb{K}_{n}$, $r=p$, $\epsilon>0$.
Output: The eigentubes of $\mathscr{A}$.

1: $[\mathscr{P},\mathscr{H}_{0}]={\tt t-hess}(\mathscr{A}_{0})$, with
$\mathscr{P}*\mathscr{H}_{0}*\mathscr{P}^{H}=\mathscr{A}_{0}$

2: for $r>1$ until convergence do

3:
$\mathscr{H}_{k}-\bm{\sigma}*\mathscr{I}_{p}=\mathscr{Q}_{k}*\mathscr{R}_{k}$
(Compute QR factorization)

4:
$\mathscr{A}_{k+1}=\mathscr{R}_{k}*\mathscr{Q}_{*}+\bm{\sigma}*\mathscr{I}_{p}$

5: if $\left\|\mathscr{A}_{k+1}(r,r-1,:)\right\|_{F}\leq\epsilon$ then

6: $r=r-1$

7: end if

8: end for

One way to determine suitable shifts $\bm{\sigma}$ is to let the shift in each
iteration be $\mathscr{A}_{k}(r,r,:)$. We should mention that sometimes we
need to reorder the tubes $\mathscr{A}_{k+1}(j,j-1,:)$, $j=2,3,\ldots,r$,
determined in each iteration of Algorithm 7 before determining the shift. This
issue will be discussed in detail elsewhere.

##  6 Numerical experiments

This section illustrates the performance of the algorithms discussed in the
previous section. The purpose of the examples is to demonstrate that the
methods work similarly as the analogous methods for matrices. We used the
following tensors in our experiments: The first tensor is of size $10\times
10\times 3$ and has the frontal slices

$\mathscr{A}(:,:,i)=\delta_{i}\;{\tt tridiag}(-1,2,-1),$

with $\delta_{i}=10^{i-1}$ for $1\leq i\leq 3$. The second tensor in our
experiments is the stochastic tensor $\mathscr{C}\in\mathbb{K}^{4\times
4}_{4}$ with frontal slices

$\mathscr{C}(:,:,1)=\begin{pmatrix}0.2091&0.2834&0.2194&0.1830\\\
0.3371&0.3997&0.3219&0.3377\\\ 0.3265&0.0560&0.3119&0.2961\\\
0.1273&0.2608&0.1468&0.1832\end{pmatrix},\;\mathscr{C}(:,:,2)=\begin{pmatrix}0.1952&0.2695&0.2055&0.1690\\\
0.3336&0.3962&0.3184&0.3342\\\ 0.2954&0.0249&0.2808&0.2650\\\
0.1758&0.3094&0.1953&0.2318\end{pmatrix},$
$\mathscr{C}(:,:,3)=\begin{pmatrix}0.3145&0.3887&0.3248&0.2883\\\
0.0603&0.1230&0.0451&0.0609\\\ 0.3960&0.1255&0.3814&0.3656\\\
0.2293&0.3628&0.2487&0.2852\end{pmatrix},\;\mathscr{C}(:,:,4)=\begin{pmatrix}0.1686&0.2429&0.1789&0.1425\\\
0.3553&0.4180&0.3402&0.3559\\\ 0.3189&0.0484&0.3043&0.2885\\\
0.1571&0.2907&0.1766&0.2131\end{pmatrix}.$

We also used the tensor ${\tt complex}(10,10,10)\in\mathbb{K}^{10\times
10}_{10}$, whose entries have normally distributed real and imaginary parts
with mean zero and variance one, as well as the real tensor ${\tt
real}(10,10,10)$, whose entries are normally distributed with mean zero and
variance one, and with real eigentubes. Table 1 lists the abbreviations of the
algorithms used in the experiments.

Method | Abbreviation | Algorithm
---|---|---
t-power method | t-PM |  Algorithm 3
shifted inverse t-power method | t-SIPM |  Algorithm 4
t-deflation method | t-DM |
t-subspace iteration | t-SI |  Algorithm 5
t-QR algorithm with f-Hessenberg reduction and shifts | t-QRHS |  Algorithm 7
Table 1: Abbreviations for the algorithms used in the experiments.

Let the diagonal entries of the f-diagonal tensor
$\mathscr{D}_{k}\in\mathbb{K}^{k\times k}_{n}$ be the exact eigentubes of the
tensors considered, and let the diagonal entries of the f-diagonal tensor
$\widetilde{\mathscr{D}}_{k}\in\mathbb{K}^{k\times k}_{n}$ contain the
corresponding approximations computed by the methods. We report the error

$\text{Error}=\|\widetilde{\mathscr{D}_{k}}-\mathscr{D}_{k}\|_{F}.$ (14)

All computations were carried out on a laptop computer with an 2.3 GHz Intel
Core i5 processor and 8 GB of memory using MATLAB 2018a.

###  6.1 The tensor t-power method and the inverse t-power method

This subsection shows the performance of the t-power method and the closely
related inverse t-power method. These methods are implemented by Algorithms 3
and 4. The t-power method determines an approximation of the eigenpair with
the eigentube of largest norm, while the inverse t-power method computes an
approximation of the eigenpair with the eigentube closest to a specified tubal
shift.

We first consider the t-power method. Generically, Algorithms 3 determines a
sequence $\\{\vec{\mathscr{V}}_{k}\\}_{k\geq 1}$ of approximations of an
eigenslice that is associated with the eigentube of largest norm, as well of
the sequence $\\{\bm{\alpha}_{k}\\}_{k\geq 1}$ of approximations of the
largest eigentube; see Theorem 30. We will use the stopping criterion

$\|\vec{\mathscr{V}}_{k+1}-\vec{\mathscr{V}}_{k}\|_{F}\leq\text{tol},\;\text{and}\;\;\left\|\bm{\alpha}_{k+1}-\bm{\alpha}_{k}\right\|_{F}\leq\text{tol},$

where we set $\text{tol}=10^{-15}$ in our tests and allow at most
$\text{Itermax}=3000$ iterations. The initial lateral slice
$\vec{\mathscr{V}}_{0}$ is chosen to have normally distributed entries; the
entries are chosen to be real if the tensor is real and the desired eigenslice
is real; otherwise $\vec{\mathscr{V}}_{0}$ is complex with entries that have
normally distributed real and imaginary parts. Let
$\\{\vec{\mathscr{U}},\bm{\lambda}\\}$ denote the computed approximation of
the desired eigenpair of a tensor $\mathscr{F}\in\mathbb{K}^{p\times p}_{n}$.
Then we evaluate the residual error norm

$\text{Res.norm}=\|\mathscr{F}*\vec{\mathscr{U}}-\vec{\mathscr{U}}*\bm{\lambda}\|_{F}.$

. Table 2 reports some computed results. As can be expected, the t-power
method may require many iterations to satisfy the convergence criterion.

Tensor | Method | Res.norm | Error | Iter | CPU time
---|---|---|---|---|---
$\mathscr{A}$ | t-PM | 2.14e-15 | 2.27e-15 | 537 | 0.382
$\mathscr{C}$ | t-PM | 3.70e-14 | 1.06e-14 | 2035 | 0.886
${\tt complex(10,10,10)}$ | t-PM | 3.47e-14 | 2.56e-14 | 849 | 0.707
Table 2: Residual norm, Error, number of iterations, and CPU time for t-PM.

The inverse t-power method is implemented by Algorithm 4 with a stopping
criterion that is analogous to the one for Algorithm 3. Here we seek to
determine the eigenslice associated with the eigentube closest to the tubal
shift $\bm{\sigma}$. The shifts $\bm{\sigma}$ used for for the tensors
$\mathscr{A}$ and ${\tt complex(10,10,10)}$ are the tube with
$\bm{\sigma}(1,1,1)=10^{-5}$ and remaining entries zero, and the tube with
$\bm{\sigma}(1,1,1)=10^{-3}$ and remaining entries zero, respectively.

Tensor | Method | Res. norm | Error | Iter
---|---|---|---|---
$\mathscr{A}$ | t-SIPM | 3.81e-15 | 2.91e-16 | 32
${\tt complex(10,10,10)}$ | t-SIPM | 4.33e-16 | 6.65e-15 | 422
Table 3: Residual norm, Error, and number of iterations for t-SIPM.

###  6.2 Deflation

We examine the performance of the previously discussed deflation techniques in
order to approximate more than one eigenpair. Recall that the deflation
methods differ in how we choose the lateral slice $\vec{\mathscr{V}}$; see
(9). We choose $\vec{\mathscr{V}}$ as the $i^{th}$ eigenslice (DE), as the
$i^{th}$ t-Schur lateral slice (DS), or as the $i^{th}$ left eigenslice (DLE),
and we report the results using DE, DS, and DLE methods for the tensors
$\mathscr{A}$ and ${\tt real}\left(10,10,10\right)$. To approximate the
$i^{th}$ eigentube, with $i>1$, we apply the power method to the new tensor
$\mathscr{A}_{i}=\mathscr{A}_{i-1}-\bm{\lambda}_{i}*\vec{\mathscr{U}}_{i}*\vec{\mathscr{V}}_{i}^{H},$
where $\mathscr{A}_{1}=\mathscr{A}$, $\bm{\lambda}_{i}$ is the previous
approximated eigentube and $\vec{\mathscr{V}}_{i}$ is chosen as the previously
approximated eigenslice (for the DE method) or as the left eigenslice (for the
DLE method). We choose
$\mathscr{A}_{i}=\mathscr{A}_{i-1}-\bm{\lambda}_{i}*\vec{\mathscr{Q}}_{i}*\vec{\mathscr{Q}}_{i}^{H},$
where $\vec{\mathscr{Q}}_{i}$ is the $i^{th}$ t-Schur lateral slice, when
applying the DS method. We approximate the first $k$ eigenpairs of a given
tensor $\mathscr{F}\in\mathbb{K}^{p\times p}_{n}$ and evaluate the residual
norm

$\text{Res.norm}=\|\mathscr{F}*\mathscr{U}_{k}-\mathscr{U}_{k}*\mathscr{D}_{k}\|_{F},$

where $\mathscr{U}_{k}\in\mathbb{K}^{p\times k}_{n}$ contains computed
approximations of the eigenslices associated with the first eigentubes of
$\mathscr{F}$, and $\mathscr{D}_{k}\in\mathbb{K}^{k\times k}_{n}$ is an
f-diagonal tensor which on its diagonal has the computed approximations of the
first $k$ eigentubes of $\mathscr{F}$.

Table 4 reports the Error and the residual norm when approximating several
eigentubes of the tensors $\mathscr{A}$ and ${\tt real}(10,10,10)$ by the DE,
DS, and DLE methods. Our aim is to approximate Num¿1 eigentubes of the tensor.

Tensor | Num | DE | DLE | DS
---|---|---|---|---
Error | Res. norm | time | Error | Res. norm | time | Error | Res. norm | time
$\mathscr{A}$ | 3 | 4.58e-15 | 7.13e-15 | 0.675 | 4.19e-15 | 7.51e-15 | 1.237 | 4.57e-15 | 3.27e-15 | 0.668
5 | 4.79e-15 | 6.87e-15 | 0.975 | 4.58e-15 | 7.63e-15 | 1.408 | 4.83e-15 | 3.43e-15 | 0.840
${\tt real}(10,10,10)$ | 4 | 8.06e-13 | 2.44e-13 | 0.642 | 8.09e-13 | 2.63e-13 | 1.246 | 8.19e-13 | 2.54e-13 | 0.641
6 | 8.10e-13 | 2.98e-13 | 1.279 | 8.30e-13 | 2.91e-13 | 1.955 | 8.21e-13 | 3.08e-13 | 1.018
Table 4: The Error, the residual norm, and the CPU time of DE, DS, and DLE
methods, when applied to the tensors $\mathscr{A}$ and ${\tt
real}\left(10,10,10\right)$ to approximate Num eigentubes.

Table 4 shows deflation with DS shifts to be faster than deflation with DE or
DLE shifts. Figure 1 illustrates the convergence behavior for each eigenpair.
We can see that the number of iterations required is the same for each
eigenpair for all shifts DE, DEL, and DS.

|  |
---|---|---
Figure 1: The behavior of the residual norm when we aimed approximate the
first three eigenpairs of the tensor ${\tt real}\left(10,10,10\right)$, by the
methods DE, DLE, and DS, from the left to the right.

###  6.3 Tensor subspace iteration

This subsection illustrates the performance of the t-subspace iteration method
when applied to approximate eigenslices associated with the $m$ eigentubes of
largest norm of a tensor $\mathscr{A}\in\mathbb{K}^{p\times p}_{n}$. The
sequence of approximate eigenslices $\\{\mathscr{X}_{k}\\}_{k\geq 1}$
generated by Algorithm 5 generically converges to the
$\operatorname*{\text{span}_{t}}$ of the t-Schur lateral slices associated
with the $m$ largest eigentubes. Thus, the tensors

$\mathscr{R}_{k}=\mathscr{X}_{k}^{H}*\mathscr{A}*\mathscr{X}_{k},\quad
k=1,2,\ldots\leavevmode\nobreak\ ,$

converge to an f-upper triangular tensor. This suggests the convergence
criterion

$\text{error}(k)={\tt
t\text{-}tril}\left(\mathscr{R}_{k+1}-\mathscr{R}_{k}\right)\leq\text{tol},$
(15)

where the function ${\tt t\text{-}tril}$ returns the f-lower triangular
portion of its tensor argument. The tolerance used in all the experiments with
the t-subspace method is $\text{tol}=10^{-15}$, and the maximum number of
iterations is set to $\text{Itermax}=3000$. The initial tensor
$\mathscr{X}_{0}$ has random entries chosen similarly as for the experiments
with the t-power method.

To approximate the first $m$ eigentubes, we compute the residual norm
associated with the third-order tensor $\mathscr{F}\in\mathbb{K}^{p\times
p}_{n}$,

$\text{Res.norm}=\|\mathscr{F}*\mathscr{U}_{m}-\mathscr{U}_{m}*\mathscr{R}_{m}\|_{F},$
(16)

where $\mathscr{U}_{m}\in\mathbb{K}^{p\times m}_{n}$ is made up of computed
approximations the t-Schur lateral slices associated the $m$ largest
eigentubes of $\mathscr{F}$, and $\mathscr{R}_{m}\in\mathbb{K}^{m\times
m}_{n}$ is an upper (or quasi-upper) f-triangular tensor, whose f-diagonal
entries are approximations of the $m$ largest eigentubes of $\mathscr{F}$.

Table 5 displays the computed results. We notice that t-MSI is the same as
t-SI when the power index $q$ is $1$. Figure 2 shows plots of the error (15)
and of the residual norm at each iteration when seeking to approximate the
four first eigentubes of the tensor ${\tt complex}(10,10,10)$ for the power
indices $q\in\\{1,4,6\\}$. Table 5 indicates that increasing the power index
$q$ has no effect on the accuracy, but reduces the total number of iterations.

Tensor | $q$ | Error | Res.norm | Iter | CPU time
---|---|---|---|---|---
$\mathscr{A}$ | 1 | 4.58e-15 | 2.62e-15 | 490 | 0.288
4 | 4.58e-15 | 2.36e-15 | 129 | 0.137
${\tt complex}(10,10,10)$ | 1 | 7.40e-11 | 2.10e-14 | 3000 | 2.775
4 | 9.45e-14 | 2.40e-14 | 956 | 1.090
Table 5: The values of the Error, the residual norm, the number of iterations, and the CPU time for different values of the power index $q$ obtained when using t-MSI for computing the first four eigentubes. |
---|---
Figure 2: The curves representing the evolution of the error and the residual
norm for algorithm t-MSI with different values of the power index
$q\in\\{1,4,6\\}$ applied to the tensor ${\tt complex}\left(10,10,10\right)$,
when we desire approximations of the first four eigentubes.

Figure 2 depicts the error norm and the residual norm for the t-MSI algorithm
for the values $1,\;4,\;6$ of the power index $q$. The results show fast
convergence.

###  6.4 The t-QR algorithm

This subsection considers the t-QR algorithm t-QRHS. The algorithm is applied
to the tensors $\mathscr{A}$ and $\mathscr{C}$. The tolerance is set to
machine epsilon $2.2204\;10^{-16}$; the maximum number of iterations allowed
for Algorithm7 is $\text{Itermax}=30000$. We compute the residual norm defined
by expression (16).

Table 6 reports the error norm (14), the residual norm, the CPU time, and the
number of iterations required to satisfy the stopping criterion of the t-QRHS
algorithm. The shifts have already been discussed after Algorithm 7, but since
the last two eigentubes of the tensor $\mathscr{C}$ are complex, we used in
each iteration the shift
$\bm{\sigma}=\mathscr{H}_{k}(r,r,:)+i\mathscr{H}_{k}(r,r,:)$ for this tensor.

Tensor | Method | Error | Res.norm | CPU time | Iter
---|---|---|---|---|---
$\mathscr{A}$ | t-QRHS | 1.3984e-14 | 1.5373e-14 | 0.169 | 61
$\mathscr{C}$ | t-QRHS | 9.0322e-15 | 4.5962e-15 | 0.232 | 128
Table 6: The Error, the residual norm, the CPU time, and the number of
iterations needed for convergence of t-QRHS when applied to the tensors
$\mathscr{A}$ and $\mathscr{C}$.

##  7 Conclusion and extensions

This work describes generalizations of eigenvalues and eigenvectors, referred
to as eigentubes and eigenslices, respectively, for third-order tensors using
the t-product. Some properties of eigentubes and eigenslices are shown, and
several methods for computing eigentubes and eigenslices are presented
including the t-power method, the t-inverse iteration method, and t-subspace
iteration, as well as the t-QR algorithm. We also introduce deflation methods.
Numerical tests illustrate the performance of these methods.

## References

  * [1] S. Aeron, E. Kernfeld, M. Kilmer, Tensor-tensor products with invertible linear transforms, Linear Algebra Appl., 485, 545–570 (2015).
  * [2] H. Avron, L. Horesh, M. E. Kilmer, E. Newman, Tensor-tensor algebra for optimal representation and compression of multiway data, Proceedings of the National Academy of Sciences, National Acad Sciences, 188, 28 e2015851118 (2021).
  * [3] B. W. Bader, T. Kolda, Tensor decompositions and applications, SIAM Rev., 51, 455–500 (2009).
  * [4] F. P. A. Beik, M. Najafi-Kalyani, L. Reichel, Iterative Tikhonov regularization of tensor equations based on the Arnoldi process and some of its generalizations, Appl. Numer. Math., 151, 425–447 (2020).
  * [5] A. H. Bentbib, M. Boubekraoui, K. Jbilou, Vector Aitken extrapolation method for multilinear PageRank computations, J. Appl. Math. Comput., 1–28 (2022).
  * [6] A. H. Bentbib, A. El Hachimi, K. Jbilou, A. Ratnani, A tensor regularized nuclear norm method for image and video completion, J. Optim. Theory Appl., 192, 401–425, (2022).
  * [7] A. H. Bentbib, A. El Hachimi, K. Jbilou, A. Ratnani, Fast multidimensional completion and principal component analysis methods via the cosine product, Calcolo, 59, 1–33, (2022).
  * [8] A. H. Bentbib, A. Khouia, H. Sadok, The LSQR method for solving tensor least-squares problems, Electron. Trans. Numer. Anal., 55, 92–111, (2022).
  * [9] A. H. Bentbib, A. Khouia, H. Sadok, Color image and video restoration using tensor CP decomposition, BIT Numer. Math., 62, 1257–1278 (2022);
  * [10] S. Brin and L. Page, The anatomy of a large-scale hypertextual web search engine, Comput. Networks ISDN Systems, 30, 107–117 (1998).
  * [11] C. Bu, L. Sun, Y. Wei, B. Zheng, Moore–Penrose inverse of tensors via Einstein product, Linear and Multilinear Algebra, 64, 4, 686–698 (2016).
  * [12] Z. Chen, C. Li, S. Li, J. Zhao, Eigenvalue bounds of third-order tensors via the minimax eigenvalue of symmetric matrices, Comput. Appl. Math., 39, 1–14 (2020).
  * [13] S. Cipolla, M. Redivo-Zaglia, F. Tudisco, Shifted and extrapolated power methods for tensor $\ell^{p}$-eigenpairs, Electron. Trans. Numer. Anal., 53, 1–27 (2020).
  * [14] M. Ding, T. -Z. Huang, T. -Y. Ji, X. -L. Zhao, J. -H. Yang, Low-rank tensor completion using matrix factorization based on tensor train rank and total variation, J. Sci. Comput., 81, 941–964 (2019).
  * [15] F. Dufrenois, A. El Ichi, K. Jbilou, Multilinear discriminant analysis using tensor-tensor products, J. Math. Modeling, in press.
  * [16] M. El Guide, A. El Ichi, K. Jbilou, R. Sadaka. On tensor GMRES and Golub-Kahan methods via the t-product for color image processing, Electron. J. Linear Algebra, 37, 524–543 (2021).
  * [17] M. El Guide, A. El Ichi, K. Jbilou, F. P. A. Beik, Tensor Krylov subspace methods via the Einstein product with applications to image and video processing, Appl. Numer. Math., 181, 347–363 (2022).
  * [18] A. El Hachimi, K. Jbilou, A. Ratnani, L. Reichel, A tensor bidiagonalisation method for higher-order singular value decomposition with applications, submitted for publication.
  * [19] S. El-Halouy, S. Noschese, L. Reichel, Perron communicability and sensitivity of multilayer networks, Numer. Algorithms, 92, 597–617 (2023).
  * [20] M. El Guide, A. El Ichi, K. Jbilou, Discrete cosine transform LSQR methods for multidimensional ill-posed problems, J. Math. Model., 10, 21–37 (2022).
  * [21] D. F. Gleich, L.-H. Lim, Y. Yu, Multilinear pagerank, SIAM J. Matrix Anal. Appl., 36, 1507–1541 (2015).
  * [22] G. H. Golub, H. A. Van der Vorst, Eigenvalue computation in the 20th century, J. Comput. Appl. Math., 123, 35–65, (2000).
  * [23] G. H. Golub, C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, Baltimore, 2013.
  * [24] P. Henrici, Applied and Computational Complex Analysis, vol. 3, Wiley, New York, 1986.
  * [25] M. E. Kilmer, K. Braman, N. Hao, R. C. Hoover, Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging, SIAM J. Matrix Anal. Appl., 34, 148–172 (2013).
  * [26] M. E. Kilmer, C. D. Martin, Factorization strategies for third-order tensors, Linear Algebra Appl., 435, 641–-658 (2011).
  * [27] R. Lehoucq, J. A. Scott, An evaluation of subspace iteration software for sparse nonsymmetric eigenproblems, SCAN-9605011, (1996).
  * [28] C. D. Martin, R. Shafer, B. LaRue, An order-$p$ tensor factorization with applications in imaging, SIAM J. Sci. Comput., 35, A474–A490 (2013).
  * [29] L. Qi, Z. Luo, Tensor Analyis: Spectral Thoery and Special Tensors, SIAM, Philadelphia, 2017\.
  * [30] L. Reichel, U. O. Ugwu, Tensor Arnoldi-Tikhonov and GMRES-type methods for ill-posed problems with a t-product structure, J. Sci. Comput., 90, Art. 59, (2022).
  * [31] L. Reichel, U. O. Ugwu, The tensor Golub-Kahan-Tikhonov method applied to the solution of ill-posed problems with a t-product structure, Numer. Linear Algebra Appl., 29, Art e2412 (2022).
  * [32] L. Reichel, U. O. Ugwu, Weighted tensor Golub-Kahan-Tikhonov-type methods applied to image processing using a t-product, J. Comput. Appl. Math., 415, Art. 114488 (2022).
  * [33] H. Rojo, O. Rojo, Some results on symmetric circulant matrices and on symmetric centrosymmetric matrices, Linear Algebra Appl., 391, 211–233 (2004).
  * [34] Y. Saad, Numerical Methods for Large Eigenvalue Problems, 2nd ed., SIAM, Philadelphia, 2011\.
  * [35] R. v. Mises, H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflösung, ZAMM, 9, 152–164 (1929).