1 Introduction

Accelerating slowly convergent sequences is one of the primary objectives of extrapolation methods. A common source of such sequences, for example, is the numerical solution of systems of linear or nonlinear equations using fixed-point iterative methods or sequences generated by quadrature techniques for integral computation. Typically, these sequences exhibit slow convergence towards the desired fixed point. As a result, to attain a satisfactory approximation of the limits of these sequences with a prescribed level of accuracy, a substantial number of iterations is necessary. This, in turn, results in a considerable computational burden.

Formally, the principle of extrapolation methods consists of transforming the terms of a certain slowly convergent sequence \((s_n)\) into a new sequence \((t_n)\) that converges more rapidly to the same limit. In fact, each extrapolation method employs a specific transformation T. For a given number \(k+1\) of elements from the basic sequence, the transformation T produces a new term \(t_n^{(k)}\) as: \(t_n^{(k)}=T(s_n,s_{n+1},\ldots ,s_{n+k})\) such that, under certain assumptions, \(\dfrac{\Vert t_n^{(k)}-s\Vert }{\Vert s_n -s\Vert }\underset{n\rightarrow \infty }{\longrightarrow }\ 0\) where s is the limit of \((s_n)\) and \(\Vert .\Vert \) is a suitable norm. As demonstrated in [12], it is worth noting that a universal transformation that accelerates the convergence of all sequences cannot exist. Actually, each transformation is only able to accelerate the convergence of a limited class of sequences. This implies that it will always be important to discover and study new transformations.

For scalars, vector and matrix sequences, many extrapolation methods have been introduced, see for example [7, 27] and the references therein. As for the tensor case that interests us in this work, extrapolation methods have been recently proposed. See for instance [2, 6, 10, 11, 16,17,18, 20, 22, 24, 25]. The primary reason for the interest in generalizing extrapolation methods to tensor sequences stems from the significant roles they have played in various disciplines, such as color and multispectral image and video processing [28], psychometrics, chemometrics, biomedical signal processing, higher-order statistics (HOS), and econometrics [1, 14]. Consequently, it becomes highly intriguing to search for appropriate transformations that expedite the convergence of tensor sequences.

In this paper, our aim is to introduce a new extrapolation method based on the combination of Higher-Order Singular Value Decomposition (HOSVD) [13], and the tensor global minimal polynomial extrapolation method (TG-MPE) [16]. A numerically stable algorithm is proposed for the implementation of the proposed method.

The outline of this paper is organized as follows. In Sect. 2, we provide the necessary definitions, notations, and some results required for this work. In Sect. 3, after a brief overview of the tensor global MPE (TG-MPE) method [16], we develop the new HOSVD-TMPE (Higher-Order Singular Value Decomposition method which is based on Tensor Minimal Polynomial Extrapolation). Section 4 outlines the algorithm for implementing this method. We establish error analysis results in Sect. 5, and in Sect. 6, we present numerical experiments that confirm the effectiveness of the proposed method.

2 Basic definitions

This section reviews some definitions and proprieties of tensors and uses notations defined by [19]. A tensor is a multidimensional array of data. The elements of a tensor are referred by using multiple indices. The required number of indices defines the order of a tensor. For a given (N-order) tensor \({\mathcal {A}} \in {\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}}\) we use the notation

$$\begin{aligned} {\mathcal {A}} =({\mathcal {A}}_{i_{1}i_{2}...i_{n-1}i_n i_{n+1}...i_N})_{1\leqslant i_n\leqslant I_n; 1\leqslant n\leqslant N}. \end{aligned}$$

The values \({\mathcal {A}}_{i_{1}i_{2}...i_{n-1}i_n i_{n+1}...i_N}\) are the entries of \({\mathcal {A}}.\)

Definition 1

[19] Given a tensor \({\mathcal {A}} \in {\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}}\) and a matrix \(M \in {\mathbb {R}}^{J_{n}\times I_{n}} \), the n-mode product of \({\mathcal {A}}\) by M, denoted by \({\mathcal {A}}\times _{n} M\), is the \((I_{1} \times I_{2}...\times I_{n-1}\times J_n \times I_{n+1}\times \cdots \times I_{N})\)-tensor defined by

$$\begin{aligned} ({\mathcal {A}}\times _{n} M)_{i_{1}i_{2}...i_{n-1}j_n i_{n+1}...i_N}=\sum _{i_n}{\mathcal {A}}_{i_{1}i_{2}...i_{n-1}i_n i_{n+1}...i_N}M_{j_n i_n}. \end{aligned}$$

The n-mode product of the tensor \({\mathcal {A}}\) by a vector \(w\in {\mathbb {R}}^{I_{n}}\), denoted by \( {\mathcal {A}}\bar{\times }_{n}w\), is the subtensor of order \((I_{1} \times I_{2}...\times I_{n-1}\times I_{n+1}\times \cdots \times I_{N})\) defined as

$$\begin{aligned} ({\mathcal {A}}\bar{\times }_{n}w)_{i_{1}i_{2}...i_{n-1}i_{n+1}...i_N}=\sum _{i_n=1}^{I_n}{\mathcal {A}}_{i_{1}i_{2}...i_{n-1}i_n i_{n+1}...i_N}w_{i_n}. \end{aligned}$$

Definition 2

(n-mode unfolding matrix) For a given tensor \({\mathcal {A}} \in {\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}}\) and \(1\le n\le N\), the n-mode unfolding matrix of \({\mathcal {A}}\), is the (\(I_n\times I_{1}I_{2}\cdots I_{n-1} I_{n+1}\cdots I_{N}\)) matrix, denoted by \({\mathcal {A}}_{(n)}\) such that

$$\begin{aligned} {\mathcal {A}}_{(n)}(i_n,j)={\mathcal {A}}_{i_{1}...i_N}, \end{aligned}$$

where \(j=1+\sum _{k=1k\ne n}^{N}(i_k-1)L_k\) with \(L_k=\prod _{m=1m\ne n}^{k-1}I_m\). The columns of \({\mathcal {A}}_{(n)}\) are called the mode-n fibres of \({\mathcal {A}}.\)

Definition 3

Let \({\mathcal {A}}\) and \({\mathcal {B}}\) two tensors of the same size \(I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}\), the (Frobenius) inner product of \({\mathcal {A}}\) and \({\mathcal {B}}\) is the scalar defined as

$$\begin{aligned} \langle {\mathcal {A}},{\mathcal {B}}\rangle = \sum _{i_{N}=1}^{I_N}\cdots \sum _{i_{1}=1}^{I_1}{\mathcal {A}}_{i_{1}...i_N}{\mathcal {B}}_{i_{1}...i_N},\; \text {and}\; \parallel {\mathcal {A}} \parallel _{F}=\sqrt{\langle {\mathcal {A}},{\mathcal {A}}\rangle }. \end{aligned}$$

Proposition 1

[13] For \({\mathcal {A}} \in {\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}}\), \(M_1\in {\mathbb {R}}^{J_{n}\times I_{n}}, M_3\in {\mathbb {R}}^{J_{p}\times I_{N}}\) and \(M_2\in {\mathbb {R}}^{K_{n}\times J_{n}}\) (\(n\ne p\)), we have the following properties

  1. 1.

    \(({\mathcal {A}} \times _n M_1)\times _p M_3=({\mathcal {A}} \times _p M_3)\times _n M_1={\mathcal {A}} \times _n M_1\times _p M_3.\)

  2. 2.

    \(({\mathcal {A}} \times _n M_1)\times _n M_2 ={\mathcal {A}} \times _n(M_2M_1)\).

  3. 3.

    If \(M_1\) is orthogonal, then \(\parallel {\mathcal {A}} \times _n M_1\parallel _{F}=\parallel {\mathcal {A}}\parallel _{F}.\)

  4. 4.

    If \(x\in {\mathbb {R}}^{I_n} \) and \(J_{n}=I_n\) then \(({\mathcal {A}} \times _n M_1)\bar{\times }_n x ={\mathcal {A}} \bar{\times }_n(M_{1}^{T}x)\).

  5. 5.

    For \(x\in {\mathbb {R}}^{I_n}\), \({\mathcal {A}} \bar{\times }_n x= {\mathcal {A}} \times _n x^{T}\).

Definition 4

[16]. The Einstein product of two tensors \({\mathcal {A}} \in {\mathbb {R}}^{I_{1} \times \ldots \times I_{N} \times J_{1} \times \cdots \times J_{M}}\) and \({\mathcal {B}} \in {\mathbb {R}}^{J_{1} \times \cdots \times J_{M} \times K_{1} \times \cdots \times K_{L}}\), is the \(I_{1} \times \ldots \times I_{N} \times K_{1} \times \cdots \times K_{L}\) tensor denoted by \({\mathcal {A}} *_{M} {\mathcal {B}}\) whose entries are given by

