Convergence algorithms of fuzzy tensors

1 Introduction

Tensor theory is a hot topic in mathematics since 2005 [1, 2]. The notion of tensor in mathematics fields is generally a multidimensional array. The elements in tensors are referred by using multiple indices. Specifically, a vector is a 1-order tensor, and a matrix is a 2-order tensor, then 3-order and greater are called higher order tensor. In SIAM Review 2009 [3] which leads to the tensor theory is more widely penetrated into all fields. Ni and Qi [4] proposed a quadratically convergent algorithm for finding the largest eigenvalue of the semi-symmetric tensor, Zhang and Qi [5] established linear convergence of an algorithm for computing the largest eigenvalue of a nonnegative tensor.

The pioneering work on fuzzy sets is dated back to 1965 [6]. The theory of fuzzy matrix plays an important role in various fields. The element of a fuzzy matrix is arbitrary value in the closed interval [0, 1] with fuzzy logic operations. The theoretical background of fuzzy matrices is derived from nonnegative matrix theory [7]. Application context of fuzzy matrices is primarily centered in fuzzy control fields. It is used to describe the stability state of the fuzzy system with the convergence of the power series of fuzzy matrices. The convergence of powers sequence of fuzzy matrix was put forward by Thomason in 1977 [8], and the existence of periodicity and index was proved. Since then, many scholars have gained abundant research achievements. In 1992, Li [9] pointed out that periodicity of powers of fuzzy matrix. Liu and Ji [10] discussed the periodicity of square fuzzy matrices. Guu, Lur and Pang [11] studied the convergence of infinite of products of a finite number of fuzzy matrices.

With the increasingly wide application of tensor and fuzzy matrix, it is necessary to extend theory from fuzzy matrix to fuzzy tensor. In this paper, we discuss the convergence of fuzzy tensor under max-min operations. In the second section, we shall describe the definitions of directed path and fuzzy directed path systems, which are used throughout the paper. The theory of convergence of fuzzy tensor will be built in terms of cutting matrices. Two algorithms for judging the convergence of a fuzzy tensor are developed. Subsequently, numerical results are reported in Section 3 and in Section 4, and conclusions will be given in Section 5.

2 Directed path and fuzzy directed path system

In this section, we first recall some basic definitions and notations in [1, 12–15]. As was indicated in [1], a real order m dimension n tensor A = ( a i 1 ⋯ i m ) consists of n ^m entries: a i 1 ⋯ i m ∈ R , where 1 ≤ i _j  ≤ n for j = 1, ⋯ , m.

For any n × n fuzzy matrices A = (a _ij ) and B = (b _ij ), the product of A and B is defined as follows: A × B = C = ( c ij ) = ⋁ k = 1 n ( a ik ∧ b kj ) , where a _ij  ∧ b _ij  = min {a _ij , b _ij } , a _ij  ∨ b _ij   =   max {a _ij , b _ij } [6, 12].

We say A ≤ B if and only if a _ij  ≤ b _ij for all i, j ∈ {1, 2, ⋯ , n} (See [6, 12–14]).

For any fuzzy matrix A, let Φ _A [13] denote the set of all nonzero elements of the fuzzy matrix A, and for any λ ∈ Φ _A . The λ level cut matrix A _λ [13] is defined by

