The hybird methods of projection-splitting for solving tensor split feasibility problem

1.   Introduction

The split feasibility problem (SFP) is formulated as finding a point $x$ with the following property

where $C$ and $Q$ are the nonempty closed convex sets. In this paper, we will focus on the discussion of the following so-called tensor split feasibility problem (TSFP)

where $C\subseteq \mathbb{R}^{n}$, $Q\subseteq \mathbb{R}^{n}$ are the nonempty closed convex sets, and $\mathcal{A} \in \mathbb{R}^{[m, n]}$ is a tensor with $m$th order and $n$-dimension. When $m = 2$, i.e., $\mathcal{A}$ is a matrix, (1.2) reduces to the split feasibility problem (SFP) (1.1) (see ^[1,2]). Furthermore, (1.2) can be regarded as the general case of multiple-sets split feasibility problem.

The SFP has always attracted the attention of some researchers. For instance, Censor et al. ^[3] presented an interesting approach for solving the multiple-sets split feasibility problem. However, it probably depends heavily on the step size, a fixed Lipschitz constant of gradient of objective function, which is hard to be estimated normally. Moreover, by adopting variable step sizes based on the known information from current iterate, Zhang and Han et al. ^[4] investigated a self-adaptive projection-type method for nonlinear multiple-sets split feasibility problem, which has a variety of specific applications in real world, e.g., image reconstruction, medical care (such as inverse problem of intensity-modulated radiation therapy (IMRT)) and signal processing ^[5,6]. To choose a best step-size for current direction, Zhao and Yang et al. ^[7] studied a simple projection method for solving the multiple-sets split feasibility problem, which is easy to implement and come true. Meanwhile, they also proposed several efficient acceleration schemes for solving the multiple-sets split feasibility problem ^[8].

All of the literatures mentioned above mainly focus on some explorations about the solution of equivalent optimization problem. This issue would be developed from another point of view, i.e., the perspective of splitting iteration for solving tensor equation. Certainly, first of all, the split feasibility problem (1.2) should be transformed into multi-linear systems with constraint by projection operator $P_Q(\cdot)$. The exact scheme is written as follows:

As is known that a critical issue in pure and applied mathematics is solving variety classes of systems. Especially for the data analysis need of the background of big data, some rapid and efficient computing techniques of multi-linear systems have received serious attention in the field of science and engineering. In fact, it is not easy to get the precise solution by utilizing some direct methods. As a result, different kinds of iterative strategies were widely established to solve this problem. These research works concentrated mostly upon fast solvers for the multi-linear systems. For instance, Ding and Wei ^[9,10] extended classical Jocobi, Gauss-Seidel, successive overrelaxation method and Newton methods. In view of the costly computations for the Newton method, Han ^[11] developed an homotopy method by means of an Euler-Newton prediction-correction strategy to solve multi-linear systems with nonsymmetric M-tensors. Tensor splitting method and its convergence results have been studied in detail by Liu and Li et al. ^[12]. Moreover, some valuable comparison results of splitting iteration for solving multi-linear systems were achieved in ^[13].

Motivated by ^[13], we extend an tensor alternating splitting iteration scheme for solving constraint multi-linear systems (1.3). Further, the accelerated overrelaxation method (AOR) and symmetric accelerated overrelaxation method (SAOR) are generalized for solving (1.3) in practical alternating splitting iteration application.

The outline of this paper is organized as follows. Some beneficial and basic notations are provided simply in Section 2. In Section 3, a tensor alternating splitting iteration scheme will be proposed for solving constraint tensor systems. In Section 4, the classical approaches, AOR and SAOR are further extended to solve the constraint multi-linear systems. Meanwhile, a few numerical results are carried out to demonstrate the efficiency of the presented iteration methods. Finally, a conclusion remark is drawn in Section 5.

2.   Preliminaries

In this section, some basic results and useful definitions are introduced which is beneficial for the discussions of the following parts.

