Printer Friendly

The perturbation bound for the spectral radius of a nonnegative tensor.

1. Introduction

Let R be the real field. We consider an mth order n-dimensional tensor A consisting of [n.sup.m] entries in R:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

A is called nonnegative (or, resp., positive) if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (or, resp., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In the following discussion, for a given vector y = [([y.sub.1], [y.sub.2], ..., [y.sub.n]).sup.T] [member of] [R.sup.n], we define a tensor-vector multiplication A[y.sup.m-1] to be n-dimensional column vector with its [i.sub.1]th entries given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

Also we let P = {([y.sub.1], [y.sub.2], ..., [y.sub.n]) | [y.sub.i] [greater than or equal to] 0} be the positive cone, and we let the interior of P be denoted as int(P) = {([y.sub.1], [y.sub.2], ..., [y.sub.n]) | [y.sub.i] > 0}. When y [member of] P (or y [member of] int(P)), y is a nonnegative (or a positive) vector. We denote the ith component of y by [(y).sub.i] or [y.sub.i], and we denote the ([i.sub.1], [i.sub.2], ..., [i.sub.m])th entry of A by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In recent studies of numerical multilinear algebra, eigenvalue problems for tensors have brought special attention. There are many related applications in information retrieval and data mining; see, for instance, [1, 2].

Definition 1. Let A be an mth-order n-dimensional tensor and let C be the set of all complex numbers. Assume that A[x.sup.m-1] is not identical to zero. We say ([lambda], x) [member of] C x ([C.sup.n] {0}) is an H-eigenpair of A if

A[x.sup.m-1] = [lambda][x.sup.[m-1]]. (3)

Here, [x.sup.[[alpha]]] := [([x.sup.[alpha].sub.1], [x.sup.[alpha].sub.2], ..., [x.sup.[alpha].sub.n]).sup.T]. The spectral radius [rho](A) of A is defined by the largest eigenvalue of A in magnitude.

This definition was introduced by Qi [3] when m is even and A is symmetric. Independently, Lim [4] gave such a definition but restricted x to be a real vector and [lambda] to be a real number. For the largest H-eigenvalue of a nonnegative tensor, the Perron-Frobenius theorem was proved by Chang et al. [5], Friedland et al. [6], and Lim [4]. Y. Yang and Q. Yang [7] generalized the weak Perron-Frobenius theorem to general nonnegative tensors. In [4], the concept of irreducibility in nonnegative matrices has been extended to nonnegative tensors.

Definition 2. An mth-order n-dimensional tensor A is called reducible if there exists a nonempty proper index subset J [subset] {1,2,..., n} such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

If A is not reducible, then we call A irreducible.

Theorem 3. Suppose A is an mth-order n-dimensional nonnegative tensor.

(i) Then there exist [[lambda].sub.0] [greater than or equal to] 0 and x [member of] P such that

A[x.sup.m-1] = [[lambda].sub.0] x [m-1]. (5)

(ii) If A is irreducible, then [[lambda].sub.0] > 0 and x [member of] int(P). Moreover, if [lambda] is an eigenvalue with a nonnegative eigenvector, then [lambda] = [[lambda].sub.0]. If [lambda] is an eigenvalue of A, then [absolute value of ([lambda])] [less than or equal to] [[lambda].sub.0].

We call x a Perron vector of a nonnegative tensor corresponding to its largest nonnegative eigenvalue.

Some algorithms for computing the largest eigenvalue of an irreducible tensor were proposed; see, for instance, [8-10]. However, the perturbation analysis and the backward error analysis for these algorithms have not been studied, which are important to the analysis of the accuracy and stability for computing the largest eigenvalue by these algorithms.

In this paper, we are interested in studying the perturbation bound for the spectral radius of an mth-order n-dimensional nonnegative tensor A. The main contribution of this paper is to show that when A is perturbed to a nonnegative tensor [??] by [DELTA]A and A has a positive Perron vector x, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

where [D.sub.x] = diag([x.sub.1], [x.sub.2], [x.sub.n]) is a diagonal matrix, for an mth-order n-dimensional tensor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and an n-by n matrix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and the tensor-matrix multiplication [11] R = P[x.sub.j]Q is a tensor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of order m and dimension n with its entries given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

the maximum norm of a tensor is defined as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

The perturbation bound (6) shows that the absolute difference between the spectral radii of A and [??] is bounded by the largest magnitude of the ratio of the ith component of [DELTA]A[x.sup.m-1] and the ith component [x.sup.m-1]. We further derive the bound based on the entries of A when x is not necessary to be known. Moreover, there is no convergence result of numerical algorithms [9, 10] for computing the spectral radius of a nonnegative tensor in general. We will make use of our perturbation results to estimate the spectral radius of a nonnegative tensor in general via the NQZ algorithm (see [10]).

On the other hand, we will study the backward error matrix [DELTA]A and obtain its smallest error bound of [DELTA]A for

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

such that [??] is an irreducible nonnegative tensor, [??] is the largest eigenvalue of [??], and [??] is a Perron vector of [??] by the NQZ algorithm. Our theoretical results show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be chosen as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [[parallel][??][parallel].sub.2] denotes the vector 2norm. By using these backward error results, we will evaluate the stability of computation of the largest eigenvalue of an irreducible nonnegative tensor by the NQZ algorithm.

The paper is organized as follows. In Section 2, we review the existing results and present the results for the perturbation bound of the spectral radius of a nonnegative tensor. In Section 3, we give the explicit expression of the backward error for the computation of the largest eigenvalue of an irreducible nonnegative tensor by the NQZ algorithm. Finally, concluding remarks are given in Section 4.

2. The Perturbation Bound of the Spectral Radius

Let us first state some preliminary results of a nonnegative tensor.

Lemma 4 (see [7, Lemma 5.2]). Suppose A is an mth-order n-dimensional nonnegative tensor. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (11)

Lemma 5 (see [7, Lemma 5.1]). Suppose A is an mth-order n-dimensional nonnegative tensor. If

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

then [rho](A) = c.

Lemma 6. Suppose A is an mth-order n-dimensional nonnegative tensor with a positive Perron vector x. Then one has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (13)

where [D.sub.x] = diag([x.sub.1], [x.sub.2], ..., [x.sub.n]).

Proof. By Theorem 3, we note that A[x.sup.m-1] = [[lambda].sub.0]x[m-1] and [[lambda].sub.0] is the largest eigenvalue of A. Therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

The result follows.

Theorem 7. Suppose A is an mth-order n-dimensional nonnegative tensor, [??] = A + [DELTA]A is the perturbed nonnegative tensor of A, and [??] has a positive Perron vector z. Then one has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

where [D.sub.z] = diag([z.sub.1], [z.sub.2], ..., [z.sub.n]) and e is a vector of all ones.

Proof. Let us consider the tensor B = [??] - [rho](A)J, where F is the identity tensor.

For an mth-order n-dimensional identity tensor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (16)

It is clear that the eigenvalue of B is the same as the eigenvalue of B[x.sub.1][[SIGMA].sup.z(m-1)][x.sub.2][SIGMA][x.sub.3] ... [x.sub.m][SIGMA] for any positive diagonal matrix [SIGMA]. Then we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (17)

By choosing [SIGMA] = [D.sub.z] = diag([z.sub.1], [z.sub.2], ..., [z.sub.n]), where z is a positive Perron vector of [??], we have, for [i.sub.1] = 1, ..., n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

On the other hand, we can deduce that, for [i.sub.1] = 1, ..., n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (19)

Taking [i.sub.1] = [i.sup.*] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

and then by using (20) with [i.sub.1] = [i.sup.*], we give the combination of (18) and 19) as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21)