A λ = ( a λ ) ij = { 1 , if a ij ≥ λ , 0 , a ij < λ .(1)

Clearly, the λ level cut matrix A _λ is Boolean matrix. Through these cut matrices, we have decomposition theorem [13] of a fuzzy matrix: A = ⋁ λ ∈ Φ A ( λ ∧ A λ ) .

From the definition of a tensor and a fuzzy matrix, we can give the definition of fuzzy tensor.

Definition 1. (See [15]) An order m dimension n fuzzy tensor A = ( a i 1 ⋯ i m ) consists of n ^m entries: 0 ≤ a i 1 ⋯ i m ≤ 1 , where 1 ≤ i _j  ≤ n for j = 1, ⋯ , m.

In this paper, we use the slice method to investigate fuzzy tensor, and study on the convergence of fuzzy tensor by using the max-min fuzzy operator. The advantage is that it does not add new elements. We refer to [11] for explore fuzzy tensor, the paper’s idea can be extended to investigate the convergence of fuzzy tensor.

For this purpose, consider a finite number of fuzzy matrices A⁽¹⁾, A⁽²⁾, ⋯ , A⁽ⁿ⁾ with each A⁽ⁱ⁾ ∈ F^n×n, where F^n×n denotes the set of all n × n fuzzy matrices. We let P = { A ( 1 ) , A ( 2 ) , ⋯ , A ( n ) } , for any λ ∈ Φ _P , where Φ P = ⋃ i = 1 n Φ A ( i ) , and accordingly denotes P λ = { A λ ( 1 ) , A λ ( 2 ) , ⋯ , A λ ( n ) } .

Then all products of finite number of fuzzy matrices can be written by P ( k ) = A ( 1 ) × A ( 2 ) × ⋯ × A ( k ) , where A⁽ⁱ⁾ ∈ F^n×n, i = 1, 2, ⋯ , k.

Definition 2. Let P = {A⁽¹⁾,  A⁽²⁾, ⋯ , A⁽ⁿ⁾} , A⁽ⁱ⁾ ∈ F^n×n, and let P be termwise multiplied by the superscript indices of fuzzy matrices from small to large, if its shape is as follows: P ( 1 ) = A ( 1 ) ∈ F n × n , P ( 2 ) = A ( 1 ) × A ( 2 ) , P ( 3 ) = A ( 1 ) × A ( 2 ) × A ( 3 ) , ⋯ ⋯ P ( k ) = A ( 1 ) × A ( 2 ) × ⋯ × A ( k ) .

We can get a sequence {P (k)} , 1 ≤ k ≤ n. Then {P (k)} is a directed path.

Remark 1. By n × n fuzzy matrices, the directed path {P (k)} contains k elements. And P (k + 1) = P (k) × A^(k+1), A^(k+1) ∈ F^(n×n). A directed path is determined from an P = {A⁽¹⁾,  A⁽²⁾, ⋯ , A⁽ⁿ⁾}.

From the theory of Boolean matrices [16, 17], it is easy to see:

Lemma 1. Consider P = {A⁽¹⁾, A⁽²⁾, ⋯ , A⁽ⁿ⁾} , A⁽ⁱ⁾ ∈ F^n×n. For λ ∈ Φ _P , {P _λ  (k)} is either convergence or oscillation.

From above, we know that the following lemma are useful mechanism to construct the directed path to convergence.

Lemma 2. Let P = {A⁽¹⁾, A⁽²⁾, ⋯ , A⁽ⁿ⁾} ,  A⁽ⁱ⁾ ∈ F^n×n. Then for all λ ∈ Φ _P ,

If {P _λ  (k)} is convergent, then {P (k)} is weakly convergent;

Proof. (i) Assume that {P (k)} is oscillating, there exist λ₁ ≠ λ₂ such that {P _{λ 1}  (k)} and {P _{λ 2}  (k)} convergent to P _{λ 1} and P _{λ 2} , respectively. Here P _{λ 1}  ≠ P _{λ 2} .

Alternatively, for {P _{λ 1}  (k)} and {P _{λ 2}  (k)}, there may be one oscillation or two oscillations. By the above analysis and Lemma 1, we know that {P _λ  (k)} is oscillating.

Hence, the result (i) is true.

(ii) Suppose that {P _λ  (k)} is strongly convergent to zero, that is, {P _λ  (k)} convergent to the same zero matrix. Hence {P (k)} is strongly convergent. The proof is completed. □

Theorem 3. Let P = {A⁽¹⁾, A⁽²⁾, ⋯ , A⁽ⁿ⁾} , A⁽ⁱ⁾ ∈ F^n×n. If the directed path {P (k)} is strongly convergent, then there exists 1 ≤ k₀ ≤ n - 1 such that P (k₀) = P (k₀ + r), where 1 ≤ r ≤ n - 1.

Proof. Since {P (k)} is strongly convergent, then {P _λ  (k)} is convergent to the same Boolean matrix, for λ ∈ Φ _P . There exists a positive k _λ such that P _λ  (k _λ ) = P _λ  (k _λ  + r), 1 ≤ k _λ  ≤ n - 1. Because the cardinal number of λ ∈ Φ _P is finite, now let k 0 = max λ ∈ Φ P k λ , and here 1 ≤ k₀ ≤ n - 1, then P _λ  (k₀) = P _λ  (k₀ + r), 1 ≤ r ≤ n - 1. By Definition 2 and the decomposition theorem of fuzzy matrix, we have P (k₀) = ⋁ _{λ∈Φ P} P _λ  (k₀) = ⋁ _{λ∈Φ P} P _λ  (k₀ + r) = P (k₀ + r). □

Definition 3. Let A = ( a i 1 ⋯ i m ) be a fuzzy tensor of order m dimension n. Multiple third-order fuzzy tensors clustering of A are constructed by fixing all but three indices. We shall call ( A i j i k i h , P ) the fuzzy directed path system, where i _j , i _k , i _h are arbitrarily taken from i₁, ⋯ , i _m , and P has the following three forms P^{(i _j )}, P^{(i _k )}, P^{(i _h )}.

From the definition of fuzzy directed path system, we learn that the effects of clustering the third-order fuzzy tensors by their spatial properties rely on accessing just a subset of the index during query time. Moreover, using a small set of polymorphic third-order fuzzy tensors, we can write out full directed paths of more than 3-order fuzzy tensor.

Notice that C m 3 n m - 3 fuzzy directed path systems and 3 C m 3 n m - 3 directed paths are generated by an m order n dimension fuzzy tensor.

Definition 4. The fuzzy directed path systems ( A i j i k i h , P ) is weakly convergent if directed paths {P⁽ⁱ⁾ (k)} (i = i _j , i _k , i _h ) are convergent. If we assume further that directed paths strong convergence to the same fuzzy matrix, we say that the fuzzy directed path systems is strong convergence.

By Definition 4 and Lemma 2, we obtain easily the following results.

Theorem 4. The fuzzy directed path systems is weakly convergent if and only if the corresponding Boolean directed path systems is weakly convergent.

From Definition 4, we know that the astringency of fuzzy directed path systems is determined by the convergence of all of their directed paths. Moreover, we define the convergence of fuzzy tensor.

Definition 5. If all fuzzy directed path systems ( A i j i k i h , P ) are weakly (strongly) convergent, then we say fuzzy tensor A is weakly (strongly) convergent.

In order to verify whether the directed path of convergence, we need to address through the associated Boolean directed path. This idea is very classical in fuzzy mathematics and makes the process relatively explicit. However, this needs miscellaneous computations when the volume of nonzero elements is large. Thus in the rest of this paper, we shall establish two algorithms to show the convergence of fuzzy tensor.

In this section, from the literature [11], we refer to Definition 4.1 in [11], and give the following definition.

Definition 6. Let P = {A⁽¹⁾, A⁽²⁾, ⋯ , A⁽ⁿ⁾} , A⁽ⁱ⁾ ∈ F^n×n. We say that P is k-th order increasing (decreasing), if the following inequality holds: P ( k ) ≤ P ( k + 1 ) ( P ( k ) ≥ P ( k + 1 ) ) , where 1 ≤ k ≤ n - 1.

Remark 2. When k = 1 and P = A⁽¹⁾, this definition is degenerated to monotonically increasing (transferring) for fuzzy matrix.

Based on Definition 6, we have the following result.

Theorem 5. Let a fuzzy directed path system ( A i j i k i h , P ) with directed path {P⁽ⁱ⁾ (k)}, where i = i _j , i _k , i _h ,

If each directed path is k-th order increasing (decreasing), then the fuzzy directed path system ( A i j i k i h , P ) is weakly convergent;

Proof. (i) Suppose that P^{(i _j )} is k-th order increasing, then P ( i j ) ( k ) = A ( 1 ) × A ( 2 ) × ⋯ × A ( k ) ≤ P ( i j ) ( k ) × A ( k + 1 ) = P ( i j ) ( k + 1 ) .

The sequence {P^{(i _j )} (k)} is monotone, and has an upper bound, so it is convergent.

Similarly, {P^{(i _k )} (k)} and {P^{(i _h )} (k)} are convergent.

Hence, the fuzzy directed path system ( A i j i k i h , P ) is weakly convergent.

(ii) This proof is similar to (i). □

Next, by the above definition and theorem, we provide an iterative algorithm for identifying the convergence of fuzzy tensor. We call the method is order reduction algorithm, denoted as ORCA.

ORCA (Order Reduction Convergent Algorithm of Fuzzy Tensor)

Input: An order m dimension n fuzzy tensor A = ( a i 1 ⋯ i m ) .

Output: By Definition 5, out put A is strongly convergent or A is weakly convergent.

Step 1. Choose i _j , i _k , i _h  ∈ {i₁, ⋯ , i _m }, and let A i jitsc i kitsc i hitsc = ( a i jitsc i kitsc i hitsc ) .

Step 2. For i _h do, then get P ( i h ) = { A ( 1 ) , A ( 2 ) , ⋯ , A ( n ) } , A ( i ) ∈ F n × n .

Step 3. Using Definition 2, compute P^{(i _h )} (1) , P^{(i _h )} (2) , ⋯, P^{(i _h )} (k) , P^{(i _h )} (k + 1).

Step 4. If there exists k₀ such that P^{(i _h )} (k₀) ≤ P^{(i _h )} (k₀ + 1) or (P^{(i _h )} (k₀) ≥ P^{(i _h )} (k₀ + 1)), then replace i _h by i _k , and go to Step 3. Otherwise, stop.

Step 5. If there exists k₁ such that P^{(i _k )} (k₁) ≤ P^{(i _k )} (k₁ + 1) or (P^{(i _k )} (k₁) ≥ P^{(i _k )} (k₁ + 1)), then replace i _k by i _j , and go to Step 3. Otherwise, stop.

Step 6. If there exists k₂ such that P^{(i _j )} (k₂) ≤ P^{(i _j )} (k₂ + 1) or (P^{(i _j )} (k₂) ≥ P^{(i _j )} (k₂ + 1)), and repeat step 1 to Step 6 until C m 3 n m - 3 times. Otherwise, stop.

Step 7. Compare all of values k₀, k₁, k₂. If all values are equal, then identifying ( A i j i k i h , P ) is strongly convergent or ( A i j i k i h , P ) is weakly convergent.

To demonstrate that ORCA works for fuzzy tensor, we test the following example whose codes are written in R language.

Example 1. Let A be a fifth order three dimensional fuzzy tensor defined in Table 1.

By ORCA, we know that each directed path is two order decreasing in Example 1, so A is weakly convergent.

This algorithm greatly reduces the order of fuzzy tensor. However, when the fuzzy tensor dimension is large, ORCA needs a huge amount of computational work. Now, we do not rely on the amount of multiplicational calculation, but only use the elements in the fuzzy tensor to determine the convergence.

In this section, we design an algorithm of element method. Similar to the way in the literature (see Definition 4.5 in [11]), we have the following definition.

Definition 7. For P = {A⁽¹⁾, A⁽²⁾, ⋯ , A⁽ⁿ⁾} , A⁽ⁱ⁾ ∈ F^n×n, consider the element at the same location of fuzzy matrices A⁽¹⁾, A⁽²⁾, ⋯ , A⁽ⁿ⁾, which in max and min operations forms two fuzzy matrices A^(max) ∈ F^n×n and A^(min) ∈ F^n×n, respectively.

If A ij ( max ) ≤ A ii ( min ) , here i ≠ j, then P is row dominated;

We next give a criterion for the weak convergence of fuzzy tensor from Definition 7.

Theorem 6. Let P = {A⁽¹⁾, A⁽²⁾, ⋯ , A⁽ⁿ⁾} , A⁽ⁱ⁾ ∈ F^n×n. If P is the column (row) dominated, then directed path {P (k)} is weakly convergent.

Proof. Assume that P is column dominated. For P (k + 1) , i ≠ j, we have P ( k + 1 ) ij = ( A ( 1 ) × A ( 2 ) × ⋯ × A ( k + 1 ) ) ij = ⋁ l = 1 n ( A ( 1 ) × A ( 2 ) × ⋯ × A ( k ) ) il × A lj ( k + 1 ) ≥ ( A ( 1 ) × A ( 2 ) × ⋯ × A ( k ) ) ij × A jj ( k + 1 ) = ( A il 1 ( 1 ) × A l 1 l 2 ( 2 ) × ⋯ × A l k - 1 j ( k ) ) × A jj ( k + 1 ) for some l₁, l₂, ⋯ , l_k-1.

Because A ij ( max ) ≤ A jj ( min ) , then A jj ( k + 1 ) ≥ A ij ( 1 ) .

Thus ( A il 1 ( 1 ) × A l 1 l 2 ( 2 ) × ⋯ × A l k - 1 j ( k ) ) × A jj ( k + 1 ) ≥ ( A il 1 ( 1 ) × A l 1 l 2 ( 2 ) × ⋯ × A l k - 1 j ( k ) ) , that is P (k + 1)  _ij  ≥ P (k)  _ij .

Hence, {P (k)  _ij } is weakly convergent.

For i = j, P ( k + 1 ) jj = A jl 1 ( 1 ) × A l 1 l 2 ( 2 ) × ⋯ × A l k - 1 l k ( k ) × A l k j ( k + 1 ) for some l₁, l₂, ⋯ , l _k .

Let l _k  = j, P ( k + 1 ) jj = ( A jl 1 ( 1 ) × A l 1 l 2 ( 2 ) × ⋯ × A l k - 1 j ( k ) ) × A jj ( k + 1 ) ≤ P ( k ) jj × A jj ( k + 1 ) ≤ P ( k ) jj

If l _k  ≠ j, by A ij ( max ) ≤ A jj ( min ) , then we have A l k j ( k + 1 ) ≤ A jj ( t ) , here t = 1, 2, ⋯ , k + 1, and P ( k + 1 ) jj ≤ A jj ( 1 ) × ⋯ × A jj ( k ) × A l k j ( k + 1 ) ≤ P ( k ) jj .

Therefore, {P (k)  _jj } is weakly convergent.

If P is the row dominated, the proof similar to the above. The proof is completed. □

By Definition 7 and Theorem 6, we naturally get the following result.

Corollary 1. Let P = {A⁽¹⁾, A⁽²⁾, ⋯ , A⁽ⁿ⁾} , A⁽ⁱ⁾ ∈ F^n×n. For all of fuzzy matrices A⁽¹⁾, A⁽²⁾, ⋯ , A⁽ⁿ⁾ on the same location elements, which in min operations obtains a fuzzy matrix, denoted by A^(min) ∈ F^n×n. If A ii ( min ) = 1 for i = 1, 2, ⋯ , n, then the directed path {P (k)} is weakly convergent.

From the proof of Theorem 6, we have the following laconic corollary to judge weakly convergent of the directed path.

Corollary 2. Let P = {A⁽¹⁾, A⁽²⁾, ⋯ , A⁽ⁿ⁾} , A⁽ⁱ⁾ ∈ F^n×n. If the off-diagonal elements are no larger than the diagonal elements for all of fuzzy matrices of P, then the directed path {P (k)} is weakly convergent.

Now, we proffer an element method for the convergence of fuzzy tensor from Definition 7, Theorem 6, Corollary 1, Definitions 4 and 5.

EMWCA (Element Method for Weakly Convergent Algorithm of Fuzzy Tensor)

Input: An order m dimension n fuzzy tensor A = ( a i 1 ⋯ i m ) .

Output: By Definition 5, if all directed paths are weakly convergent, output A is weakly convergent.

Step 1. Choose i _j , i _k , i _h  ∈ {i₁, ⋯ , i _m }, and let A i jitsc i kitsc i hitsc = ( a i jitsc i kitsc i hitsc ) .

Step 2. For i _h do, then get P ( i h ) = { A ( 1 ) , A ( 2 ) , ⋯ , A ( n ) } , A ( i ) ∈ F n × n .

Step 3. By Definition 7, compute A^(max) and A^(min).

Step 4. If A^(min) = 1, then go to Step 6. Otherwise, go to Step 5.

Step 5. Compare A ij ( max ) , A ii ( min ) and A jj ( min ) , i ≠ j.

If A ij ( max ) ≤ A ii ( min ) , or A ij ( max ) ≤ A jj ( min ) , then go to Step 6. Otherwise, stop.

Step 6. Replace i _h by i _k , go to Step 2.

Step 7. If A^(min) = 1, then go to Step 9. Otherwise, go to Step 8.

Step 8. Compare A ij ( max ) , A ii ( min ) and A jj ( min ) , here i ≠ j. If A ij ( max ) ≤ A ii ( min ) , or A ij ( max ) ≤ A jj ( min ) , then go to the next step. Otherwise, stop.

Step 9. Replace i _k by i _j , go to Step 2.

Step 10. If A^(min) = 1, then go to Step 12. Otherwise, go to Step 11.

Step 11. Compare A ij ( max ) , A ii ( min ) and A jj ( min ) , here i ≠ j. If A ij ( max ) ≤ A ii ( min ) , or A ij ( max ) ≤ A jj ( min ) , then repeat step 1 to step 11 until C m 3 n m - 3 times. Otherwise, stop.

Step 12. Output A is weakly convergent.

To show that the EMWCA works for fuzzy tensors, we test the following example.

Example 2. Let A be a third order six dimensional fuzzy tensor A = [ A ( : , : , 1 ) , A ( : , : , 2 ) , A ( : , : , 3 ) ] defined by Table 2. By Definition 7, we obtain A^(max) and A^(min) as in Table 2. It follows from Theorem 6, that all of directed paths are weakly convergent. By Definition 4 and 5, we can get that A is weakly convergent.

In this paper, we introduced the fuzzy tensor, which is a new extended class of tensor and extension of fuzzy matrix. We investigated the convergence of the directed path and the fuzzy directed path system to address the convergence of fuzzy tensor. In addition, we presented two algorithms for judging the convergence of fuzzy tensor. Both algorithms are considered according to the order and the dimension of fuzzy tensor, respectively. Our numerical results demonstrate that the two methods are promising and worth further exploring. Certainly, there are many other issues deserving to be further researched in the theory of fuzzy tensor, for example, how to find the speed of convergence of fuzzy tensor, and how to analyze the period of convergence of fuzzy tensor, and so on. We will continue to study these problems.