Linear convergence of an algorithm for largest singular value of a nonnegative rectangular tensor

An algorithm for finding the largest singular value of a nonnegative rectangular tensor was recently proposed by Chang, Qi, and Zhou [J. Math. Anal. Appl., 2010, 370: 284–294]. In this paper, we establish a linear convergence rate of the Chang-Qi-Zhou algorithm under a reasonable assumption.     

Singular values of nonnegative rectangular tensors

The real rectangular tensors arise from the strong ellipticity condition problem in solid mechanics and the entanglement problem in quantum physics. Some properties concerning the singular values of a real rectangular tensor were discussed by K. C. Chang et al. [J. Math. Anal. Appl., 2010, 370: 284–294]. In this paper, we give some new results on the Perron-Frobenius Theorem for nonnegative rectangular tensors. We show that the weak Perron-Frobenius keeps valid and the largest singular value is really geometrically simple under some conditions. In addition, we establish the convergence of an algorithm proposed by K. C. Chang et al. for finding the largest singular value of nonnegative primitive rectangular tensors.     

Linear convergence of an algorithm for computing the largest eigenvalue of a nonnegative tensor

An iterative method for finding the largest eigenvalue of a nonnegative tensor was proposed by Ng, Qi, and Zhou in 2009. In this paper, we establish an explicit linear convergence rate of the Ng–Qi–Zhou method for essentially positive tensors. Numerical results are given to demonstrate linear convergence of the Ng–Qi–Zhou algorithm for essentially positive tensors. Copyright © 2011 John Wiley & Sons, Ltd.     

Singular value inclusion sets for rectangular tensors

Two singular value inclusion sets for rectangular tensors are given. These sets provide two upper bounds and lower bounds for the largest singular value of nonnegative rectangular tensors, which can be taken as a parameter of an algorithm presented by Zhou et al. (Linear Algebra Appl. 2013; 438: 959–968) such that the sequences produced by this algorithm converge rapidly to the largest singular value of an irreducible nonnegative rectangular tensor.     

Singular values of a real rectangular tensor

Real rectangular tensors arise from the strong ellipticity condition problem in solid mechanics and the entanglement problem in quantum physics. In this paper, we systematically study properties of singular values of a real rectangular tensor, and give an algorithm to find the largest singular value of a nonnegative rectangular tensor. Numerical results show that the algorithm is efficient.     

Standard tensor and its applications in problem of singular values of tensors

In this paper, first we give the definition of standard tensor. Then we clarify the relationship between weakly irreducible tensors and weakly irreducible polynomial maps by the definition of standard tensor. And we prove that the singular values of rectangular tensors are the special cases of the eigen-values of standard tensors related to rectangular tensors. Based on standard tensor, we present a generalized version of the weak Perron-Frobenius Theorem of nonnegative rectangular tensors under weaker conditions. Furthermore, by studying standard tensors, we get some new results of rectangular tensors. Besides, by using the special structure of standard tensors corresponding to nonnegative rectangular tensors, we show that the largest singular value is really geometrically simple under some weaker conditions.     

Exact solution to a parametric linear programming problem

In this paper, we present a cubically convergent method for finding the largest eigenvalue of a nonnegative irreducible tensor. A cubically convergent method is used to solve an equivalent system of nonlinear equations which is transformed by the tensor eigenvalue problem. Due to particular structure of tensor, Chebyshev’s direction is added to the method with a few extra computation. Two rules are designed such that the descendant property of the search directions is ensured. The global convergence is proved by using the line search technique. Numerical results indicate that the proposed method is competitive and efficient on some test problems.     

Strictly nonnegative tensors and nonnegative tensor partition

We introduce a new class of nonnegative tensors—strictly nonnegative tensors.A weakly irreducible nonnegative tensor is a strictly nonnegative tensor but not vice versa.We show that the spectral radius of a strictly nonnegative tensor is always positive.We give some necessary and su?cient conditions for the six wellconditional classes of nonnegative tensors,introduced in the literature,and a full relationship picture about strictly nonnegative tensors with these six classes of nonnegative tensors.We then establish global R-linear convergence of a power method for finding the spectral radius of a nonnegative tensor under the condition of weak irreducibility.We show that for a nonnegative tensor T,there always exists a partition of the index set such that every tensor induced by the partition is weakly irreducible;and the spectral radius of T can be obtained from those spectral radii of the induced tensors.In this way,we develop a convergent algorithm for finding the spectral radius of a general nonnegative tensor without any additional assumption.Some preliminary numerical results show the feasibility and effectiveness of the algorithm.     