Since the eigenvalue of A[D.sup.-(m-1).sub.z] [x.sub.2][D.sub.z][x.sub.3] ... [x.sub.m][D.sub.z] is the same as the eigenvalue of A, by using Lemma 4, 21) becomes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (22)

The right hand side of (15) is established. By using the above argument, we can show the left hand side of (15). ?

By Theorem 7, it is easy to obtain the following corollary.

Corollary 8. Suppose A is an mth-order n-dimensional nonnegative tensor, [??] = A + [DELTA]A is the perturbed nonnegative tensor of A, and [??] has a positive Perron vector z. Then one has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (23)

where [D.sub.z] = diag([z.sub.1], [z.sub.2], ..., [z.sub.n]).

It is noted that A can also be written as the perturbed tensor of [??]; that is, A = [??] - [DELTA]A. Then, by Theorem 7, we have the following bound.

Corollary 9. Suppose A is an mth-order n-dimensional nonnegative tensor with a positive Perron vector x, and [??] = A + [DELTA]A is the perturbed nonnegative tensor of A. Then one has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (24)

where [D.sub.x] = diag([x.sub.1], [x.sub.2], ..., [x.sub.n]).

According to Corollary 9, we know that the absolute difference between the spectral radii of A and [??] is bounded by the largest magnitude of the ratio of the ith component of [DELTA]A[x.sup.m-1] and the ith component [x.sup.m-1].