First of all, let $A\in \mathbb{R}^{[2, n]}$ (i.e., matrix) and $\mathcal{B}\in \mathbb{R}^{[k, n]}$ ($k > 2$). The matrix-tensor product $\mathcal{C} = A\mathcal{B}\in \mathbb{R}^{[k, n]}$ is defined by

Hence, the formula above usually is expressed as

where $\mathcal{C}_{(1)}$ and $\mathcal{B}_{(1)}$ are the matrices generated from $\mathcal{C}$ and $\mathcal{B}$ flattened along first index. For more details, see ^[14,15].

Definition 2.1. ^[16] Let $\mathcal{A} = (a_{i_1i_2\cdots i_m})\in \mathbb{R}^{[m, n]}$ be an order $m$ dimension $n$ tensor. Then, the majorization matrix $M(\mathcal{A})$ of $\mathcal{A}$ is the $n\times n$ matrix with the entries

Definition 2.2. ^[17] Let $\mathcal{A} = (a_{i_1i_2\cdots i_m}) \in \mathbb{R}^{[m, n]}$. If $M(\mathcal{A})$ is a nonsingular matrix and $\mathcal{A} = M(\mathcal{A})\mathcal{I}_m$, $M(\mathcal{A})^{-1}$ is named as the order-$2$ left-inverse of tensor $\mathcal{A}$, and $\mathcal{A}$ is called left-nonsingular, where $\mathcal{I}_m$ is an identity tensor with all diagonal elements being 1.

Definition 2.3. ^[12] Let $\mathcal{A}, \mathcal{E}, \mathcal{F } \in \mathbb{R}^{[m, n]}$. If $\mathcal{E}$ is left-nonsingular, then $\mathcal{A} = \mathcal{E}-\mathcal{F}$ is named as a splitting of tensor $\mathcal{A}$. If $\mathcal{E}$ is left-nonsingular with $M(\mathcal{E})^{-1}\geq 0$ and $\mathcal{F}\geq 0$ $($here $\leq$ or $\geq$ denotes elementwise$)$, then the splitting of $\mathcal{A}$ is named as a regular splitting. If $\mathcal{E}$ is left-nonsingular with $M(\mathcal{E})^{-1}\mathcal{F}\geq 0$, then the splitting of $\mathcal{A}$ is named as a weak regular splitting. If spectral radius of $M(\mathcal{E})^{-1}\mathcal{F}$ is less than 1, i.e., $\rho(M(\mathcal{E})^{-1}\mathcal{F}) < 1$, then the splitting is convergence.

Definition 2.4. ^[18] Let $\mathcal{A}\in \mathbb{R}^{[m, n]}$. $\mathcal{A}$ is called a $\mathcal{Z}$-tensor if its off-diagonal entries are non-positve. $\mathcal{A}$ is called an $\mathcal{M}$-tensor if there exist a nonnegative tensor $\mathcal{B}$ and a positive real number $\eta\geq \rho(\mathcal{B})$ such that

Further, $\mathcal{A}$ is called a strong $\mathcal{M}$-tensor, if $\eta > \rho(\mathcal{B})$.

Definition 2.5. ^[19] Let $\mathcal{A} = (a_{i_1i_2\cdots i_m})\in \mathbb{R}^{[m, n]}$. A pair $(\lambda, \; x)\in \mathbb{C} \times (\mathbb{C}^n \backslash\{0\})$ is called an eigenvalue-eigenvector of tensor $\mathcal{A}$ if they satisfy the systems

where $x^{[m-1]} = (x_{1}^{m-1}, x_{2}^{m-1}, \cdots, x_{n}^{m-1})^T$. The $(\lambda, x)$ is named as $H$-eigenpair if both $\lambda$ and vector $x$ are real.

Definition 2.6. Let $\rho(\mathcal{A}) = \max\{|\lambda| |\lambda \in \sigma(\mathcal{A})\}$ be the spectral radius of $\mathcal{A}$, where $\sigma(\mathcal{A})$ is the set of all eigenvalues of $\mathcal{A}$.