$$\begin{aligned} \left( {\mathcal {A}} *_{M} {\mathcal {B}}\right) _{i_{1}, \ldots i_{N} k_{1}, \ldots k_{M}}=\sum _{j_{1} \ldots j_{M}} {\mathcal {A}}_{i_{1}, \ldots i_{N} j_{1} \ldots j_{M}} {\mathcal {B}}_{j_{1} \ldots j_{M} k_{1}, \ldots k_{L}} \end{aligned}$$

Definition 5

[16]. The tensor product denoted \(\boxdot ^{(N+1)}\) of two \((N+1)\)-mode tensors \({\mathcal {A}}=\left[ {\mathcal {A}}_{1}, {\mathcal {A}}_{2},\ldots ,{\mathcal {A}}_{m}\right] \in {\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}\times m}\) and \({\mathcal {B}}=\left[ {\mathcal {B}}_{1}, {\mathcal {B}}_{2},\ldots ,{\mathcal {B}}_{n}\right] \in {\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N} \times n}\), where \({\mathcal {A}}_{i}\in {\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}}\) and \({\mathcal {B}}_{i}\in {\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}}\), is the \(m\times n\) matrix whose (i, j) entries, \(i=1,\ldots ,m \) and \(j=1,\ldots ,n,\) is given by

$$\begin{aligned} ({\mathcal {A}}\boxdot ^{(N+1)}{\mathcal {B}})_{i,j}=\langle {\mathcal {A}}_{i},{\mathcal {B}}_{j}\rangle . \end{aligned}$$

Proposition 2

Let \({\mathcal {A}}\), \({\mathcal {B}} \in {\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}\times I_{N+1}}\), \({\mathcal {C}} \in {\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}}\) and \(x\in {\mathbb {R}}^{I_{N+1}}\). Then we have

  1. 1.

    \(({\mathcal {A}}\boxdot ^{(N+1)}{\mathcal {B}})^{T}={\mathcal {B}}\boxdot ^{(N+1)}{\mathcal {A}}\)

  2. 2.

    \(({\mathcal {A}}\boxdot ^{(N+1)}{\mathcal {B}})x={\mathcal {A}}\boxdot ^{(N+1)}({\mathcal {B}}\bar{\times }_{(N+1)}x).\)

  3. 3.

    \(\langle ({\mathcal {A}}\boxdot ^{N+1}{\mathcal {B}})x,x\rangle =\langle {\mathcal {B}}\bar{\times }_{(N+1)}x,{\mathcal {A}}\bar{\times }_{(N+1)}x\rangle .\)

  4. 4.

    \(\langle {\mathcal {C}},{\mathcal {A}}\bar{\times }_{(N+1)}x\rangle =({\mathcal {C}}\boxdot ^{(N+1)}{\mathcal {A}})x\)

Proof

By definitions of the involved tensor products. \(\square \)

3 The HOSVD-TMPE method

First of all, let us recall the Tensor Global Minimal Extrapolation Method (TG-MPE) proposed in [16] that is the starting point of this work.

Let \({\mathcal {S}}_{0},{\mathcal {S}}_{1},{\mathcal {S}}_{2}...\) be a given sequence of real tensors of the same dimension \({I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}}\) and set

$$\begin{aligned} {\mathcal {D}}_{n}={\mathcal {S}}_{n+1}-{\mathcal {S}}_{n}, \hspace{0.3cm} n=0,1,\ldots \end{aligned}$$

Define for some fixed n and k, the \(I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}\times I_{N+1}\) tensor \({\mathbb {D}}_{k}^{(n)}\) by

$$\begin{aligned} {\mathbb {D}}_{k}^{(n)}=\left[ {\mathcal {D}}_{n},{\mathcal {D}}_{n+1},\ldots ,{\mathcal {D}}_{n+k}\right] \; \text {with}\; I_{N+1}=k+1, \end{aligned}$$

such that the \(i^{th}\) frontal slice, obtained by fixing the last index at i, is \(\left[ {\mathbb {D}}^{(n)}_{k}\right] _{:,:,\ldots ,:,i}={\mathcal {D}}_{n+i}\), \(0\le i\le k\).

The TG-MPE method is based on the solution, for \(\bar{\alpha }^{(k)}=\left( \alpha ^{(k)}_{0},\alpha ^{(k)}_{1},\ldots ,\alpha ^{(k)}_{k-1}\right) \in {\mathbb {R}}^{k}\), of the problem

$$\begin{aligned} ({\mathbb {D}}_{k-1}^{(n)}\boxdot ^{N+1}{\mathbb {D}}_{k-1}^{(n)})\bar{\alpha }^{(k)} =-({\mathbb {D}}_{k-1}^{(n)}\boxdot ^{N+1}{\mathcal {D}}_{n+k}), \end{aligned}$$
(1)

for which the authors adopt a tensor QR based approach to obtain the solution (see [16] for details).

Once \(\alpha ^{(k)}_{0},\alpha ^{(k)}_{1},\ldots ,\alpha ^{(k)}_{k-1}\) have been determined, set \(\alpha ^{(k)}_{k}=1\). Provided that \(\displaystyle \sum _{i=0}^{k}\alpha ^{(k)}_{i}\ne 0\), compute the coefficients \(\delta ^{(k)}_{0}, \delta ^{(k)}_{1},\ldots ,\delta ^{(k)}_{k}\) as

$$\begin{aligned} \delta ^{(k)}_{j}=\dfrac{\alpha ^{(k)}_{j}}{\sum _{i=0}^{k}\alpha ^{(k)}_{i}}\hspace{0.7cm} for\hspace{0.3cm} j=0,\ldots ,k. \end{aligned}$$
(2)

Finally we set

$$\begin{aligned} {\mathcal {T}}_{k}^{(n)}=\sum _{j=0}^{k}\delta ^{(k)}_{j}{\mathcal {S}}_{n+j} \end{aligned}$$
(3)

as an approximation to the limit of the sequence \(({\mathcal {S}}_n).\)

Now, let us outline the approach we followed in developing our proposed method.

First, using assertion 1 of Proposition 2, we rewrite the problem in (1) as follows

$$\begin{aligned} {\mathbb {D}}_{k-1}^{(n)}\boxdot ^{N+1}({\mathbb {D}}_{k-1}^{(n)}\bar{\times }_{(N+1)}\bar{\alpha }^{(k)}+{\mathcal {D}}_{n+k})=0. \end{aligned}$$
(4)

The next proposition allows us to transform the above problem to an equivalent minimisation one.

Proposition 3

The equation (4) is equivalent to the minimization least squares tensor problem

$$\begin{aligned} \bar{\alpha }^{(k)}=\underset{x \in {\mathbb {R}}^{k}}{argmin}\parallel {\mathbb {D}}_{k-1}^{(n)}\bar{\times }_{(N+1)}x+{\mathcal {D}}_{n+k}\parallel _F \end{aligned}$$
(5)

Proof

We set \(g(x)=\parallel {\mathbb {D}}_{k-1}^{(n)}\bar{\times }_{(N+1)}x+{\mathcal {D}}_{n+k}\parallel _F^{2}\). For a vector \(h\in {\mathbb {R}}^{k}\) and a non zero scalar t, we have

$$\begin{aligned} g(x+th)&=\parallel {\mathbb {D}}_{k-1}^{(n)}\bar{\times }_{(N+1)}(x+th)+{\mathcal {D}}_{n+k}\parallel _F^2 \\&=g(x) + 2t\langle {\mathbb {D}}_{k-1}^{(n)}\bar{\times }_{(N+1)}x+{\mathcal {D}}_{n+k},{\mathbb {D}}_{k-1}^{(n)}\bar{\times }_{(N+1)}h\rangle \\ {}&\quad + t^{2}\parallel {\mathbb {D}}_{k-1}^{(n)}\bar{\times }_{(N+1)}h\parallel _F^2\\&=g(x) +t\langle {\mathbb {D}}_{k-1}^{(n)}\boxdot ^{N+1}({\mathbb {D}}_{k-1}^{(n)}\bar{\times }_{(N+1)}x+{\mathcal {D}}_{n+k}),h\rangle \\ {}&\quad + t^{2}\parallel {\mathbb {D}}_{k-1}^{(n)}\bar{\times }_{(N+1)}h\parallel _F^2 \end{aligned}$$

Therefore, the gradient of g at x is as \(\bigtriangledown g(x)={\mathbb {D}}_{k-1}^{(n)}\boxdot ^{N+1}({\mathbb {D}}_{k-1}^{(n)}\bar{\times }_{(N+1)}x+{\mathcal {D}}_{n+k})\). It is easy to check that the matrix \({\mathbb {D}}_{k-1}^{(n)}\boxdot ^{N+1}{\mathbb {D}}_{k-1}^{(n)}\) is positive semi-definite, which guarantees the convexity of g. As a result

$$\begin{aligned} \bar{\alpha }^{(k)}=\underset{x \in {\mathbb {R}}^{k}}{\texttt { argmin}}g(x)\quad \Longleftrightarrow \quad \bigtriangledown g (\bar{\alpha }^{(k)})=0. \end{aligned}$$