Remark 10. In the nonnegative matrix case (m = 2), if A is irreducible nonnegative matrix with positive Perron vector x, then the perturbation of the eigenvalues of [??] = A + [DELTA]A and A is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (25)

see [12]. It is easy to see that our perturbation result in Corollary 9 can be reduced to the bound in 25).

Remark 11. In [6], it has been shown that if A is symmetric and weakly irreducible, then A has a positive Perron vector. In particular, when A is irreducible, A also has a positive Perron vector; see [4-6].

In Corollary 9, a Perron vector x must be known in advance so that the perturbation bound can be computed. Here we derive the perturbation bound in terms of the entries of A only.

Lemma 12. Suppose A is an mth-order (m [greater than or equal to] 3) n dimensional positive tensor. Then one has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (26)

where x is the positive Perron vector, [x.sub.s] = [max.sub.1[less than or equal to]i[less than or equal to]n][x.sub.i], and [x.sub.t] = [max.sub.1[less than or equal to]i[less than or equal to]n][x.sub.i].

Proof. Since A is a positive tensor, A must be irreducible and has a positive Perron vector. The left hand side of (26) is straightforward. Now we consider

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (27)

for 2 [less than or equal to]k [less than or equal to] n. It implies that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (28)

Similarly, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (29)

Thus we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (30)

We note that, for any positive numbers [c.sub.i], [b.sub.i], and [y.sub.i] (i = 1,2, ..., n), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (31)

As A is a positive tensor and x is a positive vector, it follows from the above inequalities and 30) that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (32)

Because the above upper bound is valid for 2 [less than or equal to] k, k' [less than or equal to] m, we take the minimum among them over 2 [less than or equal to] k, k' [less than or equal to] m and we obtain the following inequality:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (33)

The result follows.

Based on Lemma 12, we have the following lemma.

Lemma 13. Suppose A is an mth-order n-dimensionalpositive tensor (m [greater than or equal to] 3), and [??] = A + [DELTA]A is the perturbed nonnegative tensor of A. Then one has

[absolute value of ([rho]([??]) - [rho](A))] [less than or equal to] [tau](A) [[parallel][DELTA],A[parallel].sub.[infinity]], (34)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (35)

Proof. By using (25) in Corollary 9, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (36)

The result follows.

Remark 14. The perturbation bound in Lemma 13 can be achieved by considering A = E and [??] = E + [epsilon]l, where e is a positive real number and E is a tensor with all the entries being equal to one. It is clear that E is irreducible; that is, E has the unique positive Perron vector. And we just note that the largest eigenvalues of E and E + [epsilon]1 are equal to [n.sup.m-1] and [n.sup.m-1] + [epsilon], respectively, [[parallel][DELTA]A[parallel].sub.[infinity]] = [epsilon], and [tau](E) = 1.

Corollary 15. Suppose A is an mth-order n-dimensional nonnegative tensor, and [??] = A + [DELTA]A is the perturbed positive tensor of A. Then one has

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (37)

where [tau](*) is defined in (35).

Proof. We just switch the roles of A and [??] in Lemma 13.

Let us state the following lemma to handle the case when A is a nonnegative tensor.

Lemma 16. Suppose A is an mth-order n-dimensional nonnegative tensor, and [A.sub.k] = A + (1/k)E. Then [rho](A) = [lim.sub.k[right arrow][infinity]] [rho]([A.sub.k]).

The proof of this lemma is similar to Theorem 2.3 given in [7].

