Linear Convergence Analysis Of An Algorithm For Computing The Dominant Eigenvalue Of An Essentially Nonnegative Tensor

2005, Qi first propose the theory of tensor eigenvalue problem. Tensor andeigenvalue problems, have wide applications in industry, natural science, informationscience, statistics, software design, data mining, image and signal processing,computational biology, demography, etc. Therefore, they are drawing more and moreresearchers’ attentions. Nonnegative tensor and its largest eigenvalue problem, with itsintrinsic properties, have found applications in multilinear pagerank, spectralhypergraph theory, as well as higher-order Markov chains, etc. Moreover, in general,the eigenvalue problem of a general tensor is NP-hard, while it has been shown that thelargest eigenvalue problem of a nonnegative tensor has linearly convergent algorithms.Recently, a lot of research has focused on algorithms and convergence of the eigenvalueproblems of nonnegative tensors.In2009, Ng, Qi and Zhou proposed an iterative method to find the largesteigenvalue of an irreducible nonnegative tensor (NQZ method, for short). In2011,Zhang and Qi proposed an iterative method, which is actually the NQZ method with aspecified starting point, and established an explicit linear convergence rate of the NQZmethod for essentially positive tensors. In2012, Zhang, Qi and Luo introduced theconcept of essentially nonnegative tensors and its dominant eigenvalue. In this paper,we focus on the algorithm and convergence of the dominant eigenvalue problem.In this paper, we propose an algorithm for computing the dominant eigenvalue foressentially nonnegative tensors and we show that the linear convergence rate of theproposed algorithm holds for any essentially nonnegative tensor. Numerical results aregiven to demonstrate the linear convergence.Our major distributions are as follows,1. We introduce a perturbation sector to construct the iterative tensor, whichin turn attributes to an algorithm suitable for any essentially nonnegative tensor;2. We prove that our algorithm is convergent for any essentially nonnegativetensor, and show that, when the perturbation sector tends to zero, the iterativeresult of our algorithm also converges;3. We show that the explicit linear convergence holds for any essentially nonnegative tensor, and we give an estimate on the number of iterations.