Lemma 2.1. ^[13] If $\mathcal{A}$ is a $\mathcal{Z}$-tensor, then the follwing conditions are equivalent:

(a) $\mathcal{A}$ is a strong $\mathcal{M}$-tensor.

(b) There exist an inverse-positive $\mathcal{Z}$-matrix $B$ and a semi-positve $\mathcal{Z}$-tensor $\mathcal{C}$ with $\mathcal{A} = B\mathcal{C}$.

(c) $\mathcal{A}$ has a convergent (weak) regular splitting.

3.   Tensor alternating splitting iteration to solve TSPF

From the view of optimization, TSPF problem in (1.2) is equivalent to

where

Set

In detail, the Levenberg-Marquardt method for solving TSPF can be described as follows (see Algorithm 3.1).

Algorithm 3.1. Projection method to solve tensor split feasibility problem

${\bf{Step\; 1.}}$ Given nonempty closed convex sets $C$ and $Q$, a semi-symmetric tensor $\mathcal{A}$ ^[19], initial point vector $x_0$, set $\beta\in (0, 1),$ $\sigma\in (0, 1),$ precision $\varepsilon_1 > 0$, $\varepsilon_2 > 0$. Set $k:=1$.

${\bf{Step\; 2.}}$ Compute $F_k=F(x_k)$, $J_k=J(x_k)$, and $g_k=\nabla f(x_k)$ in (3.2)-(3.3). If $\|g_k\|_2 < \varepsilon_1$ stop; otherwise, go to Step $3$.

${\bf{Step\; 3.}}$ Let

Compute a direction $d_k$ by solving the following equation

${\bf{Step\; 4.}}$ Find the smallest nonnegative integer $m_k$ such that $\alpha_k=\beta^{m_k}$ satisfies

${\bf{Step\; 5.}}$

If $\|x_{k+1}-x_{k}\| < \varepsilon_2$ stop; otherwise, set $k:=k+1$, return to Step $2$.

However, in this section, we will restatement TSPF problem in (1.2) form the perspective of tensor split and expect to get better convergence results, which will be further reported in numerical test part.

Now, we describe briefly alternating direction iterative method for solving unconstrained part of multi-linear systems (1.3) $\mathcal{A}x^{m-1} = P_Q(\mathcal{A}x^{m-1})$.

By $\mathcal{A} = \mathcal{E}_1-\mathcal{F}_1$, clearly, the above multi-linear systems can be written as

i.e.,

Here it makes use of the property of order $2$ left-nonsingular of tensor $\mathcal{E}_{1}$. $\mathcal{I}_m$ is an identify tensor with appropriate order. The result can be concluded in Algorithm $3.2$.

Algorithm 3.2. Projection-splitting tensor iterative method

${\bf{Step\; 1.}}$ Input a strong $M$-tensor $\mathcal{A}$ with (weak) regular splitting $\mathcal{A}=\mathcal{E}_{1}-\mathcal{F}_{1}$. Given nonempty closed convex sets $C$ and $Q$, a precision $\varepsilon > 0$ and initial vector $x_0$. Set $k:=1$.

${\bf{Step\; 2.}}$ If $\|\mathcal{A} x_k^{m-1}-P_Q(\mathcal{A}x_{k}^{m-1})\|_2 < \varepsilon$ stop; otherwise, go to Step $3$.

${\bf{Step\; 3.}}$

${\bf{Step\; 4.}}$

${\bf{Step\; 5.}}$ Set $k:=k+1$, return to Step $2$.

Now, consider the tensor splitting $\mathcal{A} = \mathcal{E}_1-\mathcal{F}_1 = \mathcal{E}_2-\mathcal{F}_2$. Based on this, two-step tensor alternating splitting iteration method is introduced. Then, it generates the iterative scheme

Set $\mathcal{G}: = M(\mathcal{E}_{2})^{-1}\mathcal{F}_{2}$. According to $\mathcal{I}_m x^{m-1} = x^{[m-1]}$ where $\mathcal{I}_m$ is an identify tensor with appropriate order, we have