Suppose that A is a nonnegative tensor. Let [A.sub.k] = A + (1/k) J. It is clear that [A.sub.k] is a positive tensor. Let [[??].sub.k] = [A.sub.k] + [DELTA]A be a perturbed nonnegative tensor of [A.sub.k]. By applying Corollary 15 to [A.sub.k] and [[??].sub.k],we have

[absolute value of ([rho]([[??].sub.k])-[rho]([A.sub.k]))] [less than or equal to]([A.sub.k]) [[parallel][DELTA]A[parallel].sub.[infinity]]. (38)

Therefore, when k [right arrow] [infinity], by Lemma 16, we have the following theorem.

Theorem 17. Suppose A is an mth-order n-dimensional nonnegative tensor, and [??] = A + [DELTA]A is the perturbed nonnegative tensor of A. Then one has

[absolute value of ([rho]([??])-[rho](A))] [less than or equal to][tau] (A)[[parallel][DELTA]A[parallel].sub.[infinity]] (39)

provided that [tau](A) > 0.

Example 18. We conduct an experiment to verify the perturbation bound. We randomly construct a positive tensor A, where each entry is generated by uniform distribution [0,1]. We further check the value of each entry must be greater than zero, and therefore the constructed tensor is positive. In the experiment, A is perturbed to a positive tensor [??] by adding [epsilon][DELTA]A, where e is a positive number and [DELTA]A is a positive tensor randomly generated by the above-mentioned method. We study the absolute difference [absolute value of ([rho] - [??])] between the spectral radii of A and [??] and the perturbation bound in Corollary 9. In Figure 1, we show the results for n = 5,10 and m = 4. For each point in the figure, we give the average value of [absolute value of ([rho] - [??])], [[parallel][DELTA]A [x.sub.1][D..sup.-(m- 1).sub.x][x.sub.2][D.sub.x][x.sub.3] ... [x.sub.m][D.sub.x][parallel].sub.[infinity]], or t(A) [[parallel][DELTA]A[parallel].sub.[infinity]] based on the computed results for 100 randomly constructed positive tensors. The x-axis refers to values of [epsilon]: 0.01, 0.005, 0.001, 0.0005, 0.0001, and 0.00005. We see from the figures that the average values (in logarithm scale) depend linearly on [epsilon] (in logarithm scale). The perturbation bounds [[parallel][DELTA]A [x.sub.1][D..sup.-(m-1).sub.x][x.sub.2][D.sub.x][x.sub.3] ... [x.sub.m][D.sub.x][parallel].sub.[infinity]] and [tau](A) [[parallel][DELTA]A[parallel].sub.[infinity]] provide the upper bound of [absolute value of ([rho]-[??])]. This result is consistent with our prediction in the theory. It is interesting to note that the bound [[parallel][DELTA]A[D.sup.-(m-1).sub.x][x.sub.2][D.sub.x][x.sub.3] ... [x.sub.m][D.sub.x][parallel].sub.[infinity]] is very close to the actual difference.

2.1. Application to the NQZ Algorithm. In this subsection, we apply our perturbation results to the NQZ algorithm [10] which is an iterative method for finding the spectral radius of a nonnegative tensor. The NQZ algorithm presented in [10] is given as follows.

Choose [u.sup.(0)] [member of] int(P) and let v = A[([u.sup.(0)]).sup.m-1]. For k = 0,1,2, ..., compute

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (40)

It is shown in [10] that the sequences {[[lambda].bar]} and {[bar.[lambda]]} converge to some numbers [[lambda].bar] and [bar.[lambda]], respectively, and we have [[lambda].bar] [less than or equal to] [rho](A) [less than or equal to] [bar.[lambda]]. If [[lambda].bar] = [bar.[lambda]], the gap is zero and therefore both the sequences {[[lambda].bar]} and {[bar.[lambda]]} converge to [rho](A). However, a positive gap may happen, which can be seen in an example given in 10]. Pearson [13] introduced the notion of essentially positive tensors and showed the convergence of the NQZ algorithm for essentially positive tensors. Chang et al. [8] further established the convergence of the NQZ algorithm for primitive tensors.