\(\square \)

Therefore, the problem in (4) is equivalent to

$$\begin{aligned} \underset{\bar{\alpha }^{(k)}\in {\mathbb {R}}^{k}}{\min } \parallel {\mathbb {D}}_{k-1}^{(n)}\bar{\times }_{(N+1)}\bar{\alpha }^{(k)}+{\mathcal {D}}_{n+k}\parallel _F, \end{aligned}$$
(6)

which can be expressed as the following constrained problem

$$\begin{aligned} \underset{\alpha ^{(k)}\in {\mathbb {R}}^{k+1}}{\min }\Vert \mathbb { D}_{k}^{(n)}\bar{\times }_{(N+1)} \alpha ^{(k)}\Vert _{F} \hspace{0.2cm} \text {subject to} \;\alpha ^{(k)}_{k}=1, \;\alpha ^{(k)} = (\alpha ^{(k)}_{0},\ldots ,\alpha ^{(k)}_{k})^T. \end{aligned}$$
(7)

Rewriting the basic problem as a constrained minimization problem is indeed the core concept of this work. Specifically, for our proposed method (HOSVD-TMPE), we have replaced the constraint \(\alpha ^{(k)}_{k}=1\) in (7) with the new constraint \(\parallel \alpha ^{(k)}\parallel _2=1\), resulting in the new constrained minimization problem

$$\begin{aligned}{} & {} \underset{\alpha ^{(k)}\in {\mathbb {R}}^{k+1}}{\min } \parallel \mathbb { D}_{k}^{(n)}\bar{\times }_{(N+1)} \alpha ^{(k)}\parallel _{F}\; \text { subject to}\; \parallel \alpha ^{(k)}\parallel _2=1,\; \alpha ^{(k)}\nonumber \\{} & {} = (\alpha ^{(k)}_{0},\alpha ^{(k)}_{1},\ldots ,\alpha ^{(k)}_{k})^T. \end{aligned}$$
(8)

Again, with \(\alpha ^{(k)}_{0},\alpha ^{(k)}_{1},\ldots ,\alpha ^{(k)}_{k}\) determined and provided \(\sum _{i=0}^{k}\alpha ^{(k)}_{i}\ne 0\), we compute similarly the scalars \(\delta ^{(k)}_{0}, \delta ^{(k)}_{1},\ldots ,\delta ^{(k)}_{k}\) as in (2) and the new sequence term \({\mathcal {T}}_{k}^{(n)}\) as in (3).

Remark 1

The purpose of this new constraint choice is not to obtain a unit solution, as it may seem, since we can achieve that simply through the normalization of the result obtained by TG-MPE. Instead, as will be demonstrated, it enables us to easily characterize the desired approximate solution and develop an efficient algorithm for its determination.

The next theorem recalls the HOSVD decomposition [13], which is a highly valuable tool for establishing the main result in this work.

Theorem 4

(HOSVD) [13] Let \({\mathcal {A}}\) be a real tensor of dimension \(I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}\). Then \({\mathcal {A}}\) can be decomposed as

$$\begin{aligned} {\mathcal {A}}=\Sigma \times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \times _{N}V^{(N)}, \end{aligned}$$
(9)

where \(V^{(n)}=\left[ v_{1}^{(n)}v_{2}^{(n)}...v_{I_n}^{(n)}\right] \) is a unitary \(I_{n}\times I_{n}\) matrix \((1\le n\le N)\), \(\Sigma \) is a real tensor of the same dimension as \({\mathcal {A}}\) and the subtensors \(\Sigma _{i_{n}=m}\) \((1\le m\le I_{n})\) obtained by fixing the \(n^{th}\) index to m, have the following properties

  • All-orthogonality \(\langle \Sigma _{i_{n}=m},\Sigma _{i_{n}=m'}\rangle =0 \hspace{0.4cm} for\hspace{0.2cm} m\ne m'.\)

  • \(\parallel \Sigma _{i_{n}=1}\parallel _{F}\geqslant \parallel \Sigma _{i_{n}=2}\parallel _{F}\geqslant \cdots \parallel \Sigma _{i_{n}=I_{n}}\parallel _{F}\geqslant 0\) for all possible values of n.

The quantity \(\parallel \Sigma _{i_{n}=i}\parallel _{F}\) is called the \(i^{th}\) n-mode singular value of \({\mathcal {A}}\), it is symbolized by \(\sigma _{i}^{(n)}\); and the vector \(v_{i}^{(n)}\) is the \(i^{th}\) n-mode singular vector.

In the following main result, we provide a characterization of the solution \(\alpha ^{(k)}\) of the minimisation problem (8).

Theorem 5

Let \(\sigma _{1}^{(N+1)},\sigma _{2}^{(N+1)},\ldots ,\sigma _{k+1}^{(N+1)}\) be the \((N+1)\)-mode singular values of \({\mathbb {D}}_{k}^{(n)}\) ordered as in

$$\begin{aligned} \sigma _{1}^{(N+1)}\ge \sigma _{2}^{(N+1)}\ge \ldots \ge \sigma _{k+1}^{(N+1)}\geqslant 0, \end{aligned}$$

and let \(\lbrace v_{i}^{(N+1)}\rbrace _{i=1}^{k+1}\) be the corresponding \((N+1)\)-mode singular vectors obtained from the HOSVD,

$$\begin{aligned} \mathbb { D}_{k}^{(n)}=\Sigma \times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \times _{(N+1)}V^{(N+1)}. \end{aligned}$$
(10)

If the smallest \((N+1)\)-mode singular value \(\sigma _{k+1}^{(N+1)}\) of \({\mathbb {D}}_{k}^{(n)}\), is simple, in the sense that \(\sigma _{k}^{(N+1)}\ne \sigma _{k+1}^{(N+1)} \), then the solution \(\alpha ^{(k)} \) to the minimization problem (8) is unique (up to a multiplicative constant \(\rho \), \(\mid \rho \mid =1)\) and is given as \(\alpha ^{(k)}=v_{k+1}^{(N+1)}. \)

Proof

First, let us show that

$$\begin{aligned} \Vert \mathbb {D}_{k}^{(n)}\bar{\times }_{(N+1)}v_{k+1}^{(N+1)}\Vert _{F}=\sigma _{k+1}^{(N+1)}. \end{aligned}$$

In fact, by Assertion 4 of Proposition 1, we have

$$\begin{aligned} \mathbb { D}_{k}^{(n)}\bar{\times }_{(N+1)}v_{k+1}^{(N+1)}&=\Sigma \times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \\&\quad \times _{(N+1)}V^{(N+1)}\bar{\times }_{(N+1)}v_{k+1}^{(N+1)}\\&=\Sigma \times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \\&\quad \times _{N} V^{(N)}\bar{\times }_{(N+1)}((V^{(N+1)})^{T} v_{k+1}^{(N+1)}). \end{aligned}$$

Since \(V^{(N+1)}\) is unitary, one has \( (V^{(N+1)})^{T}v_{k+1}^{(N+1)}=(0,0,\ldots ,1)^{T}=e_{k+1}\in {\mathbb {R}}^{k+1}. \) Therefore, using Assertion 1 and 5 of Proposition 1,

$$\begin{aligned} {\mathbb {D}}_{k}^{(n)}\bar{\times }_{(N+1)}v_{k+1}^{(N+1)}&= \Sigma \times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \times _{N} V^{(N)}\bar{\times }_{(N+1)}e_{k+1}\\&=(\Sigma \bar{\times }_{(N+1)}e_{k+1})\times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \times _{N}V^{(N)}\\&= \Sigma _{i_{(N+1)}=k+1}\times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \times _{N}V^{(N)}. \end{aligned}$$

As a result, using Assertion 3 of Proposition 1, we get

$$\begin{aligned} \Vert {\mathbb {D}}_{k}^{(n)}\bar{\times }_{(N+1)}v_{k+1}^{(N+1)}\Vert _F=\Vert \Sigma _{i_{(N+1)}=k+1}\Vert _F=\sigma _{k+1}^{(N+1)}. \end{aligned}$$

Now, let \(\beta \) be an arbitrary vector in \({\mathbb {R}}^{k+1}\) such that \(\Vert \beta \Vert _2=1\). Since \( V^{(N+1)}=\left[ v_{1}^{(N+1)}v_{2}^{(N+1)}...v_{I_N+1}^{(N+1)}\right] \) is a unitary matrix in \({\mathbb {R}}^{(k+1)\times (k+1)}\), then there exist scalars \(\beta _{1},\ldots ,\beta _{k+1}\) such that

$$\begin{aligned} \beta =\sum _{i=1}^{k+1}\beta _{i}v_{i}^{(N+1)} \;\; \text {with}\; \; \Vert \beta \Vert ^{2}=\sum _{i=1}^{k+1}(\beta _{i})^{2}=1. \end{aligned}$$

Taking into account the orthogonality of \(\lbrace \Sigma _{i}^{(N+1)}\rbrace _{i=1,\ldots , k+1}\), and the fact that \(\sigma _{k+1}^{(N+1)}\) is the smallest \((N+1)\)-mode singular value, we can easily establish that

$$\begin{aligned} \Vert \mathbb { D}_{k}^{(n)}\bar{\times }_{(N+1)}\beta \Vert ^{2}_{F}&=\Vert \sum _{j=1}^{k+1}\beta _{j}\Sigma \times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \times _{(N+1)}V^{(N+1)}\\&\quad \bar{\times }_{(N+1)}v_{j}^{(N+1)}\Vert ^{2}_{F}\\&=\Vert \sum _{j=1}^{k+1}\beta _{j} \Sigma \times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \times _{N} V^{(N)}\bar{\times }_{(N+1)}e_{j}\Vert ^{2}_{F}\\&=\Vert \sum _{j=1}^{k+1}\beta _{j}(\Sigma \bar{\times }_{(N+1)}e_{j})\times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \times _{N}V^{(N)}\Vert ^{2}_{F}\\&= \Vert \sum _{j=1}^{k+1}\beta _{j}\Sigma _{i_{(N+1)}=j}\times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \times _{N}V^{(N)}\Vert ^{2}_{F}\\&=\langle \sum _{j=1}^{k+1}\beta _{j}\Sigma _{i_{(N+1)}=j},\sum _{j=1}^{k+1}\beta _{j}\Sigma _{i_{(N+1)}=j}\rangle \quad (\textit{Orthognality of}\quad V^{(n)},s)\quad \\&=\sum _{j=1}^{k+1}\beta _{j}^{2}\langle \Sigma _{i_{(N+1)}=j},\Sigma _{i_{(N+1)}=j}\rangle \quad (\textit{Orthognality of}\quad \Sigma _{i_{(N+1)}=j},s) \\&= \sum _{j=1}^{k+1}\beta _{j}^{2}(\sigma _{j}^{(N+1)})^{2}\ge (\sigma _{k+1}^{(N+1)})^{2}(\sum _{j=1}^{k+1}\beta _{j}^{2})=(\sigma _{k+1}^{(N+1)})^{2}. \end{aligned}$$

Therefore

$$\begin{aligned} \Vert {\mathbb {D}}_{k}^{(n)}\bar{\times }_{(N+1)}\beta \Vert _{F}\ge \sigma _{k+1}^{(N+1)}, \end{aligned}$$

which leads to

$$\begin{aligned} \min _{\Vert \alpha ^{(k)}\Vert =1}\Vert \mathbb { D}_{k}^{(n)}\bar{\times }_{(N+1)}\alpha ^{(k)}\Vert _{F} =\Vert \mathbb { D}_{k}^{(n)}\bar{\times }_{(N+1)}v_{k+1}^{(N+1)}\Vert _{F}=\sigma _{k+1}^{(N+1)}. \end{aligned}$$

\(\square \)

4 Implementation of HOSVD-TMPE

As demonstrated in the previous section, determining the sequence term \({\mathcal {T}}{n}^{(k)}\) in (3) requires the computation of \(v{k+1}\), the \((k+1)^{th}\) vector of the \((N+1)\)-mode matrix \(V^{(N+1)}\) corresponding to the smallest \((N+1)\)-mode singular value \(\sigma _{k+1}^{(N+1)}\) from the decomposition (10). Obtaining the matrix \(V^{(N+1)}\) directly through HOSVD applied to \({\mathbb {D}}{k}^{(n)}\) can be expensive. However, in this case, we employ a less computationally intensive method to obtain the matrix \(V^{(N+1)}\) and consequently, the vector \(v{k+1}^{(N+1)}\). To begin, let us introduce the following lemma, which was proven in [3].

Lemma 1

[3] Let \({\mathcal {A}}\) be a real tensor of dimension \(I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N},\) and consider its HOSVD decomposition as