Hence,

The above analysis can be described concretely in Algorithm 3.3.

Now, let

In the following, we would like to show the spectral radius of iterative tensor $\rho\big(\mathcal{T}(\mathcal{E}_{1}, \mathcal{E}_{2})\big) < 1,$ i.e., the proof of convergence of Algorithm $3.3$.

Algorithm 3.3. Projection-splitting tensor alternating iterative method

${\bf{Step\; 1.}}$ Input a strong $M$-tensor $\mathcal{A}$ with (weak) regular splitting $\mathcal{A}=\mathcal{E}_{1}-\mathcal{F}_{1}$. Given nonempty closed convex sets $C$ and $Q$, a precision $\varepsilon > 0$ and initial vector $x_0$. Set $k:=1$.

${\bf{Step\; 2.}}$ If $\|\mathcal{A} x_k^{m-1}-P_Q(\mathcal{A}x_{k}^{m-1})\|_2 < \varepsilon$ stop; otherwise, go to Step $3$.

${\bf{Step\; 3.}}$

${\bf{Step\; 4.}}$

${\bf{Step\; 5.}}$ Set $k:=k+1$, return to Step $2$.

Lemma 3.1. ^[9] Let $\mathcal{A} = (a_{i_1i_2\cdots i_m})\in \mathbb{R}^{[m, n]}$, and $\mathcal{A} = \mathcal{E}_{1}-\mathcal{F}_{1} = \mathcal{E}_{2}-\mathcal{F}_{2}$ be a weak regular splitting and a regular splitting, respectively. If $\mathcal{F}_{2} < \mathcal{F}_{1}$, $\mathcal{F}_{2}\neq 0$, and $\rho((\mathcal{E}_{1})^{-1}\mathcal{F}_{1}) < 1$, then there exists a positive Perron vector $x\in \mathbb{R}^{n}$ such that

where $\rho_k = \rho(M(\mathcal{E}_{1})^{-1}\mathcal{F}_{1}+\frac{1}{k}\mathcal{S}),$ $k$ is a positive integer and $\mathcal{S}\in \mathbb{R}^{[m, n]}$ is a positive tensor.

Proof. Let $\mathcal{S}$ be in $\mathbb{R}^{[m, n]}$ whose entries are all equal to $1$. Using the strong Perron-Frobenius theorem (see ^[20,21]), for any given $k > N$, $M(\mathcal{E}_{1})^{-1}\mathcal{F}_{1}+\frac{1}{k}\mathcal{S}$ has a positive Perron vector $x$ such that

where $\rho_k = \rho(M(\mathcal{E}_{1})^{-1}\mathcal{F}_{1}+\frac{1}{k}\mathcal{S}).$

Hence, it give rises to

By $\mathcal{A} = \mathcal{E}_{1}-\mathcal{F}_{1} = \mathcal{E}_{2}-\mathcal{F}_{2}$, one gets $M(\mathcal{A}) = M(\mathcal{E}_{1})-M(\mathcal{F}_{1}) = M(\mathcal{E}_{2})-M(\mathcal{F}_{2}).$

So it generates

Further, it follows from (3.12) that

here, notice that the condition $\mathcal{F}_{1}\geq\mathcal{F}_{2}$. So $M(\mathcal{F}_{1})\geq M(\mathcal{F}_{2})$ and $\mathcal{F}_{1}-M(\mathcal{F}_{1})\mathcal{I}_m\geq \mathcal{F}_{2}-M(\mathcal{F}_{2})\mathcal{I}_m$.

By some simple computations, we obtain

Note that $M(\mathcal{E}_{2})^{-1}\geq0$ and $\mathcal{F}_{2}\geq0$ due to the regular splitting of $\mathcal{A} = \mathcal{E}_{2}-\mathcal{F}_{2}$. According to (3.15), it yields