Definition 19. An mth-order n-dimensional tensor A is essentially positive if A[y.sup.m-1] [member of] int(P) for any nonzero y [member of] P.

Definition 20. An mth-order n-dimensional tensor A is called primitive if there exists a positive integer k such that [A.sup.k]y [member of] int(P) for any nonzero y [member of] P.

An essentially positive tensor is a primitive tensor, and a primitive tensor is an irreducible nonnegative tensor but not vice versa.

Now we demonstrate how to use the results in Theorem 7 to estimate the spectral radius of a nonnegative tensor via the NQZ algorithm. For example, when A is a reducible nonnegative tensor, then the NQZ algorithm may not be convergent. Our idea is to take a small perturbation [DELTA]A = [epsilon] J, where e is a very small positive number and J is a tensor with all the entries being equal to one. It is clear that [??] = A + [epsilon]J is essentially positive. Therefore, when we apply the NQZ algorithm to compute the largest eigenvalue of [??], it is convergent. Without loss of generality, we normalize the output vector u in the NQZ algorithm. In particular, the 1norm of u is employed. The output of the algorithm contains a positive number [??] and u > 0 with [[parallel]u[parallel].sub.1] = 1 (i.e., [[summation].sup.n.sub.i=1] [u.sub.i] = 1). We note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (41)

Then, by Theorem 7, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (42)

That is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (43)

Let [u.sub.s] = [max.sub.1[less than or equal to]i[less than or equal to]n][u.sub.i] and [u.sub.t] = [min.sub.1[less than or equal to]i[less than or equal to]n][u.sub.i]. By considering m [greater than or equal to] 3,we know that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; (44)

that is, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (45)

or

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (46)

On the other hand,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (47)

By putting (46) and (47) into (43), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (48)

One may know [rho](A) = [??] + O([epsilon]) if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (49)

This shows that we can estimate [rho](A) of a nonnegative tensor A with a specified precision via the NQZ algorithm for the computation of p([??]).

Remark 21. Liu et al. [9] modified the NQZ algorithm for computing the spectral radius of A + [epsilon]f, where A is an irreducible nonnegative tensor and [epsilon] is a very small number, and showed that the algorithm converges to [rho](A) + [epsilon]. This fact can be explained by our theoretical analysis in Theorem 7 by setting [DELTA]A = [epsilon]f. We just note that the left and right sides of the inequality in (15) are equal to [epsilon]; that is, [epsilon] [less than or equal to] [rho]([??]) - [rho](A) [less than or equal to] [member of]. It implies that [rho]([??]) = [rho](A) + [epsilon]. However, when the given nonnegative tensor is not irreducible, then their results cannot be valid. However, our approach can still be used to estimate the spectral radius of a nonnegative tensor in general.

Example 22. In [8], the following 3rd order 3-dimensional nonnegative tensor is considered: [a.sub.1,2,2] = [a.sub.1,3,3] = [a.sub.2,1,1] = [a.sub.3,1,1] = 1 and the other entries are equal to zero. It can be shown that this tensor A is irreducible, but not primitive. There is no convergence result of the NQZ algorithm for such A, and the spectral radius of A is equal to [square root of (2)] [perpendicular to] 1.414213562373095; see [8]. In this example, we take the perturbation [DELTA]A = [epsilon]J. We apply the NQZ algorithm to compute the spectral radius of [??] to approximate the actual one. According to Table 1, the results show that [rho](A) is about [rho]([??]) + O([epsilon]).

Example 23. We consider the following 3rd order 3dimensional nonnegative tensor: [a.sub.1,1,1] = [a.sub.1,2,2] = [a.sub.1,3,3] = [a.sub.2,1,1] = [a.sub.2,2,2] = [a.sub.2,3,3] = [a.sub.3,1,1] = [a.sub.3,2,2] = [a.sub.3,3,3] = 1 and the other entries are equal to zero. It can be shown that this tensor A is reducible. The spectral radius of A is equal to 3. There is no convergence result of the NQZ algorithm for such reducible nonnegative tensor. It is interesting to note that this tensor satisfies (49). In this example, we take the perturbation [DELTA]A = [epsilon]J. The spectral radii of [??] by the NQZ algorithm are still accurate approximations of [rho](A): 3.090000000000000 (e = 0.01), 3.009000000000000 ([epsilon] = 0.001), 3.000900000000000 ([epsilon] = 0.0001), 3.000090000000001 ([epsilon] = 0.00001), and 3.000009000000000 ([espilon] = 0.000001). Indeed, both the values in the left and right sides of (43) are equal to 3.000000000000000 (up to the number of decimals shown in MATLAB). These results show the bounds are very tight and [rho](A) is about [rho]([??]) + O([epsilon]).