$$\begin{aligned} {\mathcal {A}}=\Sigma \times _{1}V^{(1)}\times _{2}V^{(2)}\times _{3}V^{(3)}\cdots \times _{N}V^{(N)}. \end{aligned}$$
(11)

Then a matrix representation of (11) can be obtained, for \(n\in \left\{ 1,\cdots ,N\right\} \), as follows

$$\begin{aligned} {\mathcal {A}}_{(n)}=V^{(n)}\Sigma _{(n)}( V^{(n+1)}\otimes V^{(n+2)}\otimes \cdots \otimes V^{(N)}\otimes V^{(1)}\cdots \otimes V^{(n-1)})^{T}, \end{aligned}$$
(12)

where \(\otimes \) stands for the Kronecker product of matrices.

Proposition 6

For each \(n\in \left\{ 1,\ldots ,N\right\} \) we have:

$$\begin{aligned} {\mathcal {A}}_{(n)}{\mathcal {A}}_{(n)}^{T}=V^{(n)}\Sigma _{(n)}\Sigma _{(n)}^{T} (V^{(n)})^{T} \end{aligned}$$
(13)

Proof

We use (12) and the orthogonality of the matrices \(V^{(n)}\), 1\(\le n\le N\). \(\square \)

The decomposition (13) is, in fact, the spectral decomposition of the symmetric matrix \({\mathcal {A}}_{(n)}{\mathcal {A}}_{(n)}^{T}\). Therefore, to get the n-mode matrix \(V^{(n)}\) appearing the HOSVD-decomposition of the tensor \({\mathcal {A}}\), we can compute it throughout the eigenvalue decomposition (EVD) of the \(I_n \times I_n\) matrix \({\mathcal {A}}_{(n)}{\mathcal {A}}_{(n)}^{T}\).

Now, we adopt this process to determine the matrix \(V^{(N+1)}\) in (10). We first compute the unfolding matrix \(({\mathbb {D}}_{k}^{(n)})_{(N+1)}\) and the matrix \(M=(\mathbb { D}_{k}^{(n)})_{(N+1)}({\mathbb {D}}_{k}^{(n)})_{(N+1)}^{T}\) of size \((k+1)\times (k+1)\). Therefore, applying the EVD decomposition on M allows us to obtain the matrix \(V^{(N+1)}\) ( we have \(M=V^{(N+1)}\Sigma (V^{(N+1)})^T\)). Then, the \((k+1)^{th}\) vector (solution \(\alpha ^{(k)}\)) \(v_{k+1}=V^{(N+1)}e_{k+1}\) where \(e_{k+1}=(0,0,\ldots ,1)^{T}\in {\mathbb {R}}^{k+1}\).

Remark 2

In practice, the integer k is not typically large. Therefore, applying the Eigenvalue Decomposition EVD to the symmetric positive semi definite \((k+1)\times (k+1)\) matrix \(M=(\mathbb { D}_{k}^{(n)})_{(N+1)}({\mathbb {D}}_{k}^{(n)})_{(N+1)}^{T}\) is less computationally expensive compared to performing the HOSVD decomposition of the tensor \({\mathbb {D}}_{k}^{(n)}.\)

After obtaining the solution \(\alpha ^{(k)}\), we used (2) and (3) for computing the extrapolated tensor \({\mathcal {T}}^{(k)}_{n}\). We summarize the different steps of the implementation of HOSVD-TMPE in Algorithm 1.

Algorithm 1
figure a

HOSVD-TMPE

Full size image

It is clear that Algorithm 1 outlines only the computation of a single extrapolated tensor \({\mathcal {T}}^{(k)}_{n}\) (with fixed values for n and k), and does not provide any information about the sequence \(({\mathcal {T}}^{(k)}_{n})_{n}\) as n varies. To address this aspect, in the experimental section of this work, we employ two distinct schemes following the manner in which the sequence is generated.

Algorithm 2
figure b

HOSVD-TMPE for fixed-point problems

Full size image

In case where the sequence \(({\mathcal {S}}_{n})\) is produced by a some fixed-point process

$$\begin{aligned} {\mathcal {S}}_{n+1}={\mathcal {F}}({\mathcal {S}}_{n}), \end{aligned}$$
(14)

we apply our proposed algorithm 1 in the restarted acceleration scheme explained in [10, 11]. That is, starting from an iterate \({\mathcal {S}}_{n}\), we generate via the fixed-point process 14 a sequence of iterates \(\left\{ {\mathcal {S}}_{n}\right\} _{i=0}^{k+1}\) and then use Algorithm 1 to produce \( {\mathcal {T}}^{(k)}_{n}\). Next, we use \({\mathcal {F}}({\mathcal {T}}^{(k)}_{n})\) as the starting point of (14) and the process continues. In the absence of a specific convergence measurement tool, it is generally acceptable to stop computations after a fixed number of iterations \(iter_{max}\) or when the relative residual error