Theorem 3.1. Let $\mathcal{A} = (a_{i_1i_2\cdots i_m})\in \mathbb{R}^{[m, n]}$, and $\mathcal{A} = \mathcal{E}_{1}-\mathcal{F}_{1} = \mathcal{E}_{2}-\mathcal{F}_{2}$ be a weak regular splitting and a regular splitting, respectively. If $\mathcal{F}_{2} < \mathcal{F}_{1}$, $\mathcal{F}_{2}\neq 0$ and $\rho\big((\mathcal{E}_{1})^{-1}\mathcal{F}_{1}\big) < 1$. $\mathcal{G}: = M(\mathcal{E}_{2})^{-1}\mathcal{F}_{2}$ is order $2$ left-nonsingular, i.e., $\mathcal{G} = M(\mathcal{G})\mathcal{I}_m$, then $\rho\big(\mathcal{T}(\mathcal{E}_{1}, \; \mathcal{E}_{2})\big) < 1,$ where $\mathcal{T}(\mathcal{E}_{1}, \mathcal{E}_{2})$ is defined by $(3.8)$.

Proof. First of all, similar to the previous discussion, using the strong Perron-Frobenius theorem, for any given $k > N$, $M(\mathcal{E}_{1})^{-1}\mathcal{F}_{1}+\frac{1}{k}\mathcal{S}$ has a positive Perron vector $x$ such that

where $\rho_k = \rho(M(\mathcal{E}_{1})^{-1}\mathcal{F}_{1}+\frac{1}{k}\mathcal{S}).$ This implies

where the inequality comes from the Lemma 3.1. As we know that $\rho((\mathcal{E}_{1})^{-1}\mathcal{F}_{1}) < 1$, hence, when $k\rightarrow \infty$, $(\rho_k)^2 < 1$. This completes the proof.

4.   Numerical experiments

In this section, some numerical examples are discussed to validate the performance of effectiveness of the proposed projection-splitting tensor AOR (denoted as 'P-STAOR') and tensor symmetric (alternating) splitting AOR (denoted as 'P-STSAOR') based two-step splitting method for solving the multi-linear systems (see Algorithm $3.2$ and Algorithm $3.3$). We compare the convergence of these methods with projection tensor Levenberg-Marquardt (denoted as 'P-STLM', see Algorithm 3.1) by the iteration step (denoted as 'IT'), elapsed CPU time in seconds (denoted as 'CPU'), and residual error (denoted as 'RES'). The running is terminated when the current iteration satisfies $\mathrm{RES} = \|\mathcal{A}x^{m-1}-P_Q(\mathcal{A}x^{m-1})\|_2 < 10^{-10}$ or if the number of iteration exceeds the prescribed iteration steps $k_{max} = 50$. All the numerical experiments have been carried out by MATLAB R2011b 7.1.3 on a PC equipped with an Intel(R) Core(TM) i7-2670QM, CPU running at 2.20GHZ with 8 GB of RAM in Windows 10 operating system.

Now, consider the tensor splitting of $(1.2)$

The layout of splitting description is shown in Table 1, where $\mathcal{D} = D\mathcal{I}_m$, $\mathcal{L} = L\mathcal{I}_m$, $\mathcal{U} = U\mathcal{I}_m$, and $\mathcal{D}$, $-\mathcal{L}$, $-\mathcal{U}$ are the diagonal part, strictly lower and strictly upper triangle part of majorization matrix $M(\mathcal{A})$.

Example 4.1. First consider the tensor split feasibility problem (TSFP) (1.2) with a strong $\mathcal{M}$-tensor $\mathcal{A} = 30*\mathcal{I}_m-0.01*\mathcal{B}$, where $B(i, j, k) = 0.6*i+0.1*(k+j)$, $\mathcal{I}_m$ is an identity tensor with order $m$ dimension $n$. And the nonempty closed convex sets