Example 24. Now we consider the following 3rd order 3dimensional nonnegative tensor: [a.sub.1,1,1] = 1 and the other entries are equal to zero. A is a reducible nonnegative tensor. For such A, we know the a is the spectral radius of A and [[1, 0, ..., 0].sup.T] is the corresponding eigenvector (the normalized in 2-norm). In this example, we take the perturbation [DELTA]A = [epsilon]J. Although this tensor does not satisfy (49), the spectral radii of [??] by the NQZ algorithm are still accurate approximate of [rho](A): 1.015565072567277 ([epsilon] = 0.01), 1.001139501996208 ([epsilon] = 0.001), 1.000104123060726 ([epsilon] = 0.0001), 1.000010127700654 ([epsilon] = 0.00001), and 1.000001004012030 ([epsilon] = 0.000001). We find that the values in the left and right sides of (43) are close to 1 and 0, respectively, for different values of e. It is clear that the bounds are not tight. It is interesting to note that the maximum and minimum values of the entries of the associated eigenvector are 1 and 0; we expect that the error bound in (43) can be very poor. Indeed, the errors between the actual eigenvector and the approximate eigenvector are 0.243064619277186 ([epsilon] = 0.01), 0.077415571882820 ([epsilon] = 0.001), 0.024493622285564 ([epsilon] = 0.0001), 0.007745927468297 ([epsilon] = 0.00001), and 0.002449488513126 ([epsilon] = 0.000001). Thus the approximation is more accurate for the largest eigenvalue than for the associated eigenvector.

3. Backward Error Bound

In this section, we study the backward error tensor [DELTA]A and obtain its smallest error bound of [DELTA]A such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (50)

where A and [??] = A + [DELTA]A are irreducible nonnegative tensors with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for 1 [less than or equal to] [i.sub.1], [i.sub.2], ..., [i.sub.m] [less than or equal to] n, [??] is the largest eigenvalue of [??], and [??] is a Perron vector of [??]. The backward error for the eigenpair is defined as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (51)

where

[OMEGA] = {[DELTA]A is a nonnegative tensor such that A + [DELTA]A is irreducible} (52)

and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Before we show the results of the backward error in the computation of the largest eigenvalue of an irreducible nonnegative tensor, we need the following lemma given in [14, Theorem 9.1].

Lemma 25. Let U [member of] [C.sup.pxq], V [member of] [C.sup.rxs], and W [member of] [C.sup.pxs]. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (53)

Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (54)

if and only if X [not equal to] 0, and when Y [not equal to] 0, X = Y, where [*.sup.*] denotes the conjugate transpose of a matrix, [U.sup.[dagger]] is the Moore-Penrose generalized inverse of U, [P.sub.U] = U[U.sup.[dagger]], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now we show the main result of this section.

Theorem 26. Suppose A is an mth-order n-dimensional irreducible nonnegative tensor. Let [bar.[lambda]] and u be the output of the NQZ algorithm (stated in Section 2.1) applied to A, and r = [bar.[lambda]][u.sup.[m-1]] - A[u.sup.m-1]. Then the backward error for [bar.[lambda]] and u of the perturbed irreducible nonnegative tensor A + [DELTA]A is given by

[eta](u) = [[parallel]r[parallel].sub.2] / [[parallel]u[parallel].sup.m-1.sub.2] (55)

and [DELTA]A can be chosen as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (56)

Proof. We note that

[DELTA]A[u.sup.m-1] = [bar.[lambda]][u.sup.[m-1]] - [bar.[lambda]][u.sup.m-1] = r. (57)

In order to analyze u, we rewrite the above equation into a linear system as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (58)

where [DELTA]A is an n-by-[n.sup.m-1] matrix with its entries given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (59)