$$\begin{aligned} \texttt {res}({\mathcal {T}}^{(k)}_{n}):=\frac{\parallel {\mathcal {T}}^{(k)}_{n}-{\mathcal {T}}^{(k)}_{n-1} \parallel _F}{\parallel {\mathcal {T}}^{(k)}_{n}\parallel _F} \end{aligned}$$
(15)

is less than a given threshold \(\epsilon \).

We summarized that in Algorithm 2. The error in Step 7 can either represent the relative residual res in (15) or some specific error depending on the studied problem.

Now, in cases where the sequence is not of a fixed-point type or when we lack information about its production process, we can apply our method in the acceleration scheme (see Fig. 1) as follows: we apply the extrapolation on the first \(k+2\) iterates to produce the first term \({\mathcal {T}}^{(k)}_{0}\). Next, we start from the second iterate \({\mathcal {S}}_{1}\) and consider a set of \(k+2\) iterates to produce the second term \({\mathcal {T}}^{(k)}_{1}\) via extrapolation and this process continues. The following figure illustrates this acceleration scheme.

Fig. 1
figure 1

The acceleration scheme

Full size image

Now, through the following result, we reveal a class of sequences on which the application of HOSVD-TMPE produces, just from a certain finite number of terms and in one time, the sought limit \({\mathcal {S}}\). Such property is known as finite termination property, see [27].

Theorem 7

Let \({\mathcal {S}}\) be the limit of the tensor sequence \(({\mathcal {S}}_{n})\) and let \({\mathcal {E}}_{n}={\mathcal {S}}_{n}-{\mathcal {S}}\) and \({\mathcal {D}}_{n}={\mathcal {S}}_{n+1}-{\mathcal {S}}_{n}\). Assume that there exists a fixed number k such that, for all \(n=0,1,\ldots \)

$$\begin{aligned} \sum _{i=0}^{k}\alpha ^{(k)}_i{\mathcal {E}}_{n+i}=0\hspace{1cm} with\hspace{0.5cm} \sum _{i=0}^{k}\alpha ^{(k)}_i\ne 0 \hspace{0.4cm}and\hspace{0.4cm} \alpha ^{(k)}_0 \alpha ^{(k)}_k \ne 0, \end{aligned}$$
(16)

and the tensors \(\lbrace {\mathcal {D}}_{0},{\mathcal {D}}_{1},\ldots ,{\mathcal {D}}_{k-1}\rbrace \) are linearly independent. Then the tensor \({\mathcal {T}}^{(n)}_k\) obtained by applying HOSVD-TMPE to the \(k+2\) tensors \({\mathcal {S}}_{n},{\mathcal {S}}_{n+1},\ldots ,{\mathcal {S}}_{n+k+1},\) satisfies \({\mathcal {T}}^{(n)}_k={\mathcal {S}}\) for all \(n=0,1,\ldots \).

Proof

Let us first show by induction on n the linear independence of \( {\mathcal {D}}_{n},{\mathcal {D}}_{n+1},\ldots ,\) \({\mathcal {D}}_{n+k-1}\). For \(n=0\), it is true by the hypothesis. Assume now that that \( {\mathcal {D}}_{n},{\mathcal {D}}_{n+1},\ldots ,{\mathcal {D}}_{n+k-1}\) are linearly independent, and show that so is for \( {\mathcal {D}}_{n+1},{\mathcal {D}}_{n+2},\) \(\ldots ,{\mathcal {D}}_{n+k}\). From (16), we get

$$\begin{aligned} \sum _{i=0}^{k}\alpha ^{(k)}_i{\mathcal {D}}_{n+i}=0,\hspace{1cm}n=1,2,\ldots . \end{aligned}$$
(17)

Since \(\alpha ^{(k)}_k\ne 0\), let us set \(\alpha ^{(k)}_k=-1\). Then (17) becomes

$$\begin{aligned} {\mathcal {D}}_{n+k}= \sum _{i=0}^{k-1}\alpha ^{(k)}_i{\mathcal {D}}_{n+i} \end{aligned}$$
(18)

To show that \({\mathcal {D}}_{n+1},{\mathcal {D}}_{n+2},\ldots ,{\mathcal {D}}_{n+k}\) are independent, assume that there exist scalars \(\beta _{1},\beta _{2},\ldots ,\beta _{k}\) such that

$$\begin{aligned} \sum _{i=1}^{k}\beta _i{\mathcal {D}}_{n+i}=0. \end{aligned}$$
(19)

Substituting (18) into (19) and rearranging terms leads to

$$\begin{aligned} \beta _{k}\alpha ^{(k)}_{0}{\mathcal {D}}_{n}+\sum _{i=1}^{k-1}(\beta _i+\beta _k\alpha ^{(k)}_i){\mathcal {D}}_{n+i}=0. \end{aligned}$$
(20)

The induction hypothesis implies that

$$\begin{aligned} \beta _{k}\alpha ^{(k)}_{0}=0\hspace{0.5cm} {\text {and}} \hspace{0.5cm} \beta _i+\beta _k\alpha ^{(k)}_i=0\hspace{0.5cm} {\text {for}} \hspace{0.3cm}i=1,\ldots , k-1. \end{aligned}$$

Since \(\alpha ^{(k)}_{0}\ne 0\), it follows that

$$\begin{aligned} \beta _{1}=\beta _{2}=\ldots =\beta _{k}=0 \end{aligned}$$

which implies the linear independence of \({\mathcal {D}}_{n+1},{\mathcal {D}}_{n+2},\ldots ,{\mathcal {D}}_{n+k}\).

On the other hand, using (16), we obtain

$$\begin{aligned} \sum _{i=0}^{k}\alpha ^{(k)}_i({\mathcal {S}}_{n+i}-{\mathcal {S}})=\sum _{i=0}^{k}\alpha ^{(k)}_i{\mathcal {S}}_{n+i}-(\sum _{i=0}^{k}\alpha ^{(k)}_i){\mathcal {S}}=0, \end{aligned}$$

from which it follows that

$$\begin{aligned} {\mathcal {S}}=\dfrac{\sum _{i=0}^{k}\alpha ^{(k)}_i{\mathcal {S}}_{n+i}}{\sum _{i=0}^{k}\alpha ^{(k)}_i}. \end{aligned}$$

Therefore, setting \( \check{\delta }^{(k)}_i=\dfrac{\alpha ^{(k)}_i}{\sum _{i=0}^{k}\alpha ^{(k)}_i}\), gives

$$\begin{aligned} {\mathcal {S}}=\sum _{i=0}^{k}\check{\delta }^{(k)}_i{\mathcal {S}}_{n+i}, \; {\text {with}}\; \sum _{i=0}^{k}\check{\delta }^{(k)}_i=1 . \end{aligned}$$
(21)

Again from (16), we have

$$\begin{aligned} {\mathbb {D}}_{k}^{(n)}\times _{(N+1)}\alpha ^{(k)}= \sum _{i=0}^{k}\alpha ^{(k)}_i{\mathcal {D}}_{n+i}=\sum _{i=0}^{k}\alpha ^{(k)}_i{\mathcal {E}}_{n+i+1}-\sum _{i=0}^{k}\alpha ^{(k)}_i{\mathcal {E}}_{n+i}=0. \end{aligned}$$

The linear independence of \(\lbrace {\mathcal {D}}_{n},{\mathcal {D}}_{n+1},\ldots ,{\mathcal {D}}_{n+k-1}\rbrace \) implies that the problem \({\mathbb {D}}_{k}^{(n)}\times _{(N+1)}\alpha ^{(k)}=0\) along with \(\Vert \alpha ^{(k)}\Vert =1\) has a unique solution (up to a multiplicative constant \(\rho \), \(\mid \rho \mid =1)\). That is, the scalars \(\check{\delta }^{(k)}_i\) in (21) are the same as \(\delta ^{(k)}_i\) in \( {\mathcal {T}}^{(k)}_{n}=\sum _{i=0}^{k}\delta ^{(k)}_i {\mathcal {S}}_{n+i}\) resulting from HOSVD-TMPE, and as a result \( {\mathcal {T}}^{(k)}_{n}={\mathcal {S}}.\) \(\square \)

5 Error analysis

In this section, we consider a convergent tensor sequence \(({\mathcal {S}}_n)\) with limit \({\mathcal {S}}\) obtained via the fixed-point process (14):

$$\begin{aligned} {\mathcal {S}}_{n+1}={\mathcal {F}}({\mathcal {S}}_{n}), \end{aligned}$$

where \({\mathcal {S}}_{0}\) is a given tensor and \({\mathcal {F}}\) is assumed to be a differentiable function from \({\mathbb {R}}^{I_{1}\times I_{2}\times \cdots \times I_{N}}\) into \( {\mathbb {R}}^{I_{1}\times I_{2}\times \cdots \times I_{N}}\). We associate with the iterate \({\mathcal {S}}_{n}\), the residual error given as:

