Abstract
This paper describes solution methods for linear discrete ill-posed problems defined by third order tensors and the t-product formalism introduced in (Linear Algebra Appl 435:641–658, 2011). A t-product Arnoldi (t-Arnoldi) process is defined and applied to reduce a large-scale Tikhonov regularization problem for third order tensors to a problem of small size. The data may be represented by a laterally oriented matrix or a third order tensor, and the regularization operator is a third order tensor. The discrepancy principle is used to determine the regularization parameter and the number of steps of the t-Arnoldi process. Numerical examples compare results for several solution methods, and illustrate the potential superiority of solution methods that tensorize over solution methods that matricize linear discrete ill-posed problems for third order tensors.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
We are concerned with the solution of large-scale least squares problems of the form
where \({\mathcal {A}} = [a_{ijk}]_{i,j,k=1}^{m,m,n}\in {\mathbb {R}}^{m\times m\times n}\) is a third order tensor of ill-determined tubal rank, i.e., the Frobenius norm of the singular tubes of \({\mathcal {A}}\), which are analogues of the singular values of a matrix, decay rapidly to zero with increasing index, and there are many nonvanishing singular tubes of tiny Frobenius norm of different orders of magnitude (cf. Definition 2.2 below). Least squares problems with a tensor of this kind are referred to as linear discrete ill-posed problems. The tensors \(\mathcal {\mathbf {X}}\in {\mathbb {R}}^{m\times 1\times n}\) and \(\mathcal {\mathbf {B}}\in {\mathbb {R}}^{m\times 1\times n}\) in (1.1) are laterally oriented \(m \times n\) matrices, and the operator \(*\) denotes the tensor t-product introduced in the seminal work by Kilmer and Martin [23]. We will review the t-product in Sect. 2.
An advantage of the formulation (1.1) with the t-product, when compared to other products, is that the t-product avoids loss of information inherent in the flattening of a tensor; see Kilmer et al. [22]. The t-product preserves the natural ordering and higher correlations embedded in the data, and has been found useful in many application areas, including completion of seismic data [11], image deblurring problems [10, 22, 23, 35], facial recognition [18], tomographic image reconstruction [40], and tensor compression [42].
Throughout this paper, \(\Vert \cdot \Vert _F\) denotes the Frobenius norm of a third order tensor, which for \({\mathcal {A}} = [a_{ijk}]_{i,j,k=1}^{m,m,n}\in {\mathbb {R}}^{m\times m\times n}\) is defined by
In applications of interest to us, such as image and video restoration, the data tensor \(\mathcal {\mathbf {B}} \in {\mathbb {R}}^{m \times 1 \times n}\) is contaminated by measurement error (noise) that is represented by a tensor \(\mathcal {\mathbf {E}}\in {\mathbb {R}}^{m\times 1\times n}\). Thus,
where \(\mathcal {\mathbf {B}}_\text {true} \in {\mathbb {R}}^{m \times 1 \times n}\) represents the unavailable error-free data tensor that is associated with the known data tensor \(\mathcal {\mathbf {B}}\). We assume the unavailable linear system of equations
to be consistent and let \(\mathcal {\mathbf {X}_\text {true}}\) denote its (unknown) solution of minimal Frobenius norm.
We would like to compute an accurate approximation of \(\mathcal {\mathbf {X}_\text {true}}\). Straightforward solution of (1.1) typically does not yield a meaningful approximation of \(\mathcal {\mathbf {X}}_\text {true}\), because due to the severe ill-conditioning of \({\mathcal {A}}\), the error in \(\mathcal {\mathbf {B}}\) gives rise to a large propagated error in the computed solution. We remedy this difficulty by replacing (1.1) by a nearby problem, whose solution is less sensitive to perturbations of the right-hand side \(\mathcal {\mathbf {B}}\), i.e., we solve the penalized least squares problem
where \({\mathcal {L}}\in {\mathbb {R}}^{s\times m\times n}\) is a regularization operator and \(\mu >0\) is a regularization parameter. This replacement is commonly referred to as Tikhonov regularization. Let \({\mathcal {N}}({\mathcal {M}})\) denote the null space of the tensor \({\mathcal {M}}\) under \(*\) and assume that \({\mathcal {L}}\) satisfies
where \(\mathcal {\mathbf {O}}\) denotes an \(m \times n\) zero matrix oriented laterally; see below. Then (1.3) has a unique solution \(\mathcal {\mathbf {X}}_\mu \in {\mathbb {R}}^{m\times 1\times n}\) for any \(\mu >0\) (cf. Theorem 3.1). The closeness of \(\mathcal {\mathbf {X}}_\mu \) to \(\mathcal {\mathbf {X}}_\text {true}\) and the sensitivity of \(\mathcal {\mathbf {X}}_\mu \) to the error \(\mathbf {E}\) in \(\mathbf {B}\) depends on the value of \(\mu \). We determine \(\mu \) by the discrepancy principle, which is described and analyzed in, e.g., [12]. Application of the discrepancy principle requires that a bound
be available. The parameter \(\mu >0\) then is determined so that \(\mathcal {\mathbf {X}}_\mu \) satisfies
where \(\eta >1\) is a user-specified constant independent of \(\delta >0\). It can be shown that \(\mathcal {\mathbf {X}}_\mu \rightarrow \mathcal {\mathbf {X}}_\text {true}\) as \(\delta \searrow 0\); see [12] for a proof in a Hilbert space setting.
Many other methods, including generalized cross validation (GCV) and the L-curve criterion, also can be used to determine the regularization parameter; see, e.g., [5, 13, 15, 16, 24, 25, 36] for discussions and illustrations for the situation when \({\mathcal {A}}\) is a matrix and \(\mathcal {\mathbf {B}}\) is a vector.
It is well known that a few steps of the (standard) Arnoldi process can be used to reduce a large square matrix to a matrix of small size. The small matrix so obtained can be used to define a small Tikhonov regularization problems that is easy to solve; see [5, 7, 14, 27] for discussions and illustrations. It is the purpose of the present paper to extend the (standard) matrix version of the Arnoldi process, described, e.g., in [37], to third order tensors using the t-product formalism. This gives us the t-Arnoldi process. Application of \(\ell \ge 1\) steps of this process, generically, furnishes an orthonormal basis for the \(\ell \)-dimensional tensor Krylov (t-Krylov) subspace
The meaning of t-span is discussed in Sects. 3 and 4. Each step of the t-Arnoldi process requires one tensor-matrix product evaluation with \({\mathcal {A}}\). Often fewer tensor-matrix product evaluations are required to solve Tikhonov minimization problems (1.3) than when the t-product Golub-Kahan bidiagonalization (tGKB) process, described by Kilmer et al. [22] is used, because each step of the latter demands two tensor-matrix product evaluations, one with \({\mathcal {A}}\) and one with \({\mathcal {A}}^T\), where the superscript \(^T\) denotes transposition.
We refer to our solution scheme for (1.3) as the t-product Arnoldi–Tikhonov (tAT) regularization method. It is based on reducing the tensor \({\mathcal {A}}\in {\mathbb {R}}^{m\times m\times n}\) to a small upper Hessenberg tensor. We also describe a global tAT (G-tAT) method for the solution of (1.3). This method works with a data tensor slice \(\mathcal {\mathbf {B}}\in {\mathbb {R}}^{m\times 1\times n}\) and is closely related to the T-global Arnoldi–Tikhonov regularization method recently described by El Guide et al. [10], which takes \({\mathcal {L}}\) equal to the identity tensor, denoted by \({\mathcal {I}}\), determines the regularization parameter by the GCV method, and works with a general data tensor \({\mathcal {B}}\in {\mathbb {R}}^{m\times p\times n}\), \(p>1\). Differently from the tAT method, the G-tAT and the T-global Arnoldi–Tikhonov regularization methods involve matricization of the tensor \({\mathcal {A}}\). Specifically, the G-tAT method first reduces \({\mathcal {A}}\) in (1.3) to an upper Hessenberg matrix by carrying out a few steps of the global t-Arnoldi (G-tA) process. This process furnishes an orthonormal basis for a t-Krylov subspace (1.7). It differs from the t-Arnoldi process in the choice of inner product. Algorithm 13 in Sect. 5 provides the details of the G-tA process. Numerical examples with the t-Arnoldi and G-tA processes are presented in Sect. 6. The tAT and G-tAT methods based on these processes determine the regularization parameter by the discrepancy principle.
We also describe an extension of the (standard) generalized minimal residual (GMRES) method proposed by Saad and Schultz [38] to third order tensors based on the t-product formalism. This extension will be referred to as the t-product GMRES (tGMRES) method. The tGMRES method for the solution of (1.1) computes iterates in t-Krylov subspaces of the form (1.7); the \(\ell \)th approximate solution \(\mathcal {\mathbf {X}}_\ell \in {\mathbb {K}}_\ell ({\mathcal {A}},\mathcal {\mathbf {B}})\) determined by tGMRES method with initial approximate solution \(\mathcal {\mathbf {X}}_0=\mathcal {\mathbf {O}}\) satisfies
Another extension of the (standard) GMRES method by Saad and Schulz [38] for the solution of tensor equations is provided by the global tGMRES (G-tGMRES) method, which is described in Sect. 5.2. This method is closely related to the T-global GMRES method recently presented by El Guide et al. [10]. The methods differ in that the data for the G-tGMRES method is represented by a lateral slice \(\mathcal {\mathbf {B}}\), while the data for the T-global GMRES method is a general third order tensor \({\mathcal {B}}\in {\mathbb {R}}^{m\times p\times n}\), \(p>1\). Moreover, our implementation of the t-GMRES and G-tGMRES methods uses the discrepancy principle to determine when to terminate the iterations. Differently from the tGMRES method, the G-tGMRES and T-global GMRES methods involve matricization of the tensor \({\mathcal {A}}\). While the tGMRES method is based on the t-Arnoldi process described in Sect. 3, the G-tGMRES method is based on the global t-Arnoldi (G-tA) process.
Many other methods for solving (1.3) and (1.8) that do not apply the t-product have been described in the literature; see, e.g., [2, 8, 9, 39]. These methods replace matrix-vector products by tensor-matrix products and involve matricization. A careful comparison of all these methods is outside the scope of the present paper. Here we note that computed examples of Sect. 6 indicate that methods that avoid matricization often determine approximate solutions of higher quality than methods that involve matricization.
We also are interested in solving minimization problems analogous to (1.1), in which \(\mathcal {\mathbf {B}}\) is replaced by a general third order tensor \({\mathcal {B}}\). This leads to the Tikhonov minimization problem
Besides our work [35], no literature is available on solution methods for (1.3) and (1.9) for \(\mathcal {L \ne I}\). The present paper focuses on developing tensor Arnoldi–Tikhonov-type methods for this situation.
Four methods for the solution of (1.9) will be described. Three of them are based on the tAT and G-tAT methods applied to the lateral slices \(\mathcal {\mathbf {B}}_j\), \(j=1,2,\dots ,p\), of \({\mathcal {B}}\), independently. The other method generalizes the T-global Arnoldi–Tikhonov regularization method recently presented by El Guide et al. [10] to allow for \({\mathcal {L}}\ne {\mathcal {I}}\). This method works with the lateral slices of the data tensor \({\mathcal {B}}\) simultaneously, and will be referred to as the generalized global tAT (GG-tAT) method.
A comparison of the solution methods for (1.9) is presented in Sect. 6. Computed examples show the GG-tAT method to require less CPU time, but the G-tAT method may yield higher accuracy. The fact that the GG-tAT requires less CPU time is to be expected since it uses larger chunks of data at a time.
We remark that the G-tAT and GG-tAT methods belong to the AT\(\_\)BTF (Arnoldi–Tikhonov Based Tensor Format) family of methods recently described by Beik et al. [2]. They involve flattening and require additional product definitions to the t-product.
Finally, we will discuss a variant of the T-global GMRES method that recently has been described by El Guide et al. [10] and is based on the t-product formalism. We will refer to our variant as the generalized global tGMRES (GG-tGMRES) method. This method replaces the data tensor \(\mathcal {\mathbf {B}}\) in (1.8) by a general third order tensor \({\mathcal {B}}\) and determines iterates in t-Krylov subspaces \({\mathbb {K}}_\ell ({\mathcal {A}},{\mathcal {B}})\). The \(\ell \)th iterate \({\mathcal {X}}_\ell \in {\mathbb {K}}_\ell ({\mathcal {A}},{\mathcal {B}})\) determined by the GG-tGMRES method with initial iterate \({\mathcal {X}}_0={\mathcal {O}}\in {\mathbb {R}}^{m\times p\times n}\) solves
In the T-global GMRES method by El Guide et al. [10], the iterations are terminated based on a residual Frobenius norm and a set tolerance that is independent of the error in \({\mathcal {B}}\). Differently from the T-global GMRES method, our approach for solving (1.10) uses the discrepancy principle to determine the number of iterations to carry out with the GG-tGMRES method.
This paper is organized as follows. Section 2 introduces notation and preliminaries associated with the t-product. Methods based on the t-Arnoldi process are described in Sect. 3. This includes Tikhonov regularization methods, one of which is based on a nested t-Krylov subspace, and GMRES-type methods for the computation of approximate solutions of (1.1) and the analogous minimization problem obtained by replacing the tensor slice \(\mathcal {\mathbf {B}}\) by a third order tensor \({\mathcal {B}}\). Thus, we can consider color image and video restoration problems. For the former, \({\mathcal {B}}\) represents a blurred and noisy RGB image of dimension \(m\times p\times 3\), while for gray-scale video restoration problems, \({\mathcal {B}}\) is of dimension \(m \times p \times n\) with a sequence of n consecutive blurred and noisy video frames. Section 4 describes algorithms that are based on the generalized global t-Arnoldi (GG-tA) process with data tensor \({\mathcal {B}}\). The algorithms of Sect. 5 are obtained by modifying algorithms of Sect. 4 to be applicable to each lateral slice of \({\mathcal {B}}\) separately. This allows us to consider, for instance, the restoration of gray-scale images. Section 6 presents some numerical examples that illustrate the performance of the described methods. Concluding remarks can be found in Sect. 7.
2 Notation and Preliminaries
This section reviews results on the t-product introduced by Kilmer et al. [22, 23] and defines notation from [10, 26] to be used in the sequel. In this paper, a tensor is of third order, i.e., a three-dimensional array of real scalars denoted by calligraphic script letters, say, \({\mathcal {A}}=[a_{ijk}]_{i,j,k=1}^{\ell ,m,n}\in {\mathbb {R}}^{\ell \times m\times n}\) with real entries \(a_{ijk}\). Matrices and vectors are second and first order tensors, respectively. We use capital letters to denote matrices, lower case letters to denote vectors, and bold face lower case letters to denote tube fibers (tubal scalars or tubes). A fiber of a third order tensor is a 1D section obtained by fixing two of the indices. Using MATLAB notation, \({\mathcal {A}}(:,j,k)\), \({\mathcal {A}}(i,:,k)\), and \({\mathcal {A}}(i,j,:)\) denote mode-1, mode-2, and mode-3 fibers, respectively. A slice of a third order tensor is a 2D section obtained by fixing one of the indices. With MATLAB notation, \({\mathcal {A}}(i,:,:)\), \({\mathcal {A}}(:,j,:)\), and \({\mathcal {A}}(:,:,k)\) denote the ith horizontal, jth lateral, and kth frontal slices, respectively. The jth lateral slice is also denoted by \(\mathcal {\mathbf {A}}_j\). It is a tensor and will be referred to as a tensor column. Moreover, the kth frontal slice, which also will be denoted by \({\mathcal {A}}^{(k)}\), is a matrix.
Given \({\mathcal {A}}\in {\mathbb {R}}^{\ell \times m\times n}\) with \(\ell \times m\) frontal slices \({\mathcal {A}}^{(i)}\), \(i = 1,2,\dots ,n\), the operator \(\mathtt {unfold}({\mathcal {A}})\) returns a block \(\ell n \times m\) matrix made up of the faces \({\mathcal {A}}^{(i)}\) of \({\mathcal {A}}\). The \(\mathtt {fold}\) operator folds back the unfolded \({\mathcal {A}}\), i.e.,
The operator \(\mathtt {bcirc}({\mathcal {A}})\) generates an \(\ell n\times mn\) block circulant matrix with \(\mathtt {unfold}({\mathcal {A}})\) forming the first block column,
Definition 2.1
(t-product [23]) Let \({\mathcal {A}}\in {\mathbb {R}}^{\ell \times m\times n}\) and \({\mathcal {B}}\in {\mathbb {R}}^{m\times p\times n}\). Then the t-product \(\mathcal {A*B}\) is the tensor \({\mathcal {C}}\in {\mathbb {R}}^{\ell \times p\times n}\) defined by
where “\(\cdot \)” denotes the standard matrix-matrix product.
We can view \({\mathcal {C}}\) in (2.1) as an \(\ell \times p\) matrix of tubes oriented along the third dimension with its (i, j)th tube given by
This shows that the t-product is analogous to matrix multiplication, except that multiplication between scalars is replaced by circular convolution between tubes.
The matrix \(\mathtt {bcirc}({\mathcal {A}})\) can be block diagonalized by the discrete Fourier transform (DFT) matrix combined with the Kronecker product. Suppose that \({\mathcal {A}}\in {\mathbb {R}}^{\ell \times m\times n}\) and let \(F_n\in {{\mathbb {C}}}^{n\times n}\) denote the unitary DFT matrix. Then
where \(\otimes \) is the Kronecker product and \(F_n^*\) denotes the conjugate transpose of \(F_n\). The matrix \(\bar{A}\) is an \(\ell n\times mn\) block diagonal matrix with \(\ell \times m\) blocks \(\widehat{{\mathcal {A}}}^{(i)}\), \(i=1,2,\dots ,n\). The matrices \(\widehat{{\mathcal {A}}}^{(i)}\) are the frontal slices of the tensor \(\widehat{{\mathcal {A}}}\) obtained by applying the discrete Fourier transform along each tube of \({\mathcal {A}}\). We remark that
The t-product is a natural extension of matrix multiplication for third order tensors [23]. Higher order tensors allow the definition of analogues of the t-product; see [30]. Matrix algorithms for QR and SVD factorizations have analogues for third order tensors; see Kilmer et al. [22].
We may choose to evaluate \(\mathcal {A*B}\) according to Definition 2.1 if the tensors \({\mathcal {A}}\) and \({\mathcal {B}}\) are sparse. For general tensors \({\mathcal {A}}\in {\mathbb {R}}^{\ell \times m\times n}\) and \({\mathcal {B}}\in {\mathbb {R}}^{m\times p\times n}\), the t-product \(\mathcal {A*B}\) can be computed efficiently by using the transformation (2.2), i.e.,
The right-hand side of (2.2) can be evaluated in \({\mathcal {O}}(\ell mn\log _2(n))\) arithmetic floating point operations (flops) using the fast Fourier transform (FFT); see [23].
The t-product is readily computed in MATLAB. We often will use the superscript \(\widehat{\,}\) to denote objects that are obtained by taking the FFT along the third dimension. Using MATLAB notation, let \({\widehat{\mathcal {C}}}:=\mathtt {fft}({\mathcal {C}},[\;],3)\) be the tensor obtained by applying the FFT to \({\mathcal {C}}\) along the third dimension. Then the t-product \({\mathcal {A}}*{\mathcal {B}}\) can be computed by first taking the FFT along the tubes of \({\mathcal {A}}\) and \({\mathcal {B}}\) to get \(\mathcal {\widehat{A}}=\mathtt {fft}({\mathcal {A}},[\;],3)\) and \(\mathcal {\widehat{B}} = \mathtt {fft}({\mathcal {B}},[\;],3)\), multiplying each pair of the frontal slices of \(\mathcal {\widehat{A}}\) and \(\mathcal {\widehat{B}}\),
and then taking the inverse FFT along the third dimension to obtain \({\mathcal {C}} = \mathtt {ifft}(\mathcal {\widehat{C}},[\;],3)\). The t-product (2.3) can be computed by using the MATLAB tensor-tensor product toolbox;Footnote 1 see [28]. Certain symmetry properties can be utilized during the computations. This is done in the computations reported in Sect. 6.
Let \({\mathcal {A}}\in {\mathbb {R}}^{\ell \times m\times n}\). The tensor transpose, \({\mathcal {A}}^T\in {\mathbb {R}}^{m\times \ell \times n}\), is the tensor obtained by transposing each one of the frontal slices of \({\mathcal {A}}\), and then reversing the order of the transposed frontal slices 2 through n; see [23]. The tensor transpose has similar properties as the matrix transpose. For instance, if \({\mathcal {A}}\) and \({\mathcal {B}}\) are two tensors such that \(\mathcal {A*B}\) and \({\mathcal {B}}^T*{\mathcal {A}}^T\) are defined, then \((\mathcal {A*B})^T={\mathcal {B}}^T*{\mathcal {A}}^T\).
The identity tensor \({\mathcal {I}}\in {\mathbb {R}}^{m\times m\times n}\) is a tensor, whose first frontal slice, \({\mathcal {I}}^{(1)}\), is the \(m\times m\) identity matrix and all other frontal slices, \({\mathcal {I}}^{(i)}\), \(i = 2,3, \dots , n\), are zero matrices; see [23].
The concept of orthogonality is well defined under the t-product formalism; see Kilmer and Martin [23]. A tensor \({\mathcal {Q}}\in {\mathbb {R}}^{m\times m\times n}\) is said to be orthogonal if \({\mathcal {Q}}^T*{\mathcal {Q}} = {\mathcal {Q}}*{\mathcal {Q}}^T = {\mathcal {I}}\). Analogously to the columns of an orthogonal matrix, the lateral slices of an orthogonal tensor \({\mathcal {Q}}\) are orthonormal, i.e.,
where \(\mathbf{e}_1\in {\mathbb {R}}^{1\times 1\times n}\) is a tubal scalar whose (1, 1, 1) entry equals 1 and the remaining entries vanish. It is shown in [23] that if \({\mathcal {Q}}\) is an orthogonal tensor, then
The tensor \({\mathcal {Q}}\in {\mathbb {R}}^{\ell \times m\times n}\) with \(\ell >m\) is said to be partially orthogonal if \({\mathcal {Q}}^T*{\mathcal {Q}}\) is well defined and equal to the identity tensor \({\mathcal {I}}\in {\mathbb {R}}^{m\times m\times n}\); see [23].
A tensor \({\mathcal {A}}\in {\mathbb {R}}^{m\times m\times n}\) is said to have an inverse, denoted by \({\mathcal {A}}^{-1}\), provided that \({\mathcal {A}}*{\mathcal {A}}^{-1}={\mathcal {I}}\) and \({\mathcal {A}}^{-1}*{\mathcal {A}}={\mathcal {I}}\). Moreover, a tensor is said to be f-diagonal if each frontal slice of the tensor is a diagonal matrix; see [23].
The tensor singular value decomposition (tSVD) of \({\mathcal {A}}\in {\mathbb {R}}^{\ell \times m\times n}\), introduced by Kilmer and Martin [23], is given by
where \({\mathcal {U}}\in {\mathbb {R}}^{\ell \times \ell \times n}\) and \({\mathcal {V}}\in {\mathbb {R}}^{m\times m\times n}\) are orthogonal tensors, and the tensor
is f-diagonal with singular tubes \({{\mathbf {s}}}_j\in {\mathbb {R}}^{1\times 1\times n}\), \(j =1,2,\dots ,\min \{\ell , m\}\), ordered according to
The number of nonzero singular tubes of \({\mathcal {A}}\) is referred to as the tubal rank of \({\mathcal {A}}\); see Kilmer et al. [22]. The singular tubes of \({\mathcal {A}}\) are analogues of the singular values of a matrix A. In linear discrete ill-posed problems that require the solution of a linear system of equations or of a least squares problem with a matrix A, this matrix has many singular values of different orders of magnitude close to zero. Definition 2.2 describes linear discrete ill-posed tensor problems.
Definition 2.2
The tensor least squares problems (1.1) is said to be a linear discrete ill-posed problem for third order tensors under \(*\) if \({\mathcal {A}}\) has ill-determined tubal rank, i.e., the Frobenius norm of the singular tubes of \({\mathcal {A}}\) decays rapidly to zero with increasing index, and there are many nonvanishing singular tubes of tiny Frobenius norm of different orders of magnitude.
We remark that this definition is not in terms of the frontal slices \({\mathcal {A}}^{(i)}, i = 1,2,\dots , n,\) of \({\mathcal {A}}\), but describes a property of the whole tensor \({\mathcal {A}}\), i.e., of the singular tubes of \({\mathcal {A}}\). The singular tubes are computed by finding the singular value decomposition of each frontal slice \(\mathcal {\widehat{A}}^{(i)}\), \(i = 1,2,\dots ,n\), of \(\mathcal {\widehat{A}}\) in the Fourier domain; see [23] for details.
The norm of a nonzero tensor column \(\mathcal {\mathbf {X}}\in {\mathbb {R}}^{m\times 1\times n}\) is defined as
and \(\Vert \mathcal {\mathbf {X}}\Vert = 0\) if \(\mathcal {\mathbf {X}} = \mathcal {\mathbf {O}}\); see [22] for details. The Frobenius norm of a tensor column \(\mathcal {\mathbf {X}}\in {\mathbb {R}}^{m\times 1\times n}\) is given by
see [22]. Thus, the square of the Frobenius norm of \(\mathcal {\mathbf {X}}\) is the first frontal face of the tube \(\mathcal {\mathbf {X}}^T*\mathcal {\mathbf {X}}\in {\mathbb {R}}^{1\times 1\times n}\) denoted by \(\big (\mathcal {\mathbf {X}}^T*\mathcal {\mathbf {X}}\big )_{(:,:,1)}\).
Algorithm 1, which takes a nonzero tensor \(\mathcal {\mathbf {X}} \in {\mathbb {R}}^{m\times 1\times n}\) and returns the normalized tensor \(\mathcal {\mathbf {V}}\in {\mathbb {R}}^{m\times 1\times n}\) and the tubal scalar \({\mathbf {a}}\in {\mathbb {R}}^{1\times 1\times n}\), such that
is important in the sequel. Note that the tubal scalar \({\mathbf {a}}\) might not be invertible; see [22] for details. We mention that \({\mathbf {a}}\) is invertible if there is a tubal scalar \({\mathbf {b}}\) such that \(\mathbf {a*b} = \mathbf {b*a} = \mathbf{e}_1\). The scalar \({\mathbf {a}}^{(j)}\) is the jth face of the \(1\times 1\times n\) tubal scalar \({\mathbf {a}}\), while \(\mathcal {\mathbf {V}}^{(j)}\) is a vector with m entries, and is the jth frontal face of \(\mathcal {\mathbf {V}}\in {\mathbb {R}}^{m\times 1\times n}\). The call of the MATLAB function \(\mathtt {randn}(m,1)\) in Algorithm 1 generates a pseudo-random m-vector with normally distributed entries with zero mean and variance one. In Algorithm 1 and elsewhere in this paper, \(\Vert \cdot \Vert _2\) denotes the Euclidean vector norm.
The t-product-based tensor QR (tQR) factorization implemented by Algorithm 2 is described by Kilmer et al. [22]. Let \({\mathcal {A}}\in {\mathbb {R}}^{\ell \times m\times n}\). Then its tQR factorization is given by
where the tensor \({\mathcal {Q}}\in {\mathbb {R}}^{\ell \times m\times n}\) is partially orthogonal and the tensor \({\mathcal {R}}\in {\mathbb {R}}^{m\times m\times n}\) is f-upper triangular (i.e., each face is upper triangular).
We introduce additional definitions used by El Guide et al. [10]. They will be needed when discussing the G-tAT, GG-tAT, G-tGMRES and GG-tGMRES methods in Sects. 4 and 5. Let
where \({\mathcal {C}}_j\in {\mathbb {R}}^{m\times p\times n}\) and \(\mathcal {\mathbf {C}}_j\in {\mathbb {R}}^{m\times 1\times n}\). Suppose that \(y = [y_1, \dots , y_k]^T\in {\mathbb {R}}^k\). Then El Guide et al. define the product \(\circledast \) as
It can be shown that for orthogonal tensors \({\mathbb {Q}}\in {\mathbb {R}}^{m\times kp\times n}\) and \({\mathcal {Q}}\in {\mathbb {R}}^{m\times k\times n}\), one has
see [10] for details.
Consider the tensors \({\mathcal {C}}=[c_{ijk}]\) and \({\mathcal {D}}=[w_{ijk}]\) in \({\mathbb {R}}^{m\times p\times n}\) with lateral slices \(\mathcal {\mathbf {C}}=[c_{i1k}]\) and \(\mathcal {\mathbf {D}}=[d_{i1k}]\) in \({\mathbb {R}}^{m\times 1\times n}\), respectively. Define the scalar products
Let
where \({\mathcal {A}}_i\in {\mathbb {R}}^{\ell \times k\times n}\), \(\mathcal {\mathbf {A}}_i\in {\mathbb {R}}^{\ell \times 1\times n}\), \(i=1,2,\dots ,m\), and \({\mathcal {B}}_j\in {\mathbb {R}}^{\ell \times k\times n}\), \(\mathcal {\mathbf {B}}_j\in {\mathbb {R}}^{\ell \times 1\times n}\), \(j=1,2,\dots ,p\). Following El Guide et al. [10], we define the T-diamond products \({\mathbb {A}}^T\Diamond {\mathbb {B}}\) and \({\mathcal {A}}^T\Diamond {\mathcal {B}}\). They define \(m\times p\) matrices with entries
The generalized global tensor QR (GG-tQR) factorization is described in [35] and implemented by Algorithm 3. Given \({\mathbb {A}}\) in (2.6), this factorization is defined by
where \(R\in {\mathbb {R}}^{m \times m}\) is an upper triangular matrix, and the tensor \({\mathbb {Q}}\in {\mathbb {R}}^{\ell \times km\times n}\) with \(\ell \ge k\) has k partially orthogonal tensor columns such that
where \(I_m\) is the \(m \times m\) identity matrix.
We also will need a special case of the GG-tQR factorization, which works with each lateral slice \(\mathcal {\mathbf {A}}_i\), \(i=1,2,\dots ,m\), of the tensor \({\mathcal {A}}\) in (2.6). This factorization method is implemented by Algorithm 4; it is also described in [35], and is there referred to as the global tQR (G-tQR) factorization method.
We conclude this section with the definition of some tensor operators that will be convenient to apply in Sect. 6. The matrix \(X\in {\mathbb {R}}^{m\times n}\) is associated with the tensor \(\mathcal {\mathbf {X}}\in {\mathbb {R}}^{m\times 1\times n}\) by the \(\mathtt {squeeze}\) and \(\mathtt {twist}\) operators, defined by Kilmer et al. [22], i.e.,
Note that the \(\mathtt {squeeze}\) operator is identical to the MATLAB squeeze function.
We also define the \(\mathtt {multi}\_\mathtt {squeeze}\) and \(\mathtt {multi}\_\mathtt {twist}\) operators that enable us to squeeze and twist a general third order tensor. The tensor \({\mathcal {C}}\in {\mathbb {R}}^{m\times p\times n}\) is associated with \({\mathcal {D}}\in {\mathbb {R}}^{m\times n\times p}\) by
where \(\mathtt {multi}\_\mathtt {twist}({\mathcal {C}})\) twists each one of the frontal slices \({\mathcal {C}}^{(i)}\), \(i=1,2,\dots ,n\), of \({\mathcal {C}}\) by using the \(\mathtt {twist}\) operator, and stacks them as lateral slices \(\mathcal {\mathbf {D}}_i\), \(i=1,2,\dots ,n\), of \({\mathcal {D}}\). Moreover, the operator \(\mathtt {multi}\_\mathtt {squeeze}({\mathcal {D}})\) squeezes the lateral slices of \({\mathcal {D}}\) using the \(\mathtt {squeeze}\) operator and stacks them as faces of \({\mathcal {C}}\).
3 Methods Based on the t-Arnoldi Process
We first describe an algorithm for the t-Arnoldi process. This algorithm is applied in Sects. 3.1 and 3.2 to reduce the large-scale problem (1.1) to a problem of small size.
Let \({\mathcal {A}}\in {\mathbb {R}}^{m\times m\times n}\). The t-Arnoldi process described by Algorithm 5 (cf. the matrix version in [37, Chapter 5]) reduces the tensor \({\mathcal {A}}\) to an upper Hessenberg tensor (t-Hessenberg), whose every face is an upper Hessenberg matrix.
The t-Arnoldi process is said to break down if any of the subdiagonal tubal scalars \({\mathbf {h}}_{j+1,j}\) for \(j=1,2,\ldots ,\ell \), is not invertible. This is analogous to a break down of the (standard) Arnoldi process. We will assume that the number of steps, \(\ell \), of the t-Arnoldi process is small enough to avoid break down, i.e., that \(\ell \) is chosen small enough so that every subdiagonal tubal scalar \({\mathbf {h}}_{j+1,j}\) is invertible for \(j=1,2,\ldots ,\ell \). This means, in particular, that the transformed tubal scalars \(\widehat{{\mathbf {h}}}_{j+1,j}\) of \({\mathbf {h}}_{j+1,j}\) do not have zero Fourier coefficients.
Algorithm 5 produces the partial t-Arnoldi decomposition
where
\(\mathcal {\bar{H}}_\ell = \begin{bmatrix} {\mathbf {h}}_{11} &{} &{} &{} \dots &{} {\mathbf {h}}_{1\ell }\\ {\mathbf {h}}_{21} &{} {\mathbf {h}}_{22} &{} \\ &{}{\mathbf {h}}_{32} &{} {\mathbf {h}}_{33} &{} &{} \vdots \\ &{} &{} \ddots &{} \ddots &{} \\ &{} &{} &{} {\mathbf {h}}_{\ell , \ell -1} &{} {\mathbf {h}}_{\ell ,\ell }\\ &{} &{} &{} &{} {\mathbf {h}}_{\ell +1,\ell } \end{bmatrix}\in {\mathbb {R}}^{(\ell +1)\times \ell \times n}\)
is of upper t-Hessenberg form. The lateral slices \(\mathcal {\mathbf {Q}}_j\), \(j=1,2,\dots ,\ell \), of \({\mathcal {Q}}_\ell \in {\mathbb {R}}^{m\times \ell \times n}\) form an orthonormal tensor basis for the t-Krylov subspace (1.7), where t-span refers to the set of all tensor linear (t-linear) combinations, whose coefficients are tubal scalars, \(\mathbf{c}_i \in {\mathbb {R}}^{1 \times 1 \times n}\), \(i = 1,2,\dots ,\ell \). Thus,
The t-Arnoldi process generates an orthonormal tensor basis for the t-Krylov subspace (3.2) by applying the standard Arnoldi process to each frontal slice \(\mathcal {\widehat{A}}^{(i)}\), \(i=1,2,\dots ,n\), of \(\mathcal {\widehat{A}}\) simultaneously. This process requires normalization, which is carried out by Algorithm 1.
We comment on the complexity of the standard Arnoldi and t-Arnoldi processes. Let \(A \in {\mathbb {R}}^{m \times m}\) be a dense matrix and \(1\le \ell \ll m\) the number of steps carried out by the standard Arnoldi process. Then this process requires \({\mathcal {O}}(\ell ^2 m + \ell m^2)\) flops, since \(\ell \) matrix-vector product evaluations with A cost \({\mathcal {O}}(\ell m^2)\) flops and \({\mathcal {O}}(\ell ^2 m)\) flops are required for orthogonalization.
We implement the t-Arnoldi process with transformations to and from the Fourier domain. For a dense tensor \({\mathcal {A}}\in {\mathbb {R}}^{m \times m \times n}\), application of \(1\le \ell \ll m\) steps of this process requires application of \(\ell \) steps of the standard (matrix) Arnoldi process to the frontal slices \({\mathcal {A}}^{(i)}\), \(i=1,2,\dots ,n\), of \({\mathcal {A}}\) simultaneously in the Fourier domain, and orthogonalization. Each transformation of \({\mathcal {A}}\) and \(\mathcal {\mathbf {Q}}_j\) to and from the Fourier domain in step 3 of Algorithm 5 costs \({\mathcal {O}}(m^2n\log (n))\) and \({\mathcal {O}}(mn\log (n))\) flops, respectively. Moreover, \(\ell \) matrix-vector products of the faces of \({\mathcal {A}}\) and \(\mathcal {\mathbf {Q}}_j\) in the Fourier domain cost \({\mathcal {O}}(\ell m^2)\) flops. For n frontal slices, it has a complexity of \({\mathcal {O}}(\ell m^2 n)\) flops in the Fourier domain. Similarly, the orthogonalization steps 4-7 in the Fourier domain cost \({\mathcal {O}}(\ell ^2 mn)\) flops for n frontal slices. Note that it costs \({\mathcal {O}}(n\log (n))\) flops to transform each tubal scalar \(\mathbf{h}_{ij}\) to and from the Fourier domain. Hence, the total flop count for carrying out \(\ell \) steps of the t-Arnoldi process in the Fourier domain is \({\mathcal {O}}((\ell m^2+\ell ^2 m)n)\) flops. The cost is the same for the G-tA process implemented by Algorithm 13 in Sect. 5.
We will use the decomposition (3.1) to determine an approximate solution of the Tikhonov minimization problems (1.3) and (1.9) in Sect. 3.1, and of the minimization problems (1.8) and (1.10) in Sect. 3.2.
3.1 Tensor Arnoldi–Tikhonov Regularization Methods
This subsection discusses the computation of an approximate solution of the tensor Tikhonov regularization problem (1.3) with the aid of the t-Arnoldi process. We describe how this process can be used in conjunction with the discrepancy principle (1.6), and show that the penalized least squares problem (1.3) has a unique solution \(\mathcal {\mathbf {X}}_\mu \); see, e.g., [6] for a proof of the matrix case.
Theorem 3.1
Let \(\mu >0\) be the regularization parameter. The minimization problem (1.3) has a unique solution
that satisfies the normal equations
Proof: The function
can be written as
where
Thus, \(\mathcal {\mathbf {X}}_\mu \) is a minimizer of \({\mathcal {J}}_\mu (\mathcal {\mathbf {X}})\) if and only if \(\mathcal {\mathbf {X}}_\mu \) is the solution of the normal equations
which can be written as (3.4). Due to (1.4) the solution is unique.\(\Box \)
The normal Eq. (3.4) with \(\mathcal {L = I}\) have been used by Kilmer et al. [22] and Martin et al. [30].
When the regularization operator \({\mathcal {L}}\) is the identity tensor, the solution (3.3) simplifies to
Using this expression for \(\mathcal {\mathbf {X}}_\mu \), define the function
Then Eq. (1.6) (for \({\mathcal {L}}={\mathcal {I}}\)) can be written as
A zero-finder, such as bisection, Newton’s method, or a related method [3, 34], can be used to solve (3.7) for \(\mu _\mathrm{discr}=\mu >0\). We assume here and below that \(\delta >0\). Then \(\mathcal {\mathbf {X}}_{\mu _\mathrm{discr}}\) satisfies the discrepancy principle (1.6) (when \({\mathcal {L}}={\mathcal {I}}\)).
The following properties of \(\phi \) are shown in [35]. We remark that while the solution (3.5) is meaningful for \(\mu >0\) only, we may define \(\phi (\mu )\) for \(\mu \ge 0\) by continuity.
Proposition 3.1
Assume that \({\mathcal {A}}^T*\mathcal {\mathbf {B}} \ne \mathcal {\mathbf {O}}\) and let \(\phi (\mu )\) be given by (3.6) with \(\mathcal {\mathbf {X}}_\mu \) defined by (3.5). Then
and \(\phi (0)=\Vert \mathcal {\mathbf {B}}\Vert ^2_F\). Moreover,
for \(\mu >0\).
3.1.1 The tAT Method for the Solution of (1.3)
We develop the t-product Arnoldi–Tikhonov (tAT) regularization method for the approximate solution of least squares problems of the form (1.3). The method will be used to illustrate the potential superiority of tensorizing as opposed to vectorizing or matricizing ill-posed tensor equations in general. This method will be generalized in Sect. 3.1.2 to the least squares problems (1.9) with a general data tensor \({\mathcal {B}}\).
Let \(\mathcal {\mathbf {X}}={\mathcal {Q}}_\ell *\mathcal {\mathbf {Y}}\) for some \(\mathcal {\mathbf {Y}}\in {\mathbb {R}}^{\ell \times 1\times n}\) and substitute the decomposition (3.1) into (1.3). This yields
Using the fact that \(\mathcal {\mathbf {B}} = \mathcal {\mathbf {Q}}_1*{\mathbf {z}}_1\) (cf. Algorithm 5), we obtain
where the (1, 1, 1)th entry of \(\mathbf { e }_1\in {\mathbb {R}}^{m\times 1\times n}\) equals 1 and the remaining entries vanish. Substitute (3.9) into (3.8) to obtain
In the computed examples of Sect. 6, we use the regularization operators \({\mathcal {L}}_1\in {\mathbb {R}}^{(m-2)\times m\times n}\) and \({\mathcal {L}}_2\in {\mathbb {R}}^{(m-1)\times m\times n}\), where the tensor \({\mathcal {L}}_1\) has the tridiagonal matrix
as its first frontal slice, and the remaining frontal slices \({\mathcal {L}}_1^{(i)}\in {\mathbb {R}}^{(m-2)\times m}\), \(i=2,3,\ldots ,n\), are zero matrices. The first face of the tensor \({\mathcal {L}}_2\) is the bidiagonal matrix
and the remaining faces \({\mathcal {L}}_2^{(i)}\in {\mathbb {R}}^{(m-1)\times m}\), \(i=2,3,\dots ,n\), are zero matrices.
Our approach of handling these regularization operators is analogous to the technique used in [19]. It can be applied to many other regularization operators as well. We use Algorithm 2 to compute the tQR factorization
where the tensor \({\mathcal {Q}}_{{\mathcal {L}},\ell }\in {\mathbb {R}}^{s\times \ell \times n}\) has \(\ell \) orthonormal tensor columns and the tensor \({\mathcal {R}}_{{\mathcal {L}},\ell }\in {\mathbb {R}}^{\ell \times \ell \times n}\) is f-upper triangular. In view of (2.4), the minimization problem (3.10) simplifies to
For the regularization operators \(\mathcal {L}\) defined by (3.11) and (3.12) as described above, as well as for many other regularization operators \({\mathcal {L}}\), the tensor \({\mathcal {R}}_{{\mathcal {L}},\ell }\) is invertible and not very ill-conditioned. In this situation, we may form
where \(\mathcal {{\widetilde{H}}}_\ell \) is computed by solving \(\ell \) linear systems of equations. Substituting the above expressions into (3.13) yields
The minimization problem (3.15) can be solved fairly stably by computing the solution of
using Algorithm 6 below. The solution of (3.16) can be expressed as
and the associated approximate solution of (1.3) is given by
We use the discrepancy principle (1.6) to determine the regularization parameter \(\mu >0\) and the required number of steps of the t-Arnoldi process as follows. Define the function
which is analogous to (3.6). Substituting (3.17) into (3.18), and using the identity
we obtain
The following proposition shows that we can apply the discrepancy principle (1.6) to the reduced problem to determine \(\mu >0\), i.e., we require \(\mu \) to be such that
Proposition 3.2
Let \(\mu = \mu _\ell \) solve \(\phi _\ell (\mu )=\eta ^2\delta ^2\) and let \(\mathcal {\mathbf {Z}}_{\mu ,\ell }\) solve (3.16). Let \(\mathcal {\mathbf {Y}}_{\mu ,\ell }\) and \(\mathcal {\mathbf {Z}}_{\mu ,\ell }\) be related by (3.14). Then the associated approximate solution \(\mathcal {\mathbf {X}}_{\mu ,\ell } = {\mathcal {Q}}_\ell *\mathcal {\mathbf {Y}}_{\mu ,\ell }\) of (1.1) satisfies
Proof
Substituting \(\mathcal {\mathbf {X}}_{\mu ,\ell }={\mathcal {Q}}_\ell *\mathcal {\mathbf {Y}}_{\mu ,\ell }\) into (1.6) and using the decomposition of (3.1), as well as (3.9) and (2.4), gives
\(\Box \)
It can be shown analogously as Proposition 3.1 that the function \(\phi _\ell (\mu )\) is decreasing and convex with \(\phi _\ell (0)=\Vert \mathbf { e }_1*{\mathbf {z}}_1\Vert _F^2\). Therefore, Newton’s method can be used for the solution of
without safeguarding for any initial approximate solution \(\mu _0\ge 0\) smaller than the solution of (3.20). In particular, we may use \(\mu _0 = 0\) when \(\phi _\ell (\mu )\) and \(\phi ^\prime _\ell (\mu )\) are suitably defined at \(\mu = 0\). Note that when the regularization parameter \(\mu >0\) in (1.3) is replaced by \(1/\mu \), the analogue of the function \(\phi _\ell \) obtained is not guaranteed to be convex. Then Newton’s method has to be safeguarded. An algorithm for Newton’s method can be found in [35].
We refer to the solution method for (3.8) described above as the tAT method. It is implemented by Algorithm 7 with \(p=1\). It follows from Proposition 3.1, with \(\phi \) replaced by \(\phi _\ell \), that \(\phi _\ell (\mu )\) is a decreasing function of \(\mu \). A lower bound for \(\phi _\ell (\mu )\) on the right-hand side of (3.21) can be established similarly as in the proof of [35, Proposition 4.4].
Proposition 3.3
Let \(\phi _\ell (\mu )\) be given by (3.19). Then
where \({\mathcal {D}} \in {\mathbb {R}}^{(\ell +1) \times (\ell +1) \times n}\) is a tensor whose first frontal slice \({\mathcal {D}}^{(1)}\) has the entry 1 at the \((\ell +1, \ell +1)\)st position, and the remaining frontal slices \({\mathcal {D}}^{(i)}\), \(i=2, \dots , n\), are zero matrices. The tensor \({\mathcal {U}} \in {\mathbb {R}}^{(\ell +1) \times (\ell +1) \times n}\) is the left singular tensor of \(\mathcal {{\widetilde{H}}}_\ell \).
The values
typically decrease quite rapidly as \(\ell \) increases, because making \(\ell \) larger increases the dimension of the subspace over which the least squares problem (3.8) is minimized. Therefore, generally, only a fairly small number of steps of Algorithm 7 are required to satisfy (3.20) for some \(0<\mu <\infty \).
3.1.2 tAT Methods for the Solution of (1.9)
This subsection generalizes the solution methods of Sect. 3.1.1 to the solution of least squares problems of the form (1.9). The methods of this subsection can be applied to color image and video restorations. Several matrix-based methods for the solution of these restoration problems have recently been described by Beik et al. [1, 2] and El Guide et al. [8, 10].
We present two algorithms for the solution of (1.9). They both consider (1.9) as p separate Tikhonov minimization problems
where \(\mathcal {\mathbf {B}}_1,\mathcal {\mathbf {B}}_2,\dots ,\mathcal {\mathbf {B}}_p\) are tensor columns of the data tensor \({\mathcal {B}}\) in (1.9). Both algorithms are based on the t-Arnoldi process and the tAT method described in Sect. 3.1.1.
Let \(\mathcal {\mathbf {B}}_{j,\mathrm{true}}\) denote the unknown error-free tensor (slice) associated with the available error-contaminated tensor (slice) \(\mathcal {\mathbf {B}}_j\), and assume that bounds \(\delta _j\) for the norm of the errors
are available or can be estimated, i.e.,
cf. (1.2) and (1.5). Algorithm 7 solves each one of the p least squares problems (3.22) independently. We refer to this approach of solving (3.22) as the tAT\(_p\) method.
Algorithm 8 generates a t-Krylov subspace \({\mathbb {K}}_\ell ({\mathcal {A}},\mathcal {\mathbf {B}}_1)\) of sufficiently large dimension \(\ell \) to contain accurate enough approximate solutions of all the p least squares problems (3.22). Thus, we first solve the least squares problem (3.22) for \(j=1\) by Algorithm 8, and then seek to solve the least squares problem (3.22) for \(j=2\) using the same t-Krylov subspace \({\mathbb {K}}_\ell ({\mathcal {A}},\mathcal {\mathbf {B}}_1)\). If the discrepancy principle cannot be satisfied, then the dimension \(\ell \) of the t-Krylov subspace is increased until the discrepancy principle can be satisfied. Having solved this least squares problem, we proceed similarly to solve the problems (3.22) for \(j=3,4,\ldots ,p\). The details are described by Algorithm 8. The t-Arnoldi process is implemented with reorthogonalization when applied in Algorithm 8 to ensure that the quantities \({\mathcal {Q}}_{\ell +1}^T*\mathcal {\mathbf {B}}_j\) are evaluated with sufficient accuracy. When the required number of t-Arnoldi steps, \(\ell \), for solving the least squares problem is large, it may be beneficial to restart Algorithm 8 with the tensor \(\mathcal {\mathbf {B}}_j\). Restarting was not required in the computations reported in Sect. 6. We refer to this approach based on using nested t-Krylov subspaces as the nested\(\_\)tAT\(_p\) method.
3.2 The tGMRES Method for the Solution of (1.8) and (1.10)
We first describes the t-product GMRES (tGMRES) method for the approximate solution of (1.8). This method subsequently will be generalized to the solution of problems of the form (1.10). We remark that the tGMRES method is analogous to the (standard) GMRES method introduced by Saad and Schultz [38]. Regularizing properties of the (standard) GMRES method for the situation when \({\mathcal {A}}\) is a matrix are discussed in [4, 33].
Substituting \(\mathcal {\mathbf {X}}={\mathcal {Q}}_\ell *\mathcal {\mathbf {Y}}\) into the right-hand side of (1.8), using (3.1) as well as (3.9) and (2.4), gives the reduced minimization problem
We refer to this solution method for (1.8) as the tGMRES method. It is implemented by Algorithm 9 with \(p=1\). The number of t-Arnoldi steps required by the tGMRES method is determined by the discrepancy principle
in Algorithm 9, where \(\eta >1\) is a user-specified constant that is independent of \(\delta \); cf. (1.6). Thus, we terminate the tGMRES iterations as soon as an iterate \(\mathcal {\mathbf {Y}}=\mathcal {\mathbf {Y}}_\ell \) that satisfies (3.24) has been found. Generally, only fairly few iterations are needed. Restarting tGMRES therefore typically is not required.
We turn to a tGMRES method for the solution of (1.10), which we refer to as the tGMRES\(_p\) method. This method, implemented by Algorithm 9, considers (1.10) as p separate minimization problems for \(\mathcal {\mathbf {X}}_{j,\ell }\in {\mathbb {K}}_\ell ({\mathcal {A}}, \mathcal {\mathbf {B}}_j)\),
where \(\mathcal {\mathbf {B}}_1,\mathcal {\mathbf {B}}_2,\dots ,\mathcal {\mathbf {B}}_p\) are tensor columns of the data tensor \({\mathcal {B}}\) in (1.10). The input parameters \(\delta _j\) for Algorithm 9 are defined by (3.23). The number of steps \(\ell \) is chosen large enough to satisfy the discrepancy principle.
4 Methods Based on the Generalized Global t-Arnoldi Process
This section discusses the computation of an approximate solution of the tensor Tikhonov regularization problem (1.9) and the minimization problem (1.10) with the aid of the T-global Arnoldi process recently described by El Guide et al. [10]. Application of a few, say \(1\le \ell \ll m\), steps of the T-global Arnoldi process to the tensor \({\mathcal {A}}\in {\mathbb {R}}^{m\times m\times n}\) with initial tensor \({\mathcal {B}}\in {\mathbb {R}}^{m\times p\times n}\), \(p>1\), reduces this tensor to a small upper Hessenberg matrix \(\bar{H}_\ell \in {\mathbb {R}}^{(\ell +1)\times \ell }\). We refer to this process as the generalized global t-Arnoldi (GG-tA) process. It is implemented by Algorithm 10. We assume that the number of steps, \(\ell \), is small enough to avoid breakdown. Then the GG-tA process yields the decomposition
where
and
The tensors \({\mathcal {Q}}_j\in {\mathbb {R}}^{m\times p\times n}\), \(j=1,2,\dots ,\ell \), generated by Algorithm 10 form an orthonormal tensor basis for the t-Krylov subspace \({\mathbb {K}}_\ell ({\mathcal {A}},{\mathcal {B}})\), which is analogous to the space (1.7),
The next result follows immediately from the definition (4.3). The analogous result when \({\mathcal {A}}\) is a matrix and \({\mathcal {B}}\) is a vector is discussed, e.g., in [37, 41].
Proposition 4.1
Let \({\mathcal {Z}} \in {\mathbb {K}}_\ell ({\mathcal {A}},{\mathcal {B}})\). Then \({\mathcal {Z}}=p({\mathcal {A}})*{\mathcal {B}}\) for some polynomial p of degree at most \(\ell -1\).
Proof
The tensor \({\mathcal {Z}} \in {\mathbb {K}}_\ell ({\mathcal {A}},{\mathcal {B}})\) can be expressed as
for certain real scalars \(\alpha _j\), where \(p({\mathcal {A}}) := \sum \limits _{j=0}^{\ell -1} \alpha _j {\mathcal {A}}^j\) is the polynomial of a tensor \({\mathcal {A}}\); see [29, 31, 32] for discussions on tensor functions. \(\Box \)
The upper Hessenberg matrix in (4.2) is given by
The relation
is easily deduced from Algorithm 10.
Differently from the t-Arnoldi process, the GG-tA process uses the data tensor \({\mathcal {B}}\in {\mathbb {R}}^{m \times p \times n}\), \(p>1\), and only requires transformation to and from the Fourier domain in step 3. Each transformation of \({\mathcal {A}}\) and \({\mathcal {Q}}_j\) to and from the Fourier domain in step 3 costs \({\mathcal {O}}(m^2n\log (n))\) and \({\mathcal {O}}(mpn\log (n))\) flops, respectively. This step computes \(\ell \) matrix-matrix product of the frontal slices \(\mathcal {\widehat{A}}^{(i)}\) and \(\mathcal {\widehat{Q}}_j^{(i)}\), \(i=1,2,\dots ,n\), for \({\mathcal {O}}(\ell m^2 p)\) flops each. Hence for n frontal slices, the cost of implementing step 3 in the Fourier domain is \({\mathcal {O}}(\ell m^2 p n)\) flops. The orthogonalization steps 4-7 demands \({\mathcal {O}}( \ell ^2 m np)\) flops. Hence, the GG-tA process has a complexity of \({\mathcal {O}}((\ell m^2 + \ell ^2 m)np)\) flops in the Fourier domain. This cost is the same when the t-Arnoldi and G-tA processes are applied to separately solve the p minimization problems (3.22), since solving each one of the p minimization problems independently costs \({\mathcal {O}}((\ell m^2 + \ell ^2 m)n)\) flops in the Fourier domain.
We use the decomposition (4.1) to determine an approximate solution of the Tikhonov minimization problem (1.9) in Sect. 4.1, and of the minimization problem (1.10) in Sect. 4.2.
4.1 The GG-tAT Method for the Solution of (1.9)
This subsection describes a modification of the T-global Arnoldi–Tikhonov regularization method recently presented by El Guide et al. [10] for the approximate solution of (1.9) with \(\mathcal {L=I}\) to allow a general third order tensor regularization operator \(\mathcal {L \ne I}\). This modification requires Algorithm 3. We refer to this modification of the method by El Guide et al. [10] as the generalized global tAT (GG-tAT) method. This method is based on first reducing \({\mathcal {A}}\) in (1.9) to an upper Hessenberg matrix by carrying out a few, say \(\ell \), steps of the GG-tA process, which is described by Algorithm 10. Differently from the approach of El Guide et al. [10], who apply a restarted GG-tA process, determine the regularization parameter by the GCV, and use a stopping criterion based on the residual Frobenius norm and a specified tolerance that is independent of the error in the data tensor, we use the discrepancy principle to determine the regularization parameter and the number of iterations required by the GG-tA process. Then the implementation of the GG-tA process does not require restarts since only a small number of iterations are needed.
We compute an approximate solution of (1.9) analogously as described in Sect. 3.1.1. Thus, letting \({\mathcal {X}}={\mathbb {Q}}_\ell \circledast y\), and using (4.1) and (4.5), the minimization problem (1.9) reduces to
where \(\beta =\Vert {\mathcal {B}}\Vert _F\). Algorithm 3 yields the GG-tQR factorization
where \(R_{{\mathcal {L}},\ell }\in {\mathbb {R}}^{\ell \times \ell }\) is an upper triangular matrix and \({\mathbb {Q}}_{{\mathcal {L}},\ell }\in {\mathbb {R}}^{s\times \ell p\times n}\) has \(\ell \) orthonormal tensor columns. Substituting (4.7) into (4.6), and using the left-hand side of (2.5), gives
Typically, the matrix \(R_{{\mathcal {L}},\ell }\) is nonsingular and not very ill-conditioned. Then we can express (4.8) as a Tikhonov minimization problem in standard form,
where
Similarly as above, we compute \({\widetilde{H}}_\ell \) by solving \(\ell \) linear systems of equations. The minimization problem (4.9) is analogous to (3.15). Its solution, \(z_{\mu ,\ell }\), can be computed fairly stably by solving
The associated approximate solution of (1.9) is given by
We determine the regularization parameter \(\mu \) by the discrepancy principle based on the Frobenius norm. This assumes knowledge of a bound
for the error \({\mathcal {E}}\) in \({\mathcal {B}}\). Thus, we choose \(\mu >0\) so that the solution \(z_{\mu ,\ell }\) of (4.11) satisfies
Define the function
where \(z_{\mu ,\ell }\) solves (4.11). Manipulations similar to those applied in Sect. 3.1.1 show that \(\psi _\ell (\mu )\) can be expressed as
It is readily verified that the function \(\mu \rightarrow \psi _\ell (\mu )\) is decreasing and convex for \(\mu \ge 0\) with \(\psi _\ell (0)=\beta ^2\).
Proposition 4.2
Let \(\psi _\ell (\mu )\) be given by (4.12). Then
where \(\gamma >0\) is the square of the (1, 1) entry of the \((\ell +1)\)st left singular vector of \({\widetilde{H}}_\ell \).
The infimum of \(\psi _\ell (\mu )\) on the right-hand side of (4.13) typically decreases quite rapidly as \(\ell \), which is the dimension of the solution subspace, increases; see [35] for a proof of (4.13).
A similar reasoning as in Sect. 3.1 suggests that it may be convenient to solve
by Newton’s method with initial approximate solution \(\mu =0\).
We turn to a matrix analogue of Proposition 3.2.
Proposition 4.3
Let \(\mu _\ell \) solve (4.14) and let \(z_{\mu ,\ell }\) be the associated solution of (4.9) with \(\mu =\mu _\ell \). Let \(y_{\mu ,\ell }\) and \(z_{\mu ,\ell }\) be related by (4.10). Then the approximate solution \({\mathcal {X}}_{\mu ,\ell }={\mathbb {Q}}_\ell \circledast y_{\mu ,\ell }\) of (1.9) satisfies
Proof
Substituting \({\mathcal {X}}_{\mu ,\ell }={\mathbb {Q}}_\ell \circledast y_{\mu ,\ell }\) into (4.15), using (4.1) and (4.5), as well as left-hand side of (2.5), gives
We refer to the solution method described above as the GG-tAT method. It is implemented by Algorithm 11. The method works with all lateral slices \(\mathcal {\mathbf {B}}_j\), \(j=1,2,\dots , p\), of \({\mathcal {B}}\) simultaneously.
4.2 The GG-tGMRES Method for the Approximate Solution of (1.10)
We describe the generalized global tGMRES (GG-tGMRES) method for the approximate solution of (1.10). This method works with all lateral slices \(\mathcal {\mathbf {B}}_j\), \(j=1,2,\dots ,p\), of \({\mathcal {B}}\) simultaneously. A closely related method, referred to as the T-global GMRES method, recently has been described by El Guide et al. [10]. The latter method differs from the GG-tGMRES method in the following ways: it uses a restarted GG-tA process and a stopping criterion based on the residual Frobenius norm with a prespecified tolerance that is independent of the error in \({\mathcal {B}}\). The GG-tGMRES method uses the discrepancy principle to decide when to terminate the iterations. The number of iterations required by this method to satisfy the discrepancy principle typically is quite small. Restarting therefore generally is not required.
Substituting \({\mathcal {X}} = {\mathbb {Q}}_\ell \circledast y\) into the right-hand side of (1.10), using (4.1) and (4.5), as well as the left-hand side of (2.5), gives the reduced minimization problem
The GG-tGMRES method solves (4.16) for a value of \(\ell \) determined by the discrepancy principle and requires that a bound \(\delta \) for \(\Vert {\mathcal {E}}\Vert _F\) be known, where \({\mathcal {E}}\) is the error in \({\mathcal {B}}\). This method is analogous to the tGMRES method described in Sect. 3.2. It is implemented by Algorithm 12.
5 Methods Based on the Global t-Arnoldi Process
This section discusses the computation of approximate solutions of the tensor Tikhonov regularization problems (1.3) and (1.9), and of the minimization problems (1.8) and (1.10), with the aid of the global t-Arnoldi (G-tA) process. This process is readily implemented by taking \(p=1\) in Algorithm 10. We assume that \(\ell \) is small enough to avoid breakdown. Algorithm 13 determines the G-tA decomposition
where
The expressions \({\mathcal {A}}*{\mathcal {Q}}_\ell \) and \({\mathcal {Q}}_{\ell +1}\circledast \bar{\bar{H}}_\ell \) in (5.1) are defined similarly as (4.2), and \(\bar{\bar{H}} \in {\mathbb {R}}^{(\ell +1) \times \ell }\) has a form analogous to (4.4). The tensors \(\mathcal {\mathbf {Q}}_j\in {\mathbb {R}}^{\ell \times 1\times n}\), \(j=1,2,\dots , \ell \), generated by Algorithm 13 form an orthonormal tensor basis for the t-Krylov subspace \({\mathbb {K}}_\ell ({\mathcal {A}},\mathcal {\mathbf {B}})\), where the definition of t-span is analogous to (4.3). We use the G-tA process to determine an approximate solution of the Tikhonov minimization problems (1.9) and (1.3) in Sect. 5.1.
5.1 The G-tAT Method for the Solution of (1.9) and (1.3)
We describe a solution method for (1.9) that works with each lateral slice \(\mathcal {\mathbf {B}}_j\), \(j=1,2,\dots ,p\), of the data tensor \({\mathcal {B}}\) independently. Thus, one solves (1.9) by applying the global t-product Arnoldi–Tikhonov (G-tAT) method to the p Tikhonov minimization problems (3.22) separately. We refer to this solution approach as the G-tAT\(_p\) method. It is implemented by Algorithm 14.
The G-tAT method for the approximate solution of (1.3) first reduces \({\mathcal {A}}\) in (1.3) to an upper Hessenberg matrix by carrying out a few, say \(\ell \), steps of the G-tA process described by Algorithm 13. Let \(\mathcal {\mathbf {X}}={\mathcal {Q}}_\ell \circledast y\). Then following a similar approach as in Sect. 4.1, we reduce (1.3) to
Compute the G-tQR factorization of \({\mathcal {L}}*{\mathcal {Q}}_\ell \) by Algorithm 4 to obtain
where the tensor \({\mathcal {Q}}_{{\mathcal {L}},\ell }\in {\mathbb {R}}^{s\times \ell \times n}\) has \(\ell \) orthonormal tensor columns and the matrix \(\bar{R}_{{\mathcal {L}},\ell }\in {\mathbb {R}}^{\ell \times \ell }\) is upper triangular.
Substitute (5.3) into (5.2), use the right-hand side of (2.5), and define
where we assume that the matrix \(\bar{R}_{{\mathcal {L}},\ell }\) is invertible and not very ill-conditioned. We obtain the Tikhonov minimization problem in standard form
This problem can be solved similarly as (4.9). We refer to this approach of solving (1.3) as the G-tAT method. It is implemented by Algorithm 14 with \(p=1\). The parameter \(\delta _1\) is set to \(\delta \) determined by (1.5). When applying Algorithm 14 to solve (1.9), the input parameters \(\delta _1,\delta _2,\dots ,\delta _p\) are determined by (3.23).
5.2 The G-tGMRES Method for the Solution of (1.8) and (1.10)
This subsection describes the global tGMRES (G-tGMRES) method for the approximate solution of (1.8) and (1.10). The G-tGMRES method uses the G-tA process described by Algorithm 13 and works with a data tensor slice \(\mathcal {\mathbf {B}}\) in (1.8) or one lateral slice of the data tensor \({\mathcal {B}}\) at a time in (1.10). The G-tGMRES method is analogous to the GG-tGMRES method of the previous section.
Substitute \(\mathcal {\mathbf {X}}={\mathcal {Q}}_\ell \circledast y\) into (1.8) and proceed similarly as described in Sect. 4.2 to obtain the reduced minimization problem
We refer to the solution method so defined as the G-tGMRES method. It is implemented by Algorithm 15 with \(p=1\).
We conclude this subsection by describing an algorithm for the approximate solution of (1.10) based on the G-tGMRES method. This algorithm provides an alternative to the GG-tGMRES method of Sect. 4.2. It works with each lateral slice \(\mathcal {\mathbf {B}}_j\), \(j=1,2,\dots ,p\), of the data tensor \({\mathcal {B}}\) independently. Thus, one solves the p minimization problems (3.25) separately by the G-tGMRES method. This approach is implemented by Algorithm 15 and will be referred to as the G-tGMRES\(_p\) method. The parameters \(\delta _1,\delta _2,\dots ,\delta _p\) for the algorithm are determined by (3.23).
6 Numerical Examples
This section illustrates the performance of the methods described in the previous sections when applied to the solution of several linear discrete ill-posed tensor problems. These methods are broadly categorized into two groups: those that involve flattening, i.e., reduce the tensor least squares problems (1.3), (1.8), (1.9), and (1.10) to equivalent problems involving matrices and vectors, and those that preserve the tensor structure and do not involve flattening. We illustrate that it is generally beneficial to preserve the multidimensional tensor structure when solving linear discrete ill-posed tensor problems.
Applications to the restoration of (color) images and gray-scale videos are considered. Computed examples show that methods that preserve the natural spatial ordering yield the most accurate approximate solutions. In particular, tAT-type methods, such as tAT, tAT\(_p\) and nested_ tAT\(_p\), give the best approximate solution in all computed examples except in Example 6.2; see Table 3. All computations were carried out in MATLAB 2019b on a Lenovo computer with an Intel Core i3 processor and 4 GB RAM running Windows 10.
We use the discrepancy principle to determine the regularization parameter(s) and the number of steps of the iterative methods in all examples. The “noise” tensor \({\mathcal {E}}\in {\mathbb {R}}^{m\times p\times n}\), which simulates the error in the data tensor \({\mathcal {B}}={\mathcal {B}}_{\text {true}}+{\mathcal {E}}\), is determined by its lateral slices \(\mathcal {\mathbf {E}}_j\), \(j=1,2,\dots ,p\). The entries of these slices are normally distributed random numbers with zero mean and are scaled to correspond to a specified noise level \({\widetilde{\delta }}\). Thus,
where the entries of the error tensors \(\mathcal {\mathbf {E}}_{0,j}\) are N(0, 1). For problem (1.1), we have \(p=1\).
Let \(\mathcal {\mathbf {X}}_\mathrm{method}\) be the computed approximate solution of (1.1) by a chosen method. The relative error
is used to determine the effectiveness of the proposed methods. The relative error for problems with a three-mode data tensor \({\mathcal {B}}\) is determined analogously.
We let \({\mathcal {A}}\in {\mathbb {R}}^{256\times 256\times 256}\) in all computed examples unless otherwise stated. The condition number of the frontal slices of \({\mathcal {A}}\) are computed using the MATLAB command \(\mathtt {cond}\). We set \(\mathtt{tol}=10^{-12}\) in Algorithm 1.
Example 6.1
This example compares Tikhonov regularization with the regularization tensor \({\mathcal {L}}_2\in {\mathbb {R}}^{255 \times 256 \times 256}\), see (3.12), as implemented by the tAT\(_p\), nested\(\_\)tAT\(_p\), G-tAT\(_p\) and GG-tAT methods to the GMRES-type methods described by the tGMRES\(_p\), G-tGMRES\(_p\), and GG-tGMRES methods. Let the matrix
be generated by the function \(\mathtt{gravity}\) from Hansen’s Regularization Tools [17] and define the prolate matrix \(A_2=\mathtt {gallery}('\mathtt {prolate}',256,\alpha )\) in MATLAB. We set \(\alpha =0.46\). Then \(A_2\) is a symmetric positive definite ill-conditioned Toeplitz matrix. The tensor \({\mathcal {A}}\) is defined by its frontal slices
The exact data tensor \({\mathcal {B}}_\mathrm{true}\in {\mathbb {R}}^{256\times 3\times 256}\) is given by \({\mathcal {B}}_\mathrm{true} = {\mathcal {A}}*{\mathcal {X}}_\text {true}\), where the exact solution \({\mathcal {X}}_\mathrm{true}\in {\mathbb {R}}^{256\times 3\times 256}\) has all entries equal to unity. The noise-contaminated right-hand side \({\mathcal {B}}\in {\mathbb {R}}^{256\times 3\times 256}\) is generated by \({\mathcal {B}}={\mathcal {B}}_\text {true}+{\mathcal {E}}\), where the noise tensor \({\mathcal {E}}\in {\mathbb {R}}^{256\times 3\times 256}\) is determined according to (6.1). The condition numbers of the slices \({\mathcal {A}}^{(i)}\) satisfy \(\mathtt {cond}({\mathcal {A}}^{(i)})\ge 1\cdot 10^{16}\) for all i. Thus, every slice is numerically singular. We take \(\eta =1.15\) and determine the regularization parameter(s) for Tikhonov regularization by Newton’s method. The computed regularization parameters and relative errors for different noise levels, as well as the number of iterations required to satisfy the discrepancy principle by each method, are displayed in Table 1. Here and below the table entry “-” indicates that the solution method carries out different numbers of t-Arnoldi steps or computes different values of the regularization parameter for the different lateral slices of \({\mathcal {B}}\), or that no regularization parameter is required.
Table 1 shows the GG-tAT and GG-tGMRES methods to be the fastest for both noise levels, but the tAT\(_p\) and nested\(\_\)tAT\(_p\) methods, which do not involve flattening, yield approximate solutions of higher accuracy for both noise levels. The tAT\(_p\) method determines the most accurate approximations of \({\mathcal {X}}_\text {true}\) and requires the most CPU time for both noise levels. The tGMRES\(_p\) method yields the worst quality solution for both noise levels. In general, the quality of the computed approximate solutions determined by Tikhonov regularization is higher than the approximate solutions calculated by GMRES-type methods. This depends on the use of the regularization operator \({\mathcal {L}}_2\) by the former methods. We remark that \(\mathcal {B}_{\text {true}}\) depends on the t-product.
Example 6.2
This example implements Example 6.1 analogously by taking \(\mathcal {L=I}\), \(d = 0.025\) to generate \(A_1\), and determines the regularization parameter(s) by Newton’s method with \(\eta = 1.1\). The condition numbers of \({\mathcal {A}}^{(i)}\) are as described above. The relative errors for different noise levels and the CPU times are displayed in Table 2.
Table 2 shows that the GG-tAT and GG-tGMRES methods, which involve flattening, are the fastest for both noise levels. The nested\(\_\)tAT\(_p\) method, which does not involve flattening and is based on nested t-Krylov subspaces, yields the most accurate approximate solutions. The G-tAT\(_p\) and GG-tAT methods with Tikhonov regularization determine approximate solutions of almost the same quality as the GMRES-type methods implemented by the G-tGMRES\(_p\) and GG-tGMRES methods for both noise levels. The tGMRES\(_p\) method yields approximate solutions of least accuracy for both noise levels. For the solution methods that do not involve flattening (implemented by the tAT\(_p\), nested\(\_\)tAT\(_p\), and tGMRES\(_p\) methods), the quality of the computed approximate solutions is higher when Tikhonov regularization is applied.
We finally compare the tAT and G-tAT methods to the tGMRES and G-tGMRES methods. The exact solution is the tensor column \(\mathcal {\mathbf {X}}_\mathrm{true}\in {\mathbb {R}}^{256\times 1\times 256}\) with all entries equal to unity. The noise-contaminated right-hand side \(\mathcal {\mathbf {B}}\in {\mathbb {R}}^{256\times 1\times 256}\) is generated by \(\mathcal {\mathbf {B}}=\mathcal {\mathbf {B}}_\text {true}+\mathcal {\mathbf {E}}\), where the noise tensor \(\mathcal {\mathbf {E}}\in {\mathbb {R}}^{256\times 1\times 256}\) is determined as described above. Table 3 shows the number of iterations required to satisfy the discrepancy principle by each method, the regularization parameters, as well as the relative errors and CPU times for both noise levels.
We see from Table 3 that the quality of the computed approximate solutions is higher when using Tikhonov regularization. The G-tGMRES and tGMRES methods are the fastest, but the tGMRES method yields approximate solutions of least quality for both noise levels. The G-tAT and G-tGMRES methods, which matricize the tensor equation (1.1), yield the most accurate solutions for both noise levels. This is the only one of our examples in which matricizing is beneficial for the quality of the computed solutions. In our experience this situation is quite rare.
The remainder of this section discusses image and video restoration problems. We use the bisection method to determine the regularization parameter over a chosen interval. The blurring operator \({\mathcal {A}}\) is constructed similarly as described in [20] by using the function \(\mathtt{blur}\) from [17]. We assess the quality of the approximate restorations determined by the different methods by comparing the relative error defined above and the Peak Signal-to-Noise Ratio (PSNR) given by
where \({\mathrm{MAX}}_{{\mathcal {X}}_\mathrm{true}}\) is the maximum of all the pixel values of the true image represented by \({\mathcal {X}}_\mathrm{true}\in {\mathbb {R}}^{m \times p \times n}\) and the mean square error is given by
For the problem (1.1) discussed in Example 6.3, we use \(p=1\).
Example 6.3
(2D image restoration problem) This example illustrates the advantage of preserving the tensor structure when solving tensor linear discrete ill-posed problems. Specifically, we show that the tAT method, which avoids flattening (matricization and vectorization) of the tensor equation (1.1), yields restorations of the highest quality for both noise levels independently of the regularization operators used.
We discuss the performance of the tAT and G-tAT methods with the regularization tensors \(\mathcal {L=I}\), and \({\mathcal {L}}={\mathcal {L}}_1\in {\mathbb {R}}^{298\times 300\times 300}\) defined by (3.12), and compare these methods to the standard Arnoldi–Tikhonov (AT) regularization method with regularization matrix \(L=I\) described in [27], (standard) GMRES, tGMRES, and G-tGMRES methods when applied to the restoration of the TelescopeFootnote 2 image of size \(300 \times 300\) pixels that have been contaminated by blur and noise. The AT and GMRES methods compute an approximate solution of the linear system of equations
where \(\otimes \) denotes the Kronecker product; the block matrix \(A_1 \otimes A_2 \in {\mathbb {R}}^{300^2 \times 300^2}\) represents the blurring operator. The right-hand side vector \(b\in {\mathbb {R}}^{300^2}\) stores the vectorized available blur- and noise-contaminated image \(B\in {\mathbb {R}}^{300 \times 300}\). This vector is contaminated by \(e\in {\mathbb {R}}^{300^2}\), which represents (unknown) noise; it is a vectorization of the noise matrix \(E\in {\mathbb {R}}^{300 \times 300}\). We would like to determine an approximation of the “true” blur- and noise-free image \(X_\mathrm{true}\in {\mathbb {R}}^{300 \times 300}\) or its vectorized form \(x_\mathrm{true}\in {\mathbb {R}}^{300^2}\). The circulant matrix \(A_1\) and Toeplitz matrix \(A_2\) are generated with the MATLAB commands
with \(N = 300\), \(\sigma =3\) and \(\mathtt{band}=9\). By exploiting the circulant structure of \(A_1 \otimes A_2\) and using the fold, unfold, and twist operators, the 2D deblurring problem (6.2) can be formulated as the following problem in tensor form
where \(\mathcal {\mathbf {X}} = \mathtt{twist}(X)\), \(\mathcal {\mathbf {B}} = \mathtt{twist}(B)\), and \(\mathcal {\mathbf {E}} = \mathtt{twist}(E)\). The frontal slices \({\mathcal {A}}^{(i)} \in {\mathbb {R}}^{300\times 300}\), \(i = 1,2,\dots ,300\), of the blurring operator \({\mathcal {A}}\in {\mathbb {R}}^{300\times 300\times 300}\) are generated by folding the first block column of \(A_1 \otimes A_2\), i.e.,
The computed condition numbers of \({\mathcal {A}}^{(i)}\) are \(\mathtt {cond}({\mathcal {A}}^{(i)})=1.6\cdot 10^5\) for \(i=1,2,\ldots ,9\), and \(\mathtt {cond}({\mathcal {A}}^{(i)})\) is “infinite” for \(i\ge 10\). We let \(\eta =1.1\) in (1.6) and determine the regularization parameter by the bisection method over the interval \([10^{1},10^7]\).
The true \(\mathtt {Telescope}\) image is shown on the left-hand side of Fig. 1. For the matrix problem (6.2), this image is stored as a vector \(x_\mathrm{true} \in {\mathbb {R}}^{300^2}\) and blurred by \(A_1 \otimes A_2\), while for the tensor problem (6.4), it is stored as \(\mathcal {\mathbf {X}}_{\text {true}}\in {\mathbb {R}}^{300\times 1\times 300}\) using the \(\mathtt {twist}\) operator and blurred by the tensor \({\mathcal {A}}\). The blurred and noisy image represented by b is shown in Fig. 1 (middle) using the MATLAB reshape command.
True image (left), blurred and noisy image (middle) with noise level \({\widetilde{\delta }} = 10^{-3}\), and restored image by the tAT (right) method after 8 iterations
The restored images determined by the tAT, G-tAT, and tGMRES methods are accessed using the \(\mathtt {squeeze}\) operator and displayed in Figs. 1 and 2 for the noise level \({\widetilde{\delta }}=10^{-3}\). Similarly, the restored image computed by the GMRES method is displayed in Fig. 2 (middle) using the MATLAB reshape command.
Table 4 shows the computed regularization parameters, relative errors, and PSNR values for the noise levels \(10^{-2}\) and \(10^{-3}\), as well as CPU times. As can be expected, the quality of the computed restorations is higher when the noise level is smaller. The tGMRES method requires the least CPU time for \({\widetilde{\delta }}=10^{-3}\) and yields the worst restorations for both noise levels. Independently of the choice of \({\mathcal {L}}\), Tikhonov regularization implemented by the tAT method determines restorations of the highest quality. The G-tAT and G-tGMRES methods, which involve flattening, demand the most CPU time and require the most iterations for both noise levels. The GMRES and G-tGMRES methods require the same number of iterations and yield the same quality restorations for both noise levels. Similar observations can be made for the AT and G-tAT methods when the regularization operator is the identity matrix and identity tensor, respectively.
Restored images by the G-tAT (left), GMRES (middle), and tGMRES (right) methods after 51, 51, and 8 iterations, respectively, for the noise level \({\widetilde{\delta }}=10^{-3}\)
Example 6.4
(Color image restoration) This example is concerned with the restoration of color images using the same regularization operators as in Example 6.3. We seek to determine an approximate solution of the image deblurring problem
where the desired unavailable blur- and noise-free image \(X_\mathrm{true}\in {\mathbb {R}}^{300^2 \times 3}\) is the matricized three-channel image \({\mathcal {X}}_\mathrm{true}\in {\mathbb {R}}^{300\times 300\times 3}\). The right-hand side \(B \in {\mathbb {R}}^{300^2 \times 3}\) in (6.6) is generated by \(B = (A_1 \otimes A_2)X_\mathrm{true} + E \), where the unknown noise in the matrix B is represented by \(E\in {\mathbb {R}}^{300^2 \times 3}\), which is the matricized “noise” tensor \({\mathcal {E}}\in {\mathbb {R}}^{300\times 300\times 3}\). The blurring matrices \(A_1\) and \(A_2\) are defined by (6.3) in Example 6.3 with \(N = 300\), \(\sigma =3\) and \(\mathtt{band}=12\). By the same reasoning as in Example 6.3, we formulate (6.6) as the 3D image deblurring problem
where the blurring tensor \({\mathcal {A}}\in {\mathbb {R}}^{300\times 300\times 300}\) is constructed by (6.5) in Example 6.3. The computed condition numbers of the frontal slices of \({\mathcal {A}}\) are \(\mathtt {cond}({\mathcal {A}}^{(i)})=7.6\cdot 10^8\) for \(i=1,2,\dots ,12\), and \(\mathtt {cond}({\mathcal {A}}^{(i)})\) is “infinite” for \(i\ge 13\). We determine the regularization parameter(s) by the bisection method over the interval \([10^{-5},10^7]\). The discrepancy principle is used with the parameter \(\eta =1.1\). The (standard) global GMRES (G-GMRES) and (standard) global Arnoldi–Tikhonov (GAT) methods for (6.6) are based on the global Arnoldi process applied by Huang et al. [19]. We compare the performance of these methods to the tAT\(_p\), nested\(\_\)tAT\(_p\), G-tAT\(_p\), GG-tAT, tGMRES\(_p\), G-tGMRES\(_p\), and GG-tGMRES methods for the solution of (6.7).
The original (blur- and noise-free) flowerFootnote 3 image shown on the left-hand side of Fig. 3 is stored as a tensor \({\mathcal {X}}_\text {true}\in {\mathbb {R}}^{300\times 3\times 300}\). It is blurred using the tensor \({\mathcal {A}}\). Thus, \(\mathcal {{B}}_{\text {true}}={\mathcal {A}}*\mathcal {{X}}_{\text {true}}\in {\mathbb {R}}^{300\times 3\times 300}\) represents the blurred but noise-free image associated with \({\mathcal {X}}_{\text {true}}\). The “noise” tensor \(\mathcal {{E}}\in {\mathbb {R}}^{300\times 3\times 300}\) is generated as described by (6.1) with noise level \({\widetilde{\delta }} = 10^{-3}\) and added to \({\mathcal {B}}_{\text {true}}\) to obtain the blurred and noisy image \(\mathcal {{B}}\) shown in Fig. 3 (middle). The latter image is accessed by using the multi_squeeze operator.
True image (left), blurred and noisy image (middle) with noise level \({\widetilde{\delta }} = 10^{-3}\), and restored image determined by nested\(\_\)tAT\(_p\) (right) after 9 iterations
Restored images determined by GG-tAT (left) after 32 iterations, and G-GMRES (middle) after 32 iterations and the tGMRES\(_p\) (right), for the noise level \({\widetilde{\delta }} = 10^{-3}\)
The restored images determined by the nested\(\_\)tAT\(_p\), GG-tAT, G-GMRES, and tGMRES methods are displayed in Figs. 3 and 4. Relative errors, PSNR values, as well as CPU times are shown in Table 5. The tAT method gives restorations of the highest or nearly highest quality; the nested\(\_\)tAT\(_p\) method also determines accurate restorations. These methods do not involve flattening. Solution methods that involve flattening such as the G-tAT\(_p\), GG-tAT, G-tGMRES\(_p\), and GG-tGMRES methods require the most CPU time for both noise levels. The GAT, GG-tAT, G-GMRES, and GG-tGMRES methods require the same number of iterations, which are more than the number of iterations used by the nested\(\_\)tAT\(_p\) method, for both noise levels. The tGMRES\(_p\) method yields restorations of the worst quality for both noise levels. The GG-tGMRES method, which works with the whole data tensor at a time, yields the same quality restorations as the G-GMRES method for both noise levels. The same conclusion can be drawn for the GG-tAT and GAT methods when the regularization operator is the identity tensor and the identity matrix, respectively. The quality of the restorations determined by the G-tAT\(_p\) and GG-tAT methods improves significantly with the use of the regularization operator \({\mathcal {L}}_1\) for both noise levels.
Example 6.5
(Video restoration) This example considers the restoration of the first six consecutive frames of the \(\mathtt {Xylophone}\) video from MATLAB. Each video frame is in the \(\mathtt {MP4}\) format and has \(240\times 240\) pixels.
True image (left), blurred and noisy image with noise level \({\widetilde{\delta }}=10^{-3}\) (middle), and restored image determined by 8 iterations with the tAT\(_p\) method (right)
The first six blur- and noise-free frames are stored as a tensor \({\mathcal {X}}_\text {true}\in {\mathbb {R}}^{240\times 6\times 240}\) using the \(\mathtt {multi}\_\mathtt {twist}\) operator. They are blurred by the tensor \({\mathcal {A}}\in {\mathbb {R}}^{240\times 240\times 240}\), which is generated similarly as in Example 6.3 with its frontal slices determined by
The condition numbers of the frontal slices of \({\mathcal {A}}\) are \(\mathtt {cond}({\mathcal {A}}^{(i)})=1.4\cdot 10^7\) for \(i=1,2,\dots ,12\). The condition numbers of the remaining frontal slices are “infinite”.
We use the regularization operator \({\mathcal {L}}={\mathcal {L}}_2\in {\mathbb {R}}^{239\times 240\times 240}\) and determine the regularization parameter(s) by the bisection method over the interval \([10^{-5},10^7]\) using the discrepancy principle with \(\eta =1.1\). The blurred and noisy frames are generated by \({\mathcal {B}} = {\mathcal {A}}*{\mathcal {X}}_\text {true} + {\mathcal {E}} \in {\mathbb {R}}^{240 \times 6 \times 240}\) with the “noise” tensor \({\mathcal {E}} \in {\mathbb {R}}^{240 \times 6 \times 240}\) defined by (6.1).
The true third frame is displayed in Fig. 5 (left), and the blurred and noisy third frame is shown in Fig. 5 (middle) using the \(\mathtt {squeeze}\) operator. Similarly, the restored images of the third frame determined by the G-tAT\(_p\), nested\(\_\)tAT\(_p\), G-tGMRES, and tGMRES methods are shown in Figs. 5 and 6.
Restored images by the nested\(\_\)G-tAT\(_p\) (left), G-tGMRES\(_p\) (middle), and tGMRES\(_p\) (right) for \({\widetilde{\delta }}=10^{-3}\)
The relative errors, PSNR values, and CPU times are displayed in Table 6. The tAT\(_p\) and nested\(\_\)tAT\(_p\) methods, which do not involve flattening, are seen to yield restorations of the highest quality for all noise levels. The tGMRES method is the fastest for \({\widetilde{\delta }}=10^{-2}\) and \(10^{-3}\), but gives the worst restorations for all noise levels. Solution methods that involve flattening, such as G-tAT\(_p\), GG-tAT and G-tGMRES\(_p\) and GG-tGMRES methods, are the slowest for \({\widetilde{\delta }}=10^{-3}\).
7 Conclusion
This paper extends the standard Arnoldi iteration for matrices to third order tensors and describes several algorithms based on this extension for solving linear discrete ill-posed problems with a t-product structure. The solution methods are based on computing a few steps of the extended Arnoldi process, which is referred to as the t-Arnoldi process. The global t-Arnoldi and generalized global t-Arnoldi processes also are considered. Differently from the t-Arnoldi process, the latter processes involve flattening. Both Tikhonov regularization and regularization by truncated iteration are considered. The latter gives rise to an extension of the standard GMRES method, referred to as the tGMRES and global tGMRES methods. The discrepancy principle is used to determine the number of iterations with the t-Arnoldi, global t-Arnoldi, and generalized global t-Arnoldi processes, as well as the regularization parameter in Tikhonov regularization and the number of iterations by the Arnoldi-type and GMRES-type methods. The effectiveness of the proposed methods is illustrated by applications to image and video restorations. Solution methods such as tAT, tAT\(_p\), and nested_tAT\(_p\), that avoid matricization or vectorization of discrete ill-posed problems for tensors, show great promise in terms of speed and quality of the computed restorations determined by their relative errors and PSNR values when compared to solution methods that matricize or vectorize.
References
Beik, F.P.A., Jbilou, K., Najafi-Kalyani, M., Reichel, L.: Golub–Kahan bidiagonalization for ill-conditioned tensor equations with applications. Numer. Algorithms 84, 1535–1563 (2020)
Beik, F.P.A., Najafi-Kalyani, M., Reichel, L.: Iterative Tikhonov regularization of tensor equations based on the Arnoldi process and some of its generalizations. Appl. Numer. Math. 151, 425–447 (2020)
Buccini, A., Pasha, M., Reichel, L.: Generalized singular value decomposition with iterated Tikhonov regularization. J. Comput. Appl. Math. 373, 112276 (2020)
Calvetti, D., Lewis, B., Reichel, L.: On the regularizing properties of the GMRES method. Numer. Math. 91, 605–625 (2002)
Calvetti, D., Morigi, S., Reichel, L., Sgallari, F.: Tikhonov regularization and the L-curve for large, discrete ill-posed problems. J. Comput. Appl. Math. 123, 423–446 (2000)
Calvetti, D., Reichel, L.: Tikhonov regularization of large linear problems. BIT Numer. Math. 43, 263–283 (2003)
Donatelli, M., Martin, D., Reichel, L.: Arnoldi methods for image deblurring with anti-reflective boundary conditions. Appl. Math. Comput. 253, 135–150 (2015)
El Guide, M., El Ichi, A., Jbilou, K., Beik, F.P.: Tensor GMRES and Golub–Kahan bidiagonalization methods via the Einstein product with applications to image and video processing. https://arxiv.org/pdf/2005.07458.pdf
El Ichi, M., El Guide, A., Jbilou, K.: Discrete cosine transform LSQR and GMRES methods for multidimensional ill-posed problems. https://arxiv.org/pdf/2103.11847.pdf (2021)
El Guide, M., El Ichi, A., Jbilou, K., Sadaka, R.: Tensor Krylov subspace methods via the T-product for color image processing. https://arxiv.org/pdf/2006.07133.pdf (2020)
Ely, G., Aeron, S., Hao, N., Kilmer, M.E.: 5d and 4d pre-stack seismic data completion using tensor nuclear norm (TNN). In: SEG International Exposition and Eighty-Third Annual Meeting at Houston, TX (2013)
Engl, H.W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Kluwer, Dordrecht (1996)
Fenu, C., Reichel, L., Rodriguez, G.: GCV for Tikhonov regularization via global Golub–Kahan decomposition. Numer. Linear Algebra Appl. 23, 467–484 (2016)
Gazzola, S., Novati, P., Russo, M.R.: On Krylov projection methods and Tikhonov regularization. Electron. Trans. Numer. Anal. 44, 83–123 (2015)
Golub, G.H., Heath, M., Wahba, G.: Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics 21, 215–223 (1979)
Hansen, P.C.: Analysis of discrete ill-posed problems by means of the L-curve. SIAM Rev. 34, 561–580 (1992)
Hansen, P.C.: Regularization tools version 4.0 for MATLAB 7.3. Numer. Algorithms 46, 189–194 (2007)
Hao, N., Kilmer, M.E., Braman, K., Hoover, R.C.: Facial recognition using tensor-tensor decompositions. SIAM J. Imaging Sci. 6, 437–463 (2013)
Huang, G., Reichel, L., Yin, F.: On the choice of subspace for large-scale Tikhonov regularization problems in general form. Numer. Algorithms 81, 33–55 (2019)
Kernfeld, E., Kilmer, M., Aeron, S.: Tensor-tensor products with invertible linear transforms. Linear Algebra Appl. 485, 545–570 (2015)
Kilmer, M., Braman, K., Hao, N.: Third order tensors as operators on matrices: a theoretical and computational framework. Technical Report, Department of Computer Science, Tufts University (2011)
Kilmer, M.E., Braman, K., Hao, N., Hoover, R.C.: 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)
Kilmer, M.E., Martin, C.D.: Factorization strategies for third-order tensors. Linear Algebra Appl. 435, 641–658 (2011)
Kindermann, S.: Convergence analysis of minimization-based noise level-free parameter choice rules for linear ill-posed problems. Electron. Trans. Numer. Anal. 38, 233–257 (2011)
Kindermann, S., Raik, K.: A simplified L-curve method as error estimator. Electron. Trans. Numer. Anal. 53, 217–238 (2020)
Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51, 455–500 (2009)
Lewis, B., Reichel, L.: Arnoldi–Tikhonov regularization methods. J. Comput. Appl. Math. 226, 92–102 (2009)
Lu, C., Feng, J., Chen, Y., Liu, W., Lin, Z., Yan, S.: Tensor robust principal component analysis with a new tensor nuclear norm. IEEE Trans. Pattern Anal. Mach. Intell. 42, 925–938 (2020)
Lund, K.: The tensor t-function: a definition for functions of third-order tensors. arXiv preprint. arXiv:1806.07261 (2018)
Martin, C.D., Shafer, R., LaRue, B.: An order-\(p\) tensor factorization with applications in imaging. SIAM J. Sci. Comput. 35, A474–A490 (2013)
Miao, Y., Qi, L., Wei, Y.: T-Jordan canonical form and T-Drazin inverse based on the T-product. Commun. Appl. Math. Comput. 3, 201–220 (2021)
Miao, Y., Qi, L., Wei, Y.: Generalized tensor function via the tensor singular value decomposition based on the T-product. Linear Algebra Appl. 590, 258–303 (2020)
Neubauer, A.: Augmented GMRES-type versus CGNE methods for the solution of linear ill-posed problems. Electron. Trans. Numer. Anal. 51, 412–431 (2019)
Reichel, L., Shyshkov, A.: A new zero-finder for Tikhonov regularization. BIT Numer. Math. 48, 627–643 (2008)
Reichel, L., Ugwu, U.O.: The tensor Golub–Kahan–Tikhonov method applied to the solution of ill-posed problems with a t-product structure. Numer. Linear Algebra Appl. 29,(2022). https://doi.org/10.1002/nla.2412
Reichel, L., Rodriguez, G.: Old and new parameter choice rules for discrete ill-posed problems. Numer. Algorithms 63, 65–87 (2013)
Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003)
Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual method for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7, 856–869 (1986)
Savas, B., Eldén, L.: Krylov-type methods for tensor computations. Linear Algebra Appl. 438, 891–918 (2013)
Soltani, S., Kilmer, M.E., Hansen, P.C.: A tensor-based dictionary learning approach to tomographic image reconstruction. BIT Numer. Math. 56, 1425–1454 (2015)
Trefethen, L.N., Bau, D., III.: Numerical Linear Algebra. SIAM, Philadelphia (1997)
Zhang, Z., Ely, G., Aeron, S., Hao, N., Kilmer, M. E.: Novel methods for multilinear data completion and de-noising based on tensor-SVD. In: IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2014, Columbus, OH, USA, June 23–28, 2014, pp. 3842–3849 (2014)
Acknowledgements
The authors would like to thank the referees for comments that led to improvements of the presentation. Research by LR was supported in part by NSF Grant DMS-1720259.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Reichel, L., Ugwu, U.O. Tensor Arnoldi–Tikhonov and GMRES-Type Methods for Ill-Posed Problems with a t-Product Structure. J Sci Comput 90, 59 (2022). https://doi.org/10.1007/s10915-021-01719-1
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10915-021-01719-1