It follows from Lemma 25 that

[DELTA]A = [rb.sup.[dagger]] + z(I- [bb.sup.[dagger]]), (60)

where [b.sup.[dagger]] is an 1-by-[n.sup.m-1] vector given by b/[[parallel]b[parallel].sub.2] and Z is an n-by-[n.sup.m-1] matrix. Therefore, we obtain

[[parallel][DELTA]A[parallel].sup.2.sub.F] = [[parallel][rb.sup.[dagger]][parallel].sup.2.sub.F] + [[parallel]Z(I- [bb.sup.[dagger]])[parallel].sup.2.sub.F]. (61)

The minimization of [[parallel][DELTA]A[parallel].sup.2.sub.F] is equivalent to finding a matrix Z such that [[parallel][rb.sup.[dagger]][parallel].sup.2.sub.F] + [parallel]Z(I - [bb.sup.[dagger]])[parallel].sup.2.sub.F] can be minimized. It is clear that we choose Z = 0; that is, min [[parallel][DELTA]A[parallel].sub.F] = [parallel][rb.sup.[dagger]][parallel].sup.2.sub.F].

According to the NQZ algorithm stated in Section 2.1, we know that r is nonnegative. As u is positive, both b and [b.sup.[dagger]] are also positive. Let us consider two cases. We note that if r is a zero vector, then [bar.[lambda]] is the largest eigenvalue of A, and the problem is solved. Now we consider r is not a zero vector. It follows that at least one row of [DELTA]A = [rb.sup.[dagger]] must be positive. It can be shown that [??] is irreducible. The argument is that for any nonempty proper index subset J [subset] {1,2, ..., n} such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (62)

Hence the result follows.

Remark 27. When m = 2, the results of the backward error are reduced to the results in Theorem 6.3.2 in [14]; that is,

[eta]([??]) = [[parallel][r[??].sup.[dagger]][parallel].sub.F]. (63)

Example 28. Let us conduct an experiment to check the backward error when we use the NQZ algorithm for computing the largest eigenvalue of an irreducible nonnegative tensor. We randomly construct a positive tensor A, where each entry is generated by uniform distribution [0,1]. We further check the value of each entry must be greater than zero, and therefore the constructed tensor is positive. In Table 2, we show the average backward error based on the computed results for 100 randomly constructed positive tensors. We see from the table that the backward error can be very small, but it still depends on the order m of and the dimension n of the tensor. The backward error is large when m or n is large.

4. Concluding Remarks

In summary, we have studied and derived the perturbation bounds for the spectral radius of a nonnegative tensor. Numerical examples have been given to demonstrate our theoretical results. Also we have investigated the backward error matrix [DELTA]A and obtain its smallest error bound for its perturbed largest eigenvalue and associated eigenvector of an irreducible nonnegative tensor. Numerical examples have shown that the backward error can be very small. These results may show that the NQZ algorithm may be backward stable for the computation of the largest eigenvalue of an irreducible nonnegative tensor.

In this paper, we do not study the perturbation bound of the eigenvector corresponding to the largest eigenvalue of a nonnegative tensor. This would be an interesting research topic for future consideration.

http://dx.doi.org/10.1155/2014/109525

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The authors thank the referee for his/her valuable suggestions. Wen Li was supported in part by National Natural Science Foundations of China (nos. 10971075, 11271144), Guangdong Provincial Natural Science Foundations (no. s2012010009985), and Project of Department of Education of Guangdong Province (no. 2013KJCX0053). Research was supported in part by RGC GRF Grant no. 201812.

References

[1] X. Li, M. K. Ng, and Y. Ye, "HAR: hub, authority and relevance scores in multi-relational data for query search," in Proceedings of the 12th SIAM International Conference on Data Mining (SDM '12), pp. 141-152, Anaheim, Calif, USA, April 2012.

[2] M. K. Ng, X. Li, and Y. Ye, "MultiRank: co-ranking for objects and relations in multi-relational data," in Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '11), pp. 1217-1225, August 2011.

[3] L. Qi, "Eigenvalues of a real supersymmetric tensor," Journal of Symbolic Computation, vol. 40, no. 6, pp. 1302-1324, 2005.

[4] L.-H. Lim, "Singular values and eigenvalues of tensors: a variational approach," in Proceedings of the 1st IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 05), pp. 129-132, Puerto Vallarta, Mexico, December 2005.