$$\begin{aligned} {\mathcal {R}}({\mathcal {S}}_{n})={\mathcal {F}}({\mathcal {S}}_{n})-{\mathcal {S}}_{n}={\mathcal {S}}_{n+1}-{\mathcal {S}}_{n}. \end{aligned}$$
(22)

The limit \({\mathcal {S}}\) satisfies the equations \({\mathcal {S}}={\mathcal {F}}({\mathcal {S}})\) and \({\mathcal {R}}({\mathcal {S}})=0.\)

As examples of \({\mathcal {F}}\), we consider the following cases:

  1. 1.

    \({\mathcal {F}}\) is linear:

    • \({\mathcal {F}}({\mathcal {X}})={\mathcal {X}}\times _{N}A+{\mathcal {B}},\) with \({\mathcal {B}}\in {\mathbb {R}}^{I_{1}\times I_{2}\times \cdots \times I_{N}}\) and \(A\in {\mathbb {R}}^{I_{N}\times I_{N}}\) such that \((I-A)\) is non-singular.

    • \({\mathcal {F}}({\mathcal {X}})= {\mathcal {A}}*_{N}{\mathcal {X}}+{\mathcal {B}}\) with \({\mathcal {B}}\in {\mathbb {R}}^{I_{1}\times I_{2}\times \cdots \times I_{N}}\) and \({\mathcal {A}}\in {\mathbb {R}}^{I_{1}\times I_{2}\times \cdots \times I_{N}\times I_{1}\times I_{2}\times \cdots \times I_{N}}\) and \(*_{N}\) stands for the Einstein product (Definition 4).

  2. 2.

    \({\mathcal {F}}\) is not linear: \({\mathcal {F}}({\mathcal {X}})= {\mathcal {X}}^{T}*_{N}{\mathcal {A}}*_{N}{\mathcal {X}}+{\mathcal {X}}^{T}*_{N}{\mathcal {C}}\quad {\text {with}} \quad {\mathcal {A}}, {\mathcal {C}}\in {\mathbb {R}}^{I_{1}\times I_{2}\times \cdots \times I_{N}\times I_{1}\times I_{2}\times \cdots \times I_{N}}\). Notice that in this case, one has

    $$\begin{aligned} {\mathcal {F}}({\mathcal {X}})=\dfrac{\partial {\mathcal {F}}}{\partial {\mathcal {X}}}({\mathcal {S}})*_{N}({\mathcal {X}}-{\mathcal {S}})+ {\mathcal {F}}({\mathcal {S}})+\textbf{O}(\parallel {\mathcal {X}}-{\mathcal {S}}\parallel _{F}^{2}) \quad \text {as}\quad {\mathcal {X}}\longrightarrow {\mathcal {S}} \end{aligned}$$

    where the tensor \(\dfrac{\partial {\mathcal {F}}}{\partial {\mathcal {X}}}({\mathcal {S}})={\mathcal {A}}*_{N}{\mathcal {S}}-{\mathcal {C}}\) is the gradient of \({\mathcal {F}}\) at \({\mathcal {S}}\). Thus for a large n, the sequence \(({\mathcal {S}}_n)\) can be generated as follows

    $$\begin{aligned} {\mathcal {S}}_{n+1}={\mathcal {F}}({\mathcal {S}}_n)\approx \dfrac{\partial {\mathcal {F}}}{\partial {\mathcal {X}}}({\mathcal {S}})*_{N}({\mathcal {S}}_n-{\mathcal {S}})+ {\mathcal {F}}({\mathcal {S}}). \end{aligned}$$
    (23)

    That is, the sequence \(({\mathcal {S}}_n)\) behaves as if it were being generated by approximate linear system of the form \(({\mathcal {I}}-{\mathcal {P}})*_{N}{\mathcal {X}}\approx {\mathcal {B}}\) through

    $$\begin{aligned} {\mathcal {X}}_{n+1}={\mathcal {P}}*_{N}{\mathcal {X}}_n+{\mathcal {B}} \end{aligned}$$

    with \({\mathcal {P}}=\dfrac{\partial {\mathcal {F}}}{\partial {\mathcal {X}}}({\mathcal {S}})\) and \({\mathcal {B}}=({\mathcal {I}}-{\mathcal {P}})*_{N}{\mathcal {S}}.\)

Coming back to the general case, assume that \({\mathcal {F}}\) has a unique fixed point denoted by \({\mathcal {S}}.\) Applying HOSVD-TMPE on \(({\mathcal {S}}_n)\), the residual \( {\mathcal {R}}({\mathcal {T}}^{(k)}_{n})={\mathcal {T}}^{(k)}_{n+1}-{\mathcal {T}}^{(k)}_{n} \) can be expressed as

$$\begin{aligned} {\mathcal {R}}({\mathcal {T}}^{(k)}_{n})\cong \sum _{i=0}^{k}\delta ^{(k)}_i{\mathcal {D}}_{n+i}={\mathbb {D}}_{k}^{(n)}\times _{(N+1)}\delta ^{(k)}, \; \text {with}\; \delta ^{(k)}=\left( \delta ^{(k)}_0,\delta ^{(k)}_2,\ldots ,\delta ^{(k)}_k \right) ^T, \end{aligned}$$
(24)

where ’\(\cong \)’ represents exact equality ’\(=\)’ when the sequence \(({\mathcal {S}}_{n})\) is generated linearly, while, it is just an approximation ’\(\approx \)’ when \({\mathcal {F}}\) is non-linear.

Assume that \(({\mathcal {S}}_{n})\) is generated linearly, the subsequent theorem demonstrates that the computation of \(\Vert {\mathcal {R}}({\mathcal {T}}^{(k)}_{n})\Vert _{F}\) can be achieved without incurring any additional computational expense, relying solely on the quantities derived from our algorithm, and without the need to directly compute \({\mathcal {R}}({\mathcal {T}}^{(k)}_{n})\). The result remains true for the nonlinear case when replacing \(=\) with \(\approx \).

Theorem 8

The residual \({\mathcal {R}}({\mathcal {T}}^{(k)}_{n})\) in (24) satisfies

$$\begin{aligned} \Vert {\mathcal {R}}({\mathcal {T}}^{(k)}_{n})\Vert _{F}=\dfrac{\sigma _{k+1}^{(N+1)}}{\mid \displaystyle \sum _{i=0}^{k}\alpha ^{(k)}_{i}\mid }, \end{aligned}$$
(25)

where \(\sigma _{k+1}^{(N+1)}\) is the smallest \((N+1)\)-mode singular value of \({\mathbb {D}}_{k}^{(n)}.\)

Proof

Using the relation (2), it follows that

$$\begin{aligned} {\mathbb {D}}_{k}^{(n)}\times _{(N+1)}\delta ^{(k)}=\dfrac{({\mathbb {D}}_{k}^{(n)}\times _{(N+1)}\alpha ^{(k)})}{\displaystyle \sum _{i=0}^{k}\alpha ^{(k)}_{k}} \end{aligned}$$

with \(\alpha ^{(k)}=\left( \alpha ^{(k)}_0,\alpha ^{(k)}_2,\ldots ,\alpha ^{(k)}_k \right) ^T\) is the solution of (8). Then, using Theorem 5, we obtain

$$\begin{aligned} \Vert {\mathcal {R}}({\mathcal {T}}^{(k)}_{n})\Vert _{F}=\frac{1}{ \mid \displaystyle \sum _{i=0}^{k}\alpha ^{(k)}_{k}\mid }\Vert {\mathbb {D}}_{k}^{(n)}\times _{(N+1)}\alpha ^{(k)}\Vert _{F}=\dfrac{\sigma _{k+1}^{(N+1)}}{\mid \displaystyle \sum _{i=0}^{k}\alpha ^{(k)}_{k}\mid }. \end{aligned}$$

\(\square \)

6 Numerical experiments

In this section, we will illustrate, via some numerical experiments, the effectiveness of our proposed method (HOSVD-TMPE). We compared it in the examples below, in addition to the basic sequences (Basic-Iterations), with the TG-MPE method and the Nesterov’s transformation [23] defined by

$$\begin{aligned} {\mathcal {T}}_{n+1}^{Nv}={\mathcal {X}}_{n+1}+\frac{\eta _{n}+1}{\eta _{n+1}}({\mathcal {X}}_{n+1}-{\mathcal {X}}_{n}), \end{aligned}$$

where \(\lbrace \eta _{n}\rbrace \) is the scalar sequence given by \(\eta _{n+1} =\dfrac{\sqrt{4(\eta _{n})^{2}+1)+1}}{2}\) with \(\eta _{1}=1.\)

For Examples 1, 2, and 4, we implemented the HOSVD-TMPE and TG-MPE methods using the restarted acceleration scheme outlined in Algorithm 2. Since the exact solution is known, we employed the relative error

$$\begin{aligned} \texttt {e}({\mathcal {T}}^{(k)}_{n})=\frac{\parallel {\mathcal {T}}^{(k)}_{n} -{\mathcal {S}}\parallel _F}{\parallel {\mathcal {S}}\parallel _F}, \end{aligned}$$
(26)

to illustrate the behaviour of the produced sequences.

For Example 3, we adopted the acceleration scheme outlined in Fig. 1, utilizing the residual error-norm

$$\begin{aligned} {\mathcal {R}}e({\mathcal {T}}^{(k)}_{n})= \parallel {\mathcal {B}}-{\mathcal {A}}*_2 {\mathcal {T}}_{n}^{(k)}\parallel , \end{aligned}$$
(27)

to assess the convergence behaviour of the methods.

In addition, in Example 4, which addresses image restoration problems, we used the PSNR (Peak Signal-to-Noise Ratio) to assess the quality of the restored images. Furthermore, in this specific example, we evaluated the convergence rates of TG-MPE and HOSVD-TMPE by considering the ratio \(\frac{\parallel {\mathcal {T}}_{n}^{method}-{\mathcal {S}}\parallel _{F}}{\parallel {\mathcal {S}}_{n}-{\mathcal {S}}\parallel _{F}}.\)

As shown in Algorithm 2, the iteration process is terminated as soon as the norm of the used error is less than predefined \(\epsilon \), or the number of iterations reaches a given number \(iter_{max}\). We carried out the computations using MATLAB 2023a in HP computer running Windows 11 with Intel Core i7 and 16 GB RAM.

6.1 Example 1

We consider tensor sequence \(({{\mathcal {S}}_{n}})\) with \({{\mathcal {S}}_{n}}\in {\mathbb {R}}^{d\times d \times d}\), obtained from the linear iterative scheme

$$\begin{aligned} {\mathcal {S}}_{n+1}={\mathcal {S}}_{n}\times _{3}A+{\mathcal {B}},\hspace{0.5cm} n=0,1,\ldots \end{aligned}$$

\(A=V\Sigma V^{T}\in {\mathbb {R}}^{d\times d}\) where V is a random orthogonal matrix, and \(\Sigma \) is a diagonal matrix such that \( \Sigma (i,i)=1-0.95\times \frac{i}{d}\), \(i=1,..,d\). The tensor \({\mathcal {B}}\) is such that the limit (exact solution) is the tensor \({\mathcal {S}}\) with all elements equal to one:

$$\begin{aligned} {\mathcal {B}}={\mathcal {S}}\times _{3}(I-A). \end{aligned}$$

Fig. 2 illustrates the relative error-norm versus the iteration index n for both the Basic iteration and Nesterov process, TG-MPE, and our proposed method HOSVD-TMPE with \(k=3\), considering different dimensions (\(d=25\) and 40). We set \(\epsilon \) to \(10^{-14}\). The curves clearly reveal the acceleration effect of our method, showcasing its superiority compared to TG-MPE and Nesterov.

Fig. 2
figure 2

The relative error for dimensions \(d=25\) (left) and \(d=40\) (right) for the Basic-iteration, Nesterov, TG-MPE and HOSVD-TMPE (Example 1)

Full size image

6.2 Example 2

In this example, we consider the tensor sequence \(({\mathcal {S}}_{n})\) from \({\mathbb {R}}^{N\times N \times N}\) obtained by the following linear iterative scheme

$$\begin{aligned} {\mathcal {S}}_{n+1}={\mathcal {A}}*_{N}{\mathcal {S}}_{n}+{\mathcal {B}},\hspace{0.5cm} n=0,1,\ldots \end{aligned}$$

with \({\mathcal {A}}\in {\mathbb {R}}^{N\times N\times N\times N\times N\times N}\) such that

$$\begin{aligned} {\mathcal {A}}_{i,j,k,i,j,k}=(i+j+k)/(3*N)\hspace{0.5cm} and \hspace{0.5cm} {\mathcal {A}}_{i,i,i,i,i,i}=1-0.01*i. \end{aligned}$$

The tensor right-hand \({\mathcal {B}}\) is such that the limit \({\mathcal {S}}\) is the tensor whose all elements equal to one, and is given by

$$\begin{aligned} {\mathcal {B}}=(I-{\mathcal {A}})*_{N}{\mathcal {S}}. \end{aligned}$$

Fig. 3 illustrates the behavior of the relative error-norm for the basic sequence, the Nesterov process, TG-MPE, and our method HOSVD-TMPE (\(k=3\)) across different dimensions (\(N=10\) and \(N=15\)). We set \(\epsilon \) to \(10^{-13}\) as a stopping criterion. It is evident that the application of TG-MPE and HOSVD-TMPE results in much faster convergence compared to Basic Iterations and the Nesterov process. As observed in the previous example, the HOSVD-TMPE method the HOSVD-TMPE method exhibits rapid convergence.

Fig. 3
figure 3

The relative error-norm for dimensions \(N=10\) (left) and \(N=15\) (right) for the Basic-iteration, TG-MPE, Nesterov and HOSVD-TMPE (Example 2)

Full size image

6.3 Example 3

In this example, we consider the partial differential equation

$$\begin{aligned} \left\{ \begin{aligned} \dfrac{\partial ^2 u}{\partial x^2}+\dfrac{\partial ^2 u}{\partial y^2}=0&\hspace{1.2cm}\Omega =\left] 0,1\right[ \times \left] 0,1\right[ , \\ u(0,y)=0,&\hspace{0.5cm} u(1,y)= \sin 3\pi y,\\ u(x,0)=0,&\hspace{0.5cm} u(x,1)= \sin 3\pi x\cos \pi x. \end{aligned} \right. \end{aligned}$$
(28)

The central finite difference discretization of (28) leads to the following tensor equation with Einstein product (see Definition 4)

$$\begin{aligned} {\mathcal {A}}*_2 {\mathcal {X}}={\mathcal {B}},\hspace{0.5cm}{\mathcal {X}}=(x_{kl})\in {\mathbb {R}}^{N\times N}, \end{aligned}$$
(29)

with \({\mathcal {A}}=(\alpha _{ijkl})\in {\mathbb {R}}^{N\times N\times N\times N}\) and \({\mathcal {B}}=(\beta _{ij}) \in {\mathbb {R}}^{N\times N}\) such that

$$\begin{aligned}{} & {} \alpha _{ijkl} = q_{mn}, \hspace{0.5cm} m = ivec([i, j], [N, N]), \hspace{0.5cm} n = ivec([k, l], [N,N]), \\{} & {} \beta _{ij} = b_t, \hspace{0.5cm} t = ivec([i, j], [N, N])\; \text {and} \; Q = [q_{mn}]:= (F \otimes I_N + I_N \otimes E), \end{aligned}$$

where \(\otimes \) denotes the Kronecker product, ivec is the index mapping function defined as follows: For given integers \(j_1\), \(j_2\) and dimensions \(N_1\), \(N_2\), the integer \(ivec([i, j], [N_1, N_2])\) is given by

$$\begin{aligned} ivec([j_1, j_2], [N_1, N_2])= j_1+ (j_2-1)N_1N_2. \end{aligned}$$

\(F = tridiag(1,-4,1)\) and \( E = [e_{ij}]\) are tridiagonal and diagonal matrices of order N and \( b = (b_i) \in {{\mathbb {R}}}^{N^2}\), defined by

$$\begin{aligned} e_{ij}=\left\{ \begin{aligned} 1,&\hspace{1.2cm}{\text {if}}\hspace{0.2cm} \mid i-j\mid =1, \\ 0,&\hspace{1.4cm} {\text {otherwise}},\\ \end{aligned} \right. \end{aligned}$$

\(b_t= \left\{ \begin{aligned} -\sin \frac{3t}{N+1}\pi \hspace{1.2cm}&\text {if}\hspace{0.2cm}t=vN, \hspace{0.2cm} v=1,\ldots ,N, \\ -\sin \frac{3t}{N+1}\pi \cos \frac{t}{N+1}\pi \hspace{0.2cm}&\text {if} \hspace{0.2cm}t= (N - 1)N + w,\hspace{0.2cm} w=1,\ldots ,N-1,\\ -\sin \frac{3N}{N+1}\pi (1 + \cos \frac{N}{N+1}\pi )&\hspace{0.2cm}\text {if} \hspace{0.2cm}t=N^2, \\ \hspace{-2cm}0 \hspace{1.7cm}&\text {otherwise}. \end{aligned} \right. \)

We solve (29) using the following iterative scheme [29]:

$$\begin{aligned} {\left\{ \begin{array}{ll} {\mathcal {X}}_{n+1} ={\mathcal {X}}_{n} +\dfrac{Tr({\mathcal {P}}_{n}^{T} *_2 {\mathcal {R}}_{n})}{Tr({\mathcal {P}}_{n}^{T} *_2 {\mathcal {A}}*_2 {\mathcal {P}}_{n})}{\mathcal {P}}_{n}, \\ {\mathcal {R}}_{n+1}= {\mathcal {B}}-{\mathcal {A}}*_2 {\mathcal {X}}_{n+1},\\ {\mathcal {P}}_{n+1} ={\mathcal {R}}_{n+1} -\dfrac{Tr({\mathcal {P}}_{n}^{T}*_2{\mathcal {A}} *_2 {\mathcal {R}}_{n+1})}{Tr({\mathcal {P}}_{n}^{T}*_2{\mathcal {A}} *_2 {\mathcal {P}}_{n})}{\mathcal {P}}_{n}. \end{array}\right. } \end{aligned}$$
(30)

with \({\mathcal {P}}_{0}={\mathcal {R}}_{0}={\mathcal {B}}-{\mathcal {A}}*_2 {\mathcal {X}}_{0}\) where \({\mathcal {X}}_{0}\) is an initial tensor guess.

In Table 1, we present the iteration number n, the residual error-norm \({\mathcal {R}}e({\mathcal {T}}_{n}^{(k)})=\parallel {\mathcal {B}}-{\mathcal {A}}*_2 {\mathcal {T}}_{n}^{(k)}\parallel _{F}\), and the CPU time for the four methods for different dimensions \(N=10, 40\) and 100. Note that the stopping criterion \(\epsilon \) is adjusted according to the dimension N ( \(\epsilon =10^{-16}\) for \(N=10\), \(\epsilon =10^{-8}\) for \(N=40\) and \(\epsilon =10^{-2}\) for \(N=100\) ). The results highlight the acceleration effect of our proposed method (HOSVD-TMPE). Across various dimensions (\(N=10, 40,\) and 100), both the number of iterations and the associated CPU time for HOSVD-TMPE and TG-MPE are lower compared to those obtained with the initial sequence (Basic Iteration) and the Nesterov process. We can also note the effectiveness of HOSVD-TMPE in comparison to TG-MPE method, particularly when considering the case of \(N=100\).

Table 1 Comparison of the required iteration number, residual error \({\mathcal {R}}e\), and CPU time for Basic Iterations (Scheme (30)), Nesterov, TG-MPE, and HOSVD-TMPE (Example 3)
Full size table

In Fig. 4, we have plotted the residual error \({\mathcal {R}}e\) versus the iteration number n for four methods: Basic Iterations, Nesterov, TG-MPE, and HOSVD-TMPE, considering two different values of dimensions, \(N=30\) (left) and \(N=50\) (right). Iterations are terminated when the residual \({\mathcal {R}}e\) reaches \(10^{-8}\). The acceleration effect of HOSVD-TMPE is evident, showcasing its competitiveness with TG-MPE for both \(N=30\) and \(N=50\). They exhibit nearly similar behaviors, with a slight advantage observed for HOSVD-TMPE.

Fig. 4
figure 4

The residual error \({\mathcal {R}}e\) for dimensions \(N=30\) (left) and \(N=50\) (right) for the Basic-iteration (30), Nesterov, TG-MPE and HOSVD-TMPE (Example 3)

Full size image

6.4 Example 4

Image inpainting is the process of reconstructing missing regions in an image. This task is crucial in computer vision and serves as an essential functionality in numerous imaging and graphics applications; for more details, refer to [28].

The tensor total variation is one of the techniques employed for this purpose. In this example, we address the regularization tensor-least squares problem

$$\begin{aligned} \underset{{\mathcal {X}}}{\min }\lbrace \Vert {\mathcal {P}}_\textsf{E}({\mathcal {X}})-{\mathcal {B}}\Vert _{F} + \lambda \Vert \nabla {\mathcal {X}}\Vert _1 \rbrace \end{aligned}$$
(31)

where \({\mathcal {P}}_\textsf{E}\) is the tensor projection on \({\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}}\), such that for \({\mathcal {X}} \in {\mathbb {R}}^{I_{1}\times I_{2}\times I_{3}\times \cdots \times I_{N}}\) the entries of \({\mathcal {P}}_\textsf{E}({\mathcal {X}})\) are given as

$$\begin{aligned} ({\mathcal {P}}_\textsf{E}({\mathcal {X}}))_{{i_{1},i_{2},...,i_{N}}}=\left\{ \begin{aligned} {\mathcal {X}}_{{i_{1},i_{2},...,i_{N}}}&\hspace{1.2cm}{\text {if}}\hspace{0.2cm}(i_{1},i_{2},...,i_{N})\in \textsf{E}, \\ 0&\hspace{1.4cm} {\text {otherwise}},\\ \end{aligned} \right. \end{aligned}$$

with \(\textsf{E}=\lbrace (i_{1},i_{2},...,i_{N}):{\mathcal {X}}_{{i_{1},i_{2},...,i_{N}}}\) observed \(\rbrace \) (see [8]).Let \({\mathcal {X}}^{exact}\) be the original image, and the tensor \({\mathcal {B}}\) represents its text-added version. Utilizing the tensorial double proximal gradient algorithm (TDPG) proposed in [4], we iteratively solve the problem (31).

For the first experiment, we consider the image ’coloredChips.png’ from the MATLAB R2020a collection, with dimensions of (\(150 \times 190 \times 3\)). We corrupted it by adding text, as shown in Fig. 5.

Fig. 5
figure 5

The original ’coloredChips.png’ image (left) and its text-added one (right)

Full size image

Fig. 6 displays the restored images using TDPG, TG-MPE, and the proposed method (HOSVD-TMPE). It is evident that our proposed method successfully removed nearly all the added text, a result not achieved by the basic iteration TDPG or the TG-MPE method.

Fig. 6
figure 6

The recovered images by TDPG (left), TG-MPE (middle) and HOSVD-TMPE (right) in 500 iterations

Full size image

Table 2 presents the iteration number, relative error-norm, recovered image PSNR, and the required CPU time for TDPG (Basic Iterations), TG-MPE, and HOSVD-TMPE. We use \(\epsilon =5 \times 10^{-2}\) as a stopping criterion for computations. The results obtained confirm the superiority of our proposed method in terms of PSNR and relative error-norm, as well as in terms of CPU time.

Table 2 Comparison of the required iterations number, relative error, PSNR and CPU time for TDPG (Basic-Iterations), TG-MPE and HOSVD-TMPE for the ’coloredChips’ image
Full size table

Figure 7 displays the relative error-norm (on the left), the rate of acceleration (in the middle), and PSNR (on the right) versus the iteration index for the three methods: TDPG, TG-MPE, and HOSVD-TMPE. Compared to TDPG (Basic Iterations) and TG-MPE, the curves confirm that our proposed algorithm is more effective.

Fig. 7
figure 7

The relative error-norm, the acceleration rate and the PSNR curves for ’coloredChips’ image

Full size image

Now, let us consider another color image obtained from ’sherlock.jpg’ in the MATLAB R2020a collection. We corrupted it by adding a scribble, as illustrated in Fig. 8.

Fig. 8
figure 8

The original "sherlock" image (left) and its painted one (right)

Full size image

Figure 9 illustrates the restored images obtained using TDPG, TG-MPE, and the proposed algorithm (HOSVD-TMPE). It is evident that our proposed method and TG-MPE yield nearly identical results, with a slight advantage observed for HOSVD-TMPE. Compared to the basic iterative TDPG method, both HOSVD-TMPE and TG-MPE methods have effectively removed most of the superimposed scribble.

Fig. 9
figure 9

The recovered images by TDPG (left), TG-MPE (middle) and HOSVD-TMPE (right) in 520 iterations

Full size image

Table 3 presents various values, including the iteration number, relative error, recovered image PSNR, and required CPU time for TDPG (Basic Iterations), TG-MPE, and HOSVD-TMPE. For the size \(150 \times 160 \times 3\), we stopped computations when the relative error was less than \(\epsilon =8 \times 10^{-2}\), while for the size \((325 \times 300 \times 3)\), we set \(\epsilon =10^{-1}\). The obtained results confirm the advantage of our proposed method in terms of PSNR, relative error, as well as the required number of iterations and CPU time.

Table 3 Comparison of the required iteration number, relative error, PSNR and CPU time for TDPG (Basic-Iterations), TG-MPE and HOSVD-TMPE for different sizes of ’sherlok’ image
Full size table

The curves depicted in Fig. 10 illustrate the superior performance of our proposed method compared to TG-MPE. It is evident that HOSVD-TMPE excels in terms of PSNR, relative error-norm, and convergence rate, highlighting its effectiveness

Fig. 10
figure 10

The relative error (left), the acceleration rate (middle) and the PSNR (right) curves for ’sherlok’ image

Full size image

7 Conclusion

The acceleration of slowly convergent sequences is an interesting purpose of extrapolation methods. In this paper, we introduced a new tensor extrapolation method for tensor sequences, namely HOSVD-TMPE. We presented an efficient algorithm that is based on high-order singular value decomposition for implementing the proposed extrapolation method. The presented numerical tests show the performance and effectiveness of the algorithm. Additionally, we provide some applications in color image restoration and completion.