Three different examples are given for different tensors $\mathcal{A}$, $\mathcal{B}$ with various sizes. Parameters $r$ and $\omega$ for P-STAOR and P-STSAOR, $\beta$ for P-STLM are experiential selected according to particular example, see those tables in this section for details. In all examples, parameter $\mu$ for P-STLM (in Algorithm 3.1) is selected fixedly with $0.25$.

The numerical results have been shown in Tables 2–6 and Figures 1–5. From the numerical results, we can see that P-STAOR and P-STSAOR are efficient methods, and both of them are comparable with P-STLM in all sides. Totally, two approaches proposed in this paper, i.e., P-STAOR and P-STSAOR, are nearly the same merits. However, in some cases, e.g., for the numbers of iteration and elapsed CPU time, P-STSAOR seems to be a more fascinating method than P-STAOR (see Table 4). The reasons are possible the flexible selection of parameters and the superiority of alternating direction iterative. Further from the residual trend chart with the changing numbers of iteration in Figures 1–5, one can demonstrably find the desired performance of the proposed methods.

From three examples, whatever the parameters $r$ and $\omega$ in two methods P-STAOR and P-STSAOR are, the results of convergence are satisfactory as always. However, P-STLM dependents heavily on parameter $\beta$. By the Case $b$, i.e., when $\beta = 0.2$ in Table 6, P-STLM cann't guarantee the global convergence any more. At the same time, we notice that the residual of P-STLM disappears from the restricted area in Figure 5. Nevertheless, the residuals of P-STAOR and P-STSAOR still decline rapidly and converge well.

Example 4.2. Consider the tensor split feasibility problem (TSFP) (1.2) with a strong $\mathcal{M}$-tensor $\mathcal{A} = 50*\mathcal{I}_m-0.01*\mathcal{B}$, where $B(i, j, k, l, p) = 0.85*i+0.3*(k+j+l+p)$, $\mathcal{I}_m$ is an identity tensor with order $m$ dimension $n$. And the nonempty closed convex sets

Example 4.3. Finally, consider the tensor split feasibility problem (TSFP) (1.2) with a strong $\mathcal{M}$-tensor $\mathcal{A} = 300*\mathcal{I}_m-0.5*\mathcal{B}$, where $B = rand(n, n, n, n, n)$, a random generated tensor with order $m$ dimension $n$, $\mathcal{I}_m$ is an identity tensor with order $m$ dimension $n$. And the nonempty closed convex sets

We test this example with different $n$.

In this example, all the numerical results are depicted in Tables 4–6 and Figures 3–5. From the elapsed CPU and numbers of iteration, P-STSAOR performs always well than all of other approaches. Although the optimum parameters are perhaps hard to determine, we just choose them tentatively in some reality application according to experiment essential effects. Also, we try to introduce the preconditioner to precondition the constraint tensor system (1.3). However, it is difficult to choose a suitable preconditioner for this problem. Hence, the investigations of optimum parameters and befitting preconditioners for P-STSAOR and P-STAOR will be further accomplished in our future work. In a word, P-STSAOR and P-STAOR can be regarded as the promising and efficient approaches for solving the multi-linear split feasibility problem.

5.   Conclusions

In this paper, by making use of the idea of tensor alternating splitting, two efficient methods are presented to solve the multi-linear split feasibility problem. Concretely, by extending accelerated overrelaxation and symmetric accelerated overrelaxation, tensor accelerated overrelaxation and tensor symmetric accelerated overrelaxation splitting iteration strategies are introduced for solving the multi-linear split feasibility problem, which are distinctly different from some techniques on the perspective of optimization. The convergence result is presented in detail by analysis of tensor spectral radius. Precisely, the proposed P-STSAOR and P-STAOR have been verified to be quite meaningful approaches. Many numerical test results illustrate they meet the expectation as the current efficient methods. Finally, some advices about future research work are also provided.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors are very much indebted to the anonymous referees for their constructive and valuable comments and suggestions which greatly improved the original manuscript of this paper. This work was supported by Fujian Natural Science Foundation (Grant No.2022J01378).

Conflict of interest

The authors declare that they have no conflict of interest.