[5] K. C. Chang, K. Pearson, and T. Zhang, "Perron-Frobenius theorem for nonnegative tensors," Communications in Mathematical Sciences, vol. 6, no. 2, pp. 507-520, 2008.

[6] S. Friedland, S. Gaubert, and L. Han, "Perron-Frobenius theorem for nonnegative multilinear forms and extensions," Linear Algebra and its Applications, vol. 438, no. 2, pp. 738-749, 2013.

[7] Y. Yang and Q. Yang, "Further results for Perron-Frobenius theorem for nonnegative tensors," SIAM Journal on Matrix Analysis and Applications, vol. 31, no. 5, pp. 2517-2530, 2010.

[8] K.-C. Chang, K. J. Pearson, and T. Zhang, "Primitivity, the convergence of the NQZ method, and the largest eigenvalue for nonnegative tensors," SIAM Journal on Matrix Analysis and Applications, vol. 32, no. 3, pp. 806-819, 2011.

[9] Y. Liu, G. Zhou, and N. F. Ibrahim, "An always convergent algorithm for the largest eigenvalue of an irreducible nonnegative tensor," Journal of Computational and Applied Mathematics, vol. 235, no. 1, pp. 286-292, 2010.

[10] M. Ng, L. Qi, and G. Zhou, "Finding the largest eigenvalue of a nonnegative tensor," SIAM Journal on Matrix Analysis and Applications, vol. 31, no. 3, pp. 1090-1099, 2009.

[11] L. de Lathauwer, B. de Moor, and J. Vandewalle, "A multilinear singular value decomposition," SIAM Journal on Matrix Analysis and Applications, vol. 21, no. 4, pp. 1253-1278, 2000.

[12] S. L. Liu and S. Y. Wang, "Sensitivity analysis of nonnegative irreducible matrices," Applied Mathematics Letters, vol. 12, no. 2, pp. 121-124, 1999.

[13] K. Pearson, "Essentially positive tensors," International Journal of Algebra, vol. 4, pp. 421-427, 2010.

[14] J. Sun, Matrix Perturbation Analysis, Science Press, Beijing, China, 2001.

Wen Li (1) and Michael K. Ng (2)

(1) School of Mathematical Sciences, South China Normal University, Guangzhou, China

(2) Department of Mathematics, Hong Kong Baptist University, Hong Kong

Correspondence should be addressed to Michael K. Ng; mng@math.hkbu.edu.hk Received 29 March 2014; Revised 29 August 2014; Accepted 9 September 2014; Published 28 September 2014 Academic Editor: Nils Henrik Risebro

TABLE 1: Numerical results for different e in Example 22.

[epsilon]   [rho]([??]) - [[epsilon]/    [rho]([??]) - [[epsilon]/
               [min.sub.1[less than         [max.sub.1[less than
                or equal to]i[less           or equal to]i[less
               than or equal to]n]          than or equal to]n]
                [u.sup.m-1.sub.i]]           [u.sup.m-1.sub.i]]

1e-2            1.399817488643705            1.428757688931172
1e-3            1.412729187546902            1.415699496853463
1e-4            1.414064662464100            1.414362477963432
1e-5            1.414198667753479            1.414228457171375
1e-6            1.414212073004730            1.414215052025221

[epsilon]      Difference

1e-2        0.028940200287467
1e-3        0.002970309306561
1e-4        0.000297815499332
1e-5        0.000029789417896
1e-6        0.000002979020491

TABLE 2: The backward errors for different cases.

m    n    Backward error
           [eta]([??])

3    5      1.2297e-15
3    10     5.5960e-15
3    20     1.5579e-14
3    40     5.9253e-14
4    5      9.9174e-15
4    10     6.4772e-14
4    20     4.3210e-13
4    40     2.9931e-12
COPYRIGHT 2014 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Li, Wen; Ng, Michael K.
Publication:Advances in Numerical Analysis
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2014
Words:5866
Next Article:Nonlinear double-layer Bragg waveguide: analytical and numerical approaches to investigate waveguiding problem.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |