# The Perturbation Bound for the Spectral Radius of a Nonnegative Tensor

Authors: Wen Li; Michael K. Ng
Journal: Advances in Numerical Analysis
 (2014)

---

## Abstract

We study the perturbation bound for the spectral radius of anmth-order n-dimensional nonnegative tensor A. The main contribution of this paper is to show that when A is perturbed to a nonnegative tensor A~ by ΔA, the absolute difference between the spectral radii of A and A~ is bounded by the largest magnitude of the ratio of the ith component of ΔAxm-1 and the ith component xm-1, where x is an eigenvector associated with the largest eigenvalue of A in magnitude and its entries are positive. We further derive the bound in terms of the entries of A only when x is not known in advance. Based on the perturbation analysis, we make use of the NQZ algorithm
to estimate the spectral radius of a nonnegative tensor in general. On the other hand, we study the backward error matrix ΔA and obtain its smallest error bound for its perturbed largest eigenvalue and associated eigenvector of an irreducible nonnegative tensor. Based on the backward error analysis, we can estimate the stability of computation of the largest eigenvalue of an irreducible nonnegative tensor by the NQZ algorithm. Numerical examples are presented to illustrate the theoretical results of our perturbation analysis.


---

## Body

## 1. Introduction

LetR be the real field. We consider an mth order n-dimensional tensor A consisting of nm entries in R:
(1)A=(ai1,i2,…,im),ai1,i2,…,im∈R,1≤i1,i2,…,im≤n.A is called nonnegative (or, resp., positive) if ai1,i2,…,im≥0 (or, resp., ai1,i2,…,im>0). In the following discussion, for a given vector y=(y1,y2,…,yn)T∈Rn, we define a tensor-vector multiplication Aym-1 to be n-dimensional column vector with its i1th entries given by
(2)∑i2,…,im=1n‍ai1,i2,…,imyi2⋯yim,1≤i1≤n.
Also we let P={(y1,y2,…,yn)∣yi≥0} be the positive cone, and we let the interior of P be denoted as int⁡(P)={(y1,y2,…,yn)∣yi>0}. When y∈P (or y∈int⁡(P)), y is a nonnegative (or a positive) vector. We denote the ith component of y by (y)i or yi, and we denote the (i1,i2,…,im)th entry of A by (A)i1,i2,…,im or ai1,i2,…,im.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.
LetA be an mth-order n-dimensional tensor and let C be the set of all complex numbers. Assume that Axm-1 is not identical to zero. We say (λ,x)∈C×(Cn∖{0}) is an H-eigenpair of A if
(3)Axm-1=λx[m-1].
Here, x[α]:=(x1α,x2α,…,xnα)T. The spectral radius ρ(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 λ 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.
Anmth-order n-dimensional tensor A is called reducible if there exists a nonempty proper index subset J⊂{1,2,…,n} such that
(4)ai1,i2,…,im=0,∀i1∈J,∀i2,…,im∉J.
If A is not reducible, then we call A irreducible.Theorem 3.
SupposeA is an mth-order n-dimensional nonnegative tensor. (i)
Then there existλ0≥0 and x∈P such that
(5)Axm-1=λ0x[m-1].(ii)
IfA is irreducible, then λ0>0 and x∈int⁡(P). Moreover, if λ is an eigenvalue with a nonnegative eigenvector, then λ=λ0. If λ is an eigenvalue of A, then |λ|≤λ0.We callx 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 anmth-order n-dimensional nonnegative tensor A. The main contribution of this paper is to show that when A is perturbed to a nonnegative tensor A~ by ΔA and A has a positive Perron vector x, we have
(6)|ρ(A)-ρ(A~)|≤∥ΔA×1Dx-(m-1)×2Dx×3⋯×mDx∥∞,
where Dx=diag⁡(x1,x2,…,xn) is a diagonal matrix, for an mth-order n-dimensional tensor P=(pi1,i2,…,im) and an n-by-n matrix Q=(qij,ij′), and the tensor-matrix multiplication [11] R=P×jQ is a tensor (ri1,i2,…,im) of order m and dimension n with its entries given by
(7)ri1,…,ij-1,ij′,ij+1,…,im≡∑ij=1n‍pi1,…,ij-1,ij,ij+1,…,imqij,ij′;
the maximum norm of a tensor is defined as follows:
(8)∥P∥∞≡max⁡1≤ii≤n∑i2,…,im=1n‍|pi1,i2,…,im|.
The perturbation bound (6) shows that the absolute difference between the spectral radii of A and A~ is bounded by the largest magnitude of the ratio of the ith component of ΔAxm-1 and the ith component xm-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ΔA and obtain its smallest error bound of ΔA for
(9)A~x~m-1=(A+ΔA)x~m-1=λ~x~m-1
such that A~ is an irreducible nonnegative tensor, λ~ is the largest eigenvalue of A~, and x~ is a Perron vector of A~ by the NQZ algorithm. Our theoretical results show that ΔA=(δai1,i2,…,im) can be chosen as follows:
(10)δai1,i2,…,im=(r)i1·(x~)i2⋯(x~)im∥x~∥22(m-1),
where r=λ~x~[m-1]-Ax~m-1 and ∥x~∥2 denotes the vector 2-norm. 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 Section2, 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]).
SupposeA is an mth-order n-dimensional nonnegative tensor. Then we have
(11)min⁡1≤i1≤n∑i2,…,im=1n‍ai1,i2,…,im≤ρ(A)≤max⁡1≤i1≤n∑i2,…,im=1n‍aii,i2,…,im.Lemma 5 (see [7, Lemma 5.1]).
SupposeA is an mth-order n-dimensional nonnegative tensor. If
(12)∑i2,…,im=1n‍ai1,i2,…,im=c,i1=1,…,n,
then ρ(A)=c.Lemma 6.
SupposeA is an mth-order n-dimensional nonnegative tensor with a positive Perron vector x. Then one has
(13)∑i2,…,im=1n‍(A×1Dx-(m-1)×2Dx×3⋯×mDx)i1,i2,…,im=ρ(A),i1=1,…,n,
where Dx=diag⁡(x1,x2,…,xn).Proof.
By Theorem3, we note that Axm-1=λ0x[m-1] and λ0 is the largest eigenvalue of A. Therefore,
(14)∑i2,…,im=1n‍(A×1Dx-(m-1)×2Dx×3⋯×mDx)i1,i2,…,im=λ0.
The result follows.Theorem 7.
SupposeA is an mth-order n-dimensional nonnegative tensor, A~=A+ΔA is the perturbed nonnegative tensor of A, and A~ has a positive Perron vector z. Then one has
(15)min⁡1≤ii≤n(ΔA×1Dz-(m-1)×2Dz×3⋯×mDzem-1)i1≤ρ(A~)-ρ(A)≤max⁡1≤ii≤n(ΔA×1Dz-(m-1)×2Dz×3⋯×mDzem-1)i1,
where Dz=diag⁡(z1,z2,…,zn) and e is a vector of all ones.Proof.
Let us consider the tensorB=A~-ρ(A)I, where I is the identity tensor.
For anmth-order n-dimensional identity tensor I=(ii1,i2,…,im),
(16)ii1,i2,…,im={1,i1=i2=⋯=im,0,otherwise.
It is clear that the eigenvalue of B is the same as the eigenvalue of B×1Σ-(m-1)×2Σ×3⋯×mΣ for any positive diagonal matrix Σ. Then we obtain
(17)B×1Σ-(m-1)×2Σ×3⋯×mΣ=A~×1Σ-(m-1)×2Σ×3⋯×mΣ-ρ(A)I.
By choosing Σ=Dz=diag⁡(z1,z2,…,zn), where z is a positive Perron vector of A~, we have, for i1=1,…,n,
(18)∑i2,…,im=1n‍(B×1Dz-(m-1)×2Dz×3⋯×mDz)i1,i2,…,im=∑i2,…,im=1n‍(A~×1Dz-(m-1)×2Dz×3⋯×mDz)i1,i2,…,im-ρ(A)∑i2,…,im=1n‍Ii1,i2,…,im=ρ(A~)-ρ(A).
On the other hand, we can deduce that, for i1=1,…,n,
(19)∑i2,…,im=1n‍(B×1Dz-(m-1)×2Dz×3⋯×mDz)i1,i2,…,im=∑i2,…,im=1n‍((A+ΔA)×1Dz-(m-1)×2Dz×3⋯×mDz)i1,i2,…,im-ρ(A)∑i2,…,im=1n‍Ii1,i2,…,im=∑i2,…,im=1n‍((A+ΔA)×1Dz-(m-1)×2Dz×3⋯×mDz)i1,i2,…,im-ρ(A)=∑i2,…,im=1n‍(A×1Dz-(m-1)×2Dz×3⋯×mDz)i1,i2,…,im-ρ(A)+∑i2,…,im=1n‍(ΔA×1Dz-(m-1)×2Dz×3⋯×mDz)i1,i2,…,im.
Taking i1=i* such that
(20)∑i2,…,im=1n‍(A×1Dz-(m-1)×2Dz×3⋯×mDz)i*,i2,…,im=min⁡1≤i1≤n∑i2,…,im=1n‍(A×1Dz-(m-1)×2Dz×3⋯×mDz)i1,i2,…,im,
and then by using (20) with i1=i*, we give the combination of (18) and (19) as follows:
(21)ρ(A~)-ρ(A)=∑i2,…,im=1n‍(A×1Dz-(m-1)×2Dz×3⋯×mDz)i*,i2,…,im-ρ(A)+∑i2,…,im=1n‍(ΔA×1Dz-(m-1)×2Dz×3⋯×mDz)i*,i2,…,im=min⁡1≤i1≤n∑i2,…,im=1n‍(A×1Dz-(m-1)×2Dz×3⋯×mDz)i1,i2,…,im-ρ(A)+∑i2,…,im=1n‍(ΔA×1Dz-(m-1)×2Dz×3⋯×mDz)i*,i2,…,im.
Since the eigenvalue of ADz-(m-1)×2Dz×3⋯×mDz is the same as the eigenvalue of A, by using Lemma 4, (21) becomes
(22)ρ(A~)-ρ(A)≤∑i2,…,im=1n‍(ΔA×1Dz-(m-1)×2Dz×3⋯×mDz)i*,i2,…,im≤max⁡1≤i1≤n∑i2,…,im=1n‍(ΔA×1Dz-(m-1)×2Dz×3⋯×mDz)i1,i2,…,im=max⁡1≤ii≤n(ΔA×1Dz-(m-1)×2Dz×3⋯×mDzem-1)i1.
The right hand side of (15) is established. By using the above argument, we can show the left hand side of (15).By Theorem7, it is easy to obtain the following corollary.Corollary 8.
SupposeA is an mth-order n-dimensional nonnegative tensor, A~=A+ΔA is the perturbed nonnegative tensor of A, and A~ has a positive Perron vector z. Then one has
(23)|ρ(A~)-ρ(A)|≤∥ΔA×1Dz-(m-1)×2Dz×3⋯×mDz∥∞,
where Dz=diag⁡(z1,z2,…,zn).It is noted thatA can also be written as the perturbed tensor of A~; that is, A=A~-ΔA. Then, by Theorem 7, we have the following bound.Corollary 9.
SupposeA is an mth-order n-dimensional nonnegative tensor with a positive Perron vector x, and A~=A+ΔA is the perturbed nonnegative tensor of A. Then one has
(24)min⁡1≤ii≤n(ΔA×1Dx-(m-1)×2Dx×3⋯×mDxem-1)i1≤ρ(A~)-ρ(A)≤max⁡1≤ii≤n(ΔA×1Dx-(m-1)×2Dx×3⋯×mDxem-1)i1,
where Dx=diag⁡(x1,x2,…,xn).According to Corollary9, we know that the absolute difference between the spectral radii of A and A~ is bounded by the largest magnitude of the ratio of the ith component of ΔAxm-1 and the ith component xm-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~=A+ΔA and A is given by
(25)min⁡1≤ii≤n(ΔDx-1ADxe)i1≤ρ(A~)-ρ(A)≤max⁡1≤ii≤n(ΔDx-1ADxe)i1;
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 Corollary9, 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.
SupposeA is an mth-order (m≥3) n-dimensional positive tensor. Then one has
(26)1≤xsxt≤min⁡2≤k,k′≤mmax⁡1≤ik=ik′≤n{∑i2,…,im=1︸exceptiknas,i2,…,im∑i2′,…,im′=1︸exceptik′nat,i2′,…,im′},
where x is the positive Perron vector, xs=max⁡1≤i≤nxi, and xt=min⁡1≤i≤nxi.Proof.
SinceA 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
(27)ρ(A)xtm-1=∑i2,…,im=1n‍at,i2,…,imxi2⋯xim≥(∑i2,…,im=1n‍at,i2,…,imxik)xtm-2,
for 2≤k≤n. It implies that
(28)ρ(A)xt≥∑i2,…,im=1n‍at,i2,…,imxik,2≤k≤n.
Similarly, we get
(29)ρ(A)xs≤∑i2,…,im=1n‍as,i2,…,imxik,2≤k≤n.
Thus we obtain
(30)xsxt≤∑i2,…,im=1nas,i2,…,imxik∑i2,…,im=1nat,i2′,…,im′xik′=∑ik=1n∑i2,…,im=1︸exceptiknas,i2,…,imxik∑ik′=1n∑i2′,…,im′=1︸exceptik′nat,i2′,…,im′xik′.
We note that, for any positive numbers ci, bi, and yi (i=1,2,…,n), we have
(31)b1y1+b2y2+⋯+bnync1y1+c2y2+⋯+cnyn≤max⁡1≤i≤nbici.
As A is a positive tensor and x is a positive vector, it follows from the above inequalities and (30) that
(32)xsxt≤max⁡1≤ik=ik′≤n{∑i2,…,im=1︸exceptiknas,i2,…,im∑i2′,…,im′=1︸exceptik′nat,i2′,…,im′}.
Because the above upper bound is valid for 2≤k, k′≤m, we take the minimum among them over 2≤k, k′≤m and we obtain the following inequality:
(33)xsxt≤min⁡2≤k,k′≤mmax⁡1≤ik=ik′≤n{∑i2,…,im=1︸exceptiknas,i2,…,im∑i2′,…,im′=1︸exceptik′nat,i2′,…,im′}.
The result follows.Based on Lemma12, we have the following lemma.Lemma 13.
SupposeA is an mth-order n-dimensional positive tensor (m≥3), and A~=A+ΔA is the perturbed nonnegative tensor of A. Then one has
(34)|ρ(A~)-ρ(A)|≤τ(A)∥ΔA∥∞,
where
(35)τ(A)≡(min⁡2≤k,k′≤mmax⁡1≤ik=ik′≤n{∑i2,…,im=1︸exceptiknas,i2,…,im∑i2′,…,im′=1︸exceptik′nat,i2′,…,im′})m-1.Proof.
By using (25) in Corollary 9, we have
(36)|ρ(A~)-ρ(A)|≤∥ΔA×1Dx-(m-1)×2Dx×3⋯×mDx∥∞≤∥Dx-(m-1)∥∞∥Dxm-1∥∞∥ΔA∥∞.
The result follows.Remark 14.
The perturbation bound in Lemma13 can be achieved by considering A=E and A~=E+ɛI, where ɛ 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+ɛI are equal to nm-1 and nm-1+ɛ, respectively, ∥ΔA∥∞=ɛ, and τ(E)=1.Corollary 15.
SupposeA is an mth-order n-dimensional nonnegative tensor, and A~=A+ΔA is the perturbed positive tensor of A. Then one has
(37)|ρ(A~)-ρ(A)|≤τ(A~)∥ΔA∥∞,
where τ(·) is defined in (35).Proof.
We just switch the roles ofA and A~ in Lemma 13.Let us state the following lemma to handle the case whenA is a nonnegative tensor.Lemma 16.
SupposeA is an mth-order n-dimensional nonnegative tensor, and Ak=A+(1/k)E. Then ρ(A)=lim⁡k→∞ρ(Ak).The proof of this lemma is similar to Theorem 2.3 given in [7].Suppose thatA is a nonnegative tensor. Let Ak=A+(1/k)J. It is clear that Ak is a positive tensor. Let A~k=Ak+ΔA be a perturbed nonnegative tensor of Ak. By applying Corollary 15 to Ak and A~k, we have
(38)|ρ(A~k)-ρ(Ak)|≤τ(Ak)∥ΔA∥∞.
Therefore, when k→∞, by Lemma 16, we have the following theorem.Theorem 17.
SupposeA is an mth-order n-dimensional nonnegative tensor, and A~=A+ΔA is the perturbed nonnegative tensor of A. Then one has
(39)|ρ(A~)-ρ(A)|≤τ(A)∥ΔA∥∞
provided that τ(A)>0.Example 18.
We conduct an experiment to verify the perturbation bound. We randomly construct a positive tensorA, 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 A~ by adding ɛΔA, where ɛ is a positive number and ΔA is a positive tensor randomly generated by the above-mentioned method. We study the absolute difference |ρ-ρ~| between the spectral radii of A and A~ 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 |ρ-ρ~|, ∥ΔA×1Dx-(m-1)×2Dx×3⋯×mDx∥∞, or τ(A)∥ΔA∥∞ based on the computed results for 100 randomly constructed positive tensors. The x-axis refers to values of ɛ: 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 ɛ (in logarithm scale). The perturbation bounds ∥ΔA×1Dx-(m-1)×2Dx×3⋯×mDx∥∞ and τ(A)∥ΔA∥∞ provide the upper bound of |ρ-ρ~|. This result is consistent with our prediction in the theory. It is interesting to note that the bound ∥ΔADx-(m-1)×2Dx×3⋯×mDx∥∞ is very close to the actual difference.The results of the perturbation bounds (a)n=5 and m=4 and (b) n=10 and m=4: — |λ-λ~| (the actual difference); – – – – ∥ΔADx-(m-1)×2Dx×3⋯×mDx∥∞ and – · – · – · – · τ(A)∥ΔA∥∞.
(a)
(b)


### 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.Chooseu(0)∈int⁡(P) and let v=A(u(0))m-1. For k=0,1,2,…, compute
(40)u(k)=(v(k))[1/(m-1)]∥(v(k))[1/(m-1)]∥;v(k+1)=A(u(k+1))m-1;λ_k+1=min⁡ui(k+1)>0vi(k+1)(ui(k+1))m-1;λ¯k+1=max⁡ui(k+1)>0vi(k+1)(ui(k+1))m-1.
It is shown in [10] that the sequences {λ_} and {λ¯} converge to some numbers λ_ and λ¯, respectively, and we have λ_≤ρ(A)≤λ¯. If λ_=λ¯, the gap is zero and therefore both the sequences {λ_} and {λ¯} converge to ρ(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.
Anmth-order n-dimensional tensor A is essentially positive if Aym-1∈int⁡(P) for any nonzero y∈P.Definition 20.
Anmth-order n-dimensional tensor A is called primitive if there exists a positive integer k such that Aky∈int⁡(P) for any nonzero y∈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 Theorem7 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 ΔA=ɛJ, where ɛ is a very small positive number and J is a tensor with all the entries being equal to one. It is clear that A~=A+ɛJ is essentially positive. Therefore, when we apply the NQZ algorithm to compute the largest eigenvalue of A~, it is convergent. Without loss of generality, we normalize the output vector u in the NQZ algorithm. In particular, the 1-norm of u is employed. The output of the algorithm contains a positive number λ~ and u>0 with ∥u∥1=1 (i.e., ∑i=1nui=1). We note that
(41)(ɛJDu-(m-1)×2Du×3⋯×mDuem-1)i1=∑i2,…,im=1n‍(ɛJ)i1,i2,…,imui2⋯uimui1m-1=ɛui1m-1∑i2,…,im=1n‍ui2⋯uim=ɛui1m-1.
Then, by Theorem 7, we have
(42)ɛmax⁡1≤i≤nuim-1≤ρ(A~)-ρ(A)≤ɛmin⁡1≤i≤nuim-1.
That is,
(43)ρ(A~)-ɛmin⁡1≤i≤nuim-1≤ρ(A)≤ρ(A~)-ɛmax⁡1≤i≤nuim-1.Letus=max⁡1≤i≤nui and ut=min⁡1≤i≤nui. By considering m≥3, we know that
(44)ρ(A~)utm-1=∑i2,…,im=1n‍(A+ɛJ)t,i2,…,imui2⋯uim≥utm-2max⁡2≤k≤m{∑i2,…,im=1︸exceptikn‍(A+ɛJ)t,i2,…,imuik}≥utm-2max⁡2≤k≤m{min⁡1≤ik≤n∑i2,…,im=1︸exceptikn‍(A+ɛJ)t,i2,…,im∑ik=1n‍uik}=utm-2max⁡2≤k≤m{min⁡1≤ik≤n∑i2,…,im=1︸exceptikn‍(A+ɛJ)t,i2,…,im}=utm-2(ɛnm-2+max⁡2≤k≤mmin⁡1≤ik≤n∑i2,…,im=1︸exceptikn‍at,i2,…,im);
that is, we have
(45)ρ(A~)ut≥ɛnm-2+max⁡2≤k≤mmin⁡1≤i1,ik≤n∑i2,…,im=1︸exceptikn‍ai1,i2,…,im
or
(46)1ut≤ρ(A~)ɛnm-2+max⁡2≤k≤mmin⁡1≤i1,ik≤n∑i2,…,im=1︸exceptiknai1,i2,…,im.
On the other hand,
(47)ρ(A~)usm-1=∑i2,…,im=1n‍(A+ɛJ)s,i2,…,imui2⋯uim≤∑i2,…,im=1n‍(A+ɛJ)s,i2,…,im≤ɛnm-1+∥A∥∞.
By putting (46) and (47) into (43), we have(48)ρ(A~)(1-ɛρ(A~)m-2(ɛnm-2+max⁡2≤k≤mmin⁡1≤i1,ik≤n∑i2,…,im=1︸exceptiknai1,i2,…,im)m-1)≤ρ(A)≤ρ(A~)(1-ɛɛnm-1+∥A∥∞).One may know ρ(A)=λ~+O(ɛ) if
(49)max⁡2≤k≤mmin⁡1≤i1,ik≤n∑i2,…,im=1︸exceptikn‍ai1,i2,…,im>0.
This shows that we can estimate ρ(A) of a nonnegative tensor A with a specified precision via the NQZ algorithm for the computation of ρ(A~).Remark 21.
Liu et al. [9] modified the NQZ algorithm for computing the spectral radius of A+ɛI, where A is an irreducible nonnegative tensor and ɛ is a very small number, and showed that the algorithm converges to ρ(A)+ɛ. This fact can be explained by our theoretical analysis in Theorem 7 by setting ΔA=ɛI. We just note that the left and right sides of the inequality in (15) are equal to ɛ; that is, ɛ≤ρ(A~)-ρ(A)≤ɛ. It implies that ρ(A~)=ρ(A)+ɛ. 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: a1,2,2=a1,3,3=a2,1,1=a3,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 2≈1.414213562373095; see [8]. In this example, we take the perturbation ΔA=ɛJ. We apply the NQZ algorithm to compute the spectral radius of A~ to approximate the actual one. According to Table 1, the results show that ρ(A) is about ρ(A~)+O(ɛ).Table 1
Numerical results for differentε  in Example 22.
ε
ρ
(
A
~
)
-
ε
min
⁡
1
≤
i
≤
n
u
i
m
-
1
ρ
(
A
~
)
-
ε
max
⁡
1
≤
i
≤
n
u
i
m
-
1
Difference
1
e
-
2
1.399817488643705
1.428757688931172
0.028940200287467
1
e
-
3
1.412729187546902
1.415699496853463
0.002970309306561
1
e
-
4
1.414064662464100
1.414362477963432
0.000297815499332
1
e
-
5
1.414198667753479
1.414228457171375
0.000029789417896
1
e
-
6
1.414212073004730
1.414215052025221
0.000002979020491Example 23.
We consider the following 3rd order 3-dimensional nonnegative tensor:a1,1,1=a1,2,2=a1,3,3=a2,1,1=a2,2,2=a2,3,3=a3,1,1=a3,2,2=a3,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 ΔA=ɛJ. The spectral radii of A~ by the NQZ algorithm are still accurate approximations of ρ(A): 3.090000000000000 (ɛ=0.01), 3.009000000000000 (ɛ=0.001), 3.000900000000000 (ɛ=0.0001), 3.000090000000001 (ɛ=0.00001), and 3.000009000000000 (ɛ=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 ρ(A) is about ρ(A~)+O(ɛ).Example 24.
Now we consider the following 3rd order 3-dimensional nonnegative tensor:a1,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]T is the corresponding eigenvector (the normalized in 2-norm). In this example, we take the perturbation ΔA=ɛJ. Although this tensor does not satisfy (49), the spectral radii of A~ by the NQZ algorithm are still accurate approximate of ρ(A): 1.015565072567277 (ɛ=0.01), 1.001139501996208 (ɛ=0.001), 1.000104123060726 (ɛ=0.0001), 1.000010127700654 (ɛ=0.00001), and 1.000001004012030 (ɛ=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 ɛ. 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 (ɛ=0.01), 0.077415571882820 (ɛ=0.001), 0.024493622285564 (ɛ=0.0001), 0.007745927468297 (ɛ=0.00001), and 0.002449488513126 (ɛ=0.000001). Thus the approximation is more accurate for the largest eigenvalue than for the associated eigenvector.


## 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.Chooseu(0)∈int⁡(P) and let v=A(u(0))m-1. For k=0,1,2,…, compute
(40)u(k)=(v(k))[1/(m-1)]∥(v(k))[1/(m-1)]∥;v(k+1)=A(u(k+1))m-1;λ_k+1=min⁡ui(k+1)>0vi(k+1)(ui(k+1))m-1;λ¯k+1=max⁡ui(k+1)>0vi(k+1)(ui(k+1))m-1.
It is shown in [10] that the sequences {λ_} and {λ¯} converge to some numbers λ_ and λ¯, respectively, and we have λ_≤ρ(A)≤λ¯. If λ_=λ¯, the gap is zero and therefore both the sequences {λ_} and {λ¯} converge to ρ(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.
Anmth-order n-dimensional tensor A is essentially positive if Aym-1∈int⁡(P) for any nonzero y∈P.Definition 20.
Anmth-order n-dimensional tensor A is called primitive if there exists a positive integer k such that Aky∈int⁡(P) for any nonzero y∈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 Theorem7 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 ΔA=ɛJ, where ɛ is a very small positive number and J is a tensor with all the entries being equal to one. It is clear that A~=A+ɛJ is essentially positive. Therefore, when we apply the NQZ algorithm to compute the largest eigenvalue of A~, it is convergent. Without loss of generality, we normalize the output vector u in the NQZ algorithm. In particular, the 1-norm of u is employed. The output of the algorithm contains a positive number λ~ and u>0 with ∥u∥1=1 (i.e., ∑i=1nui=1). We note that
(41)(ɛJDu-(m-1)×2Du×3⋯×mDuem-1)i1=∑i2,…,im=1n‍(ɛJ)i1,i2,…,imui2⋯uimui1m-1=ɛui1m-1∑i2,…,im=1n‍ui2⋯uim=ɛui1m-1.
Then, by Theorem 7, we have
(42)ɛmax⁡1≤i≤nuim-1≤ρ(A~)-ρ(A)≤ɛmin⁡1≤i≤nuim-1.
That is,
(43)ρ(A~)-ɛmin⁡1≤i≤nuim-1≤ρ(A)≤ρ(A~)-ɛmax⁡1≤i≤nuim-1.Letus=max⁡1≤i≤nui and ut=min⁡1≤i≤nui. By considering m≥3, we know that
(44)ρ(A~)utm-1=∑i2,…,im=1n‍(A+ɛJ)t,i2,…,imui2⋯uim≥utm-2max⁡2≤k≤m{∑i2,…,im=1︸exceptikn‍(A+ɛJ)t,i2,…,imuik}≥utm-2max⁡2≤k≤m{min⁡1≤ik≤n∑i2,…,im=1︸exceptikn‍(A+ɛJ)t,i2,…,im∑ik=1n‍uik}=utm-2max⁡2≤k≤m{min⁡1≤ik≤n∑i2,…,im=1︸exceptikn‍(A+ɛJ)t,i2,…,im}=utm-2(ɛnm-2+max⁡2≤k≤mmin⁡1≤ik≤n∑i2,…,im=1︸exceptikn‍at,i2,…,im);
that is, we have
(45)ρ(A~)ut≥ɛnm-2+max⁡2≤k≤mmin⁡1≤i1,ik≤n∑i2,…,im=1︸exceptikn‍ai1,i2,…,im
or
(46)1ut≤ρ(A~)ɛnm-2+max⁡2≤k≤mmin⁡1≤i1,ik≤n∑i2,…,im=1︸exceptiknai1,i2,…,im.
On the other hand,
(47)ρ(A~)usm-1=∑i2,…,im=1n‍(A+ɛJ)s,i2,…,imui2⋯uim≤∑i2,…,im=1n‍(A+ɛJ)s,i2,…,im≤ɛnm-1+∥A∥∞.
By putting (46) and (47) into (43), we have(48)ρ(A~)(1-ɛρ(A~)m-2(ɛnm-2+max⁡2≤k≤mmin⁡1≤i1,ik≤n∑i2,…,im=1︸exceptiknai1,i2,…,im)m-1)≤ρ(A)≤ρ(A~)(1-ɛɛnm-1+∥A∥∞).One may know ρ(A)=λ~+O(ɛ) if
(49)max⁡2≤k≤mmin⁡1≤i1,ik≤n∑i2,…,im=1︸exceptikn‍ai1,i2,…,im>0.
This shows that we can estimate ρ(A) of a nonnegative tensor A with a specified precision via the NQZ algorithm for the computation of ρ(A~).Remark 21.
Liu et al. [9] modified the NQZ algorithm for computing the spectral radius of A+ɛI, where A is an irreducible nonnegative tensor and ɛ is a very small number, and showed that the algorithm converges to ρ(A)+ɛ. This fact can be explained by our theoretical analysis in Theorem 7 by setting ΔA=ɛI. We just note that the left and right sides of the inequality in (15) are equal to ɛ; that is, ɛ≤ρ(A~)-ρ(A)≤ɛ. It implies that ρ(A~)=ρ(A)+ɛ. 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: a1,2,2=a1,3,3=a2,1,1=a3,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 2≈1.414213562373095; see [8]. In this example, we take the perturbation ΔA=ɛJ. We apply the NQZ algorithm to compute the spectral radius of A~ to approximate the actual one. According to Table 1, the results show that ρ(A) is about ρ(A~)+O(ɛ).Table 1
Numerical results for differentε  in Example 22.
ε
ρ
(
A
~
)
-
ε
min
⁡
1
≤
i
≤
n
u
i
m
-
1
ρ
(
A
~
)
-
ε
max
⁡
1
≤
i
≤
n
u
i
m
-
1
Difference
1
e
-
2
1.399817488643705
1.428757688931172
0.028940200287467
1
e
-
3
1.412729187546902
1.415699496853463
0.002970309306561
1
e
-
4
1.414064662464100
1.414362477963432
0.000297815499332
1
e
-
5
1.414198667753479
1.414228457171375
0.000029789417896
1
e
-
6
1.414212073004730
1.414215052025221
0.000002979020491Example 23.
We consider the following 3rd order 3-dimensional nonnegative tensor:a1,1,1=a1,2,2=a1,3,3=a2,1,1=a2,2,2=a2,3,3=a3,1,1=a3,2,2=a3,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 ΔA=ɛJ. The spectral radii of A~ by the NQZ algorithm are still accurate approximations of ρ(A): 3.090000000000000 (ɛ=0.01), 3.009000000000000 (ɛ=0.001), 3.000900000000000 (ɛ=0.0001), 3.000090000000001 (ɛ=0.00001), and 3.000009000000000 (ɛ=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 ρ(A) is about ρ(A~)+O(ɛ).Example 24.
Now we consider the following 3rd order 3-dimensional nonnegative tensor:a1,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]T is the corresponding eigenvector (the normalized in 2-norm). In this example, we take the perturbation ΔA=ɛJ. Although this tensor does not satisfy (49), the spectral radii of A~ by the NQZ algorithm are still accurate approximate of ρ(A): 1.015565072567277 (ɛ=0.01), 1.001139501996208 (ɛ=0.001), 1.000104123060726 (ɛ=0.0001), 1.000010127700654 (ɛ=0.00001), and 1.000001004012030 (ɛ=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 ɛ. 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 (ɛ=0.01), 0.077415571882820 (ɛ=0.001), 0.024493622285564 (ɛ=0.0001), 0.007745927468297 (ɛ=0.00001), and 0.002449488513126 (ɛ=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ΔA and obtain its smallest error bound of ΔA such that
(50)A~x~m-1=(A+ΔA)x~m-1=λ~x~[m-1],
where A and A~=A+ΔA are irreducible nonnegative tensors with ΔA=(δai1,i2,…,im) for 1≤i1,i2,…,im≤n, λ~ is the largest eigenvalue of A~, and x~ is a Perron vector of A~. The backward error for the eigenpair is defined as follows:
(51)η(x~)=min⁡ΔA∈Ω∥ΔA∥F,
where
(52)Ω={ΔAisanonnegativetensorsuchthatiA+ΔAisirreducibleΔAisanonnegativetensorsuchthatΔA}
and ∥ΔA∥F:=∑i1,…,im=1nδai1,…,im2.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.
LetU∈Cp×q, V∈Cr×s, and W∈Cp×s. Let
(53)X={X∈Cp×s:UXV=W},Y={U†WV†+Y-PU*YPV}.
Then
(54)PUWPV*=W
if and only if X≠∅, and when Y≠∅, X=Y, where ·* denotes the conjugate transpose of a matrix, U† is the Moore-Penrose generalized inverse of U, PU=UU†, and PV*=V†V.Now we show the main result of this section.Theorem 26.
SupposeA is an mth-order n-dimensional irreducible nonnegative tensor. Let λ¯ and u be the output of the NQZ algorithm (stated in Section 2.1) applied to A, and r=λ¯u[m-1]-Aum-1. Then the backward error for λ¯ and u of the perturbed irreducible nonnegative tensor A+ΔA is given by
(55)η(u)=∥r∥2∥u∥2m-1
and ΔA can be chosen as follows:
(56)δai1,i2,…,im=(r)i1·(u)i2⋯(u)im∥u∥22(m-1).Proof.
We note that(57)ΔAum-1=λ¯u[m-1]-Aum-1=r.
In order to analyze u, we rewrite the above equation into a linear system as follows:
(58)ΔAb=ΔA(u⊗⋯⊗u︷m-1)=r,
where ΔA is an n-by-nm-1 matrix with its entries given by
(59)(ΔA)i1,j=δai1,i2,…,imwithj=i2×⋯×im,1≤i1,i2,…,im≤n.
It follows from Lemma 25 that
(60)ΔA=rb†+Z(I-bb†),
where b† is an 1-by-nm-1 vector given by b/∥b∥2 and Z is an n-by-nm-1 matrix. Therefore, we obtain
(61)∥ΔA∥F2=∥rb†∥F2+∥Z(I-bb†)∥F2.
The minimization of ∥ΔA∥F2 is equivalent to finding a matrix Z such that ∥rb†∥F2+∥Z(I-bb†)∥F2 can be minimized. It is clear that we choose Z=0; that is, min⁡∥ΔA∥F2=∥rb†∥F2.
According to the NQZ algorithm stated in Section2.1, we know that r is nonnegative. As u is positive, both b and b† are also positive. Let us consider two cases. We note that if r is a zero vector, then λ¯ 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 ΔA=rb† must be positive. It can be shown that A~ is irreducible. The argument is that for any nonempty proper index subset J⊂{1,2,…,n} such that
(62)ai1,i2,…,im+δi1,i2,…,im>0,∀i1∈J,∀i2,…,im∉J.
Hence the result follows.Remark 27.
Whenm=2, the results of the backward error are reduced to the results in Theorem 6.3.2 in [14]; that is,
(63)η(x~)=∥rx~†∥F.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 tensorA, 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.Table 2
The backward errors for different cases.
m
n
Backward errorη(x~)
3
5
1.2297
e
-
15
3
10
5.5960
e
-
15
3
20
1.5579
e
-
14
3
40
5.9253
e
-
14
4
5
9.9174
e
-
15
4
10
6.4772
e
-
14
4
20
4.3210
e
-
13
4
40
2.9931
e
-
12


## 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Δ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.



---

*Source: 109525-2014-09-28.xml*