An always convergent algorithm for the largest eigenvalue of an irreducible nonnegative tensor

In this paper we propose an iterative method to calculate the largest eigenvalue of a nonnegative tensor. We prove this method converges for any irreducible nonnegative tensor. We also apply this method to study the positive definiteness of a multivariate form.     

Finding the Maximum Eigenvalue of Essentially Nonnegative Symmetric Tensors via Sum of Squares Programming

Finding the maximum eigenvalue of a tensor is an important topic in tensor computation and multilinear algebra. Recently, for a tensor with nonnegative entries (which we refer it as a nonnegative tensor), efficient numerical schemes have been proposed to calculate its maximum eigenvalue based on a Perron–Frobenius-type theorem. In this paper, we consider a new class of tensors called essentially nonnegative tensors, which extends the concept of nonnegative tensors, and examine the maximum eigenvalue of an essentially nonnegative tensor using the polynomial optimization techniques. We first establish that finding the maximum eigenvalue of an essentially nonnegative symmetric tensor is equivalent to solving a sum of squares of polynomials (SOS) optimization problem, which, in its turn, can be equivalently rewritten as a semi-definite programming problem. Then, using this sum of squares programming problem, we also provide upper and lower estimates for the maximum eigenvalue of general symmetric tensors. These upper and lower estimates can be calculated in terms of the entries of the tensor. Numerical examples are also presented to illustrate the significance of the results.     

一类半正奇异Sturm-Liouville边值问题的正解

本文讨论了一类半正奇异Sturm-Liouville边值问题正解的存在性,其中非线性项f(t,u)关于t=0,1和u=0奇异.在非线性项可取负值且下方无界的情形下,利用不动点指数理论以及线性算子的特征值理论得到了该问题正解存在性结果.     

Magic square spectra

To study the eigenvalues of low order singular and non-singular magic squares we begin with some aspects of general square matrices. Additional properties follow for general semimagic squares (same row and column sums), with further properties for general magic squares (semimagic with same diagonal sums). Parameterizations of general magic squares for low orders are examined, including factorization of the linesum eigenvalue from the characteristic polynomial.For nth order natural magic squares with matrix elements 1,…,n² we find examples of some remarkably singular cases. All cases of the regular (or associative, or symmetric) type (antipodal pair sum of 1+n²) with n-1 zero eigenvalues have been found in the only complete sets of these squares (in fourth and fifth order). Both the Jordan form and singular value decomposition (SVD) have been useful in this study which examines examples up to 8th order.In fourth order these give examples illustrating a theorem by Mattingly that even order regular magic squares have a zero eigenvalue with odd algebraic multiplicity, m. We find 8 cases with m=3 which have a non-diagonal Jordan form. The regular group of 48 squares is completed by 40 squares with m=1, which are diagonable. A surprise finding is that the eigenvalues of 16 fourth order pandiagonal magic squares alternate between m=1, diagonable, and m=3, non-diagonable, on rotation by π/2. Two 8th order natural magic squares, one regular and the other pandiagonal, are also examined, found to have m=5, and to be diagonable.Mattingly also proved that odd order regular magic squares have a zero eigenvalue with even multiplicity, m=0,2,4,... Analyzing results for natural fifth order magic squares from exact backtracking calculations we find 652 with m=2, and four with m=4. There are also 20, 604 singular seventh order natural ultramagic (simultaneously regular and pandiagonal) squares with m=2, demonstrating that the co-existence of regularity and pandiagonality permits singularity. The singular odd order examples studied are all non-diagonable.     

<Emphasis Type="Italic">l</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis>,<Emphasis Type="Italic">s</Emphasis></Superscript>-Singular values and spectral radius of partially symmetric rectangular tensors

The real rectangular tensors arise from the strong ellipticity condition problem in solid mechanics and the entanglement problem in quantum physics. In this paper, we first study properties of l ^k,s -singular values of real rectangular tensors. Then, a necessary and sufficient condition for the positive definiteness of partially symmetric rectangular tensors is given. Furthermore, we show that the weak Perron-Frobenius theorem for nonnegative partially symmetric rectangular tensor keeps valid under some new conditions and we prove a maximum property for the largest l ^k,s -singular values of nonnegative partially symmetric rectangular tensor. Finally, we prove that the largest l ^k,s -singular value of nonnegative weakly irreducible partially symmetric rectangular tensor is still geometrically simple.     

张量分析和多项式优化的若干进展

张量分析 (也称多重数值线性代数) 主要包括张量分解和张量特征值的理论和算法,多项式优化主要包括目标和约束均为多项式的一类优化问题的理论和算法. 主要介绍这两个研究领域中若干新的研究结果. 对张量分析部分,主要介绍非负张量H-特征值谱半径的一些性质及求解方法,还介绍非负张量最大 (小) Z-特征值的优化表示及其解法;对多项式优化部分,主要介绍带单位球约束或离散二分单位取值、目标函数为齐次多项式的优化问题及其推广形式的多项式优化问题和半定松弛解法. 最后对所介绍领域的发展趋势做了预测和展望.     

Solving inverse eigenvalue problems via Householder and rank-one matrices

A brief and practical algorithm is introduced to solve symmetric inverse eigenvalue problems, which we call HROU algorithm. The algorithm is based on Householder transformations and rank one updating. We give some basic properties and the computational amount and develop sensitivity analysis of HROU algorithm. Furthermore, we develop HROU algorithm into a multi-level and adaptive one, named MLAHROU, to solve symmetric nonnegative inverse eigenvalue problems. New sufficient conditions to ensure symmetric nonnegative matrices and symmetric M-matrices are given. Many numerical examples are given to verify our theory, compare with existing results and show the efficiency of our algorithms.     

On the quadratic two-parameter eigenvalue problem and its linearization

We introduce the quadratic two-parameter eigenvalue problem and linearize it as a singular two-parameter eigenvalue problem. This, together with an example from model updating, shows the need for numerical methods for singular two-parameter eigenvalue problems and for a better understanding of such problems.There are various numerical methods for two-parameter eigenvalue problems, but only few for nonsingular ones. We present a method that can be applied to singular two-parameter eigenvalue problems including the linearization of the quadratic two-parameter eigenvalue problem. It is based on the staircase algorithm for the extraction of the common regular part of two singular matrix pencils.     

Efficient algorithms for computing the largest eigenvalue of a nonnegative tensor

Consider the problem of computing the largest eigenvalue for nonnegative tensors. In this paper, we establish the Q-linear convergence of a power type algorithm for this problem under a weak irreducibility condition. Moreover, we present a convergent algorithm for calculating the largest eigenvalue for any nonnegative tensors.     

Backward errors for eigenvalue and singular value decompositions

Summary. We present bounds on the backward errors for the symmetric eigenvalue decomposition and the singular value decomposition in the two-norm and in the Frobenius norm. Through different orthogonal decompositions of the computed eigenvectors we can define different symmetric backward errors for the eigenvalue decomposition. When the computed eigenvectors have a small residual and are close to orthonormal then all backward errors tend to be small. Consequently it does not matter how exactly a backward error is defined and how exactly residual and deviation from orthogonality are measured. Analogous results hold for the singular vectors. We indicate the effect of our error bounds on implementations for eigenvector and singular vector computation. In a more general context we prove that the distance of an appropriately scaled matrix to its orthogonal QR factor is not much larger than its distance to the closest orthogonal matrix. Received July 19, 1993     

A backward error for the inverse singular value problem

A backward error for inverse singular value problems with respect to an approximate solution is defined, and an explicit expression for the backward error is derived by extending the approach described in [J.G. Sun, Backward errors for the inverse eigenvalue problem, Numer. Math. 82 (1999) 339-349]. The expression may be useful for testing the stability of practical algorithms.     

Existence and uniqueness of splittings for stationary iterative methods with applications to alternating methods

Summary. Given a nonsingular matrix , and a matrix of the same order, under certain very mild conditions, there is a unique splitting , such that . Moreover, all properties of the splitting are derived directly from the iteration matrix . These results do not hold when the matrix is singular. In this case, given a matrix and a splitting such that , there are infinitely many other splittings corresponding to the same matrices and , and different splittings can have different properties. For instance, when is nonnegative, some of these splittings can be regular splittings, while others can be only weak splittings. Analogous results hold in the symmetric positive semidefinite case. Given a singular matrix , not for all iteration matrices there is a splitting corresponding to them. Necessary and sufficient conditions for the existence of such splittings are examined. As an illustration of the theory developed, the convergence of certain alternating iterations is analyzed. Different cases where the matrix is monotone, singular, and positive (semi)definite are studied. Received September 5, 1995 / Revised version received April 3, 1996