Volume 53, pp. 1-27, 2020.

Shifted and extrapolated power methods for tensor $\ell^p$-eigenpairs

Stefano Cipolla, Michela Redivo-Zaglia, and Francesco Tudisco

Abstract

This work is concerned with the computation of $\ell^p$-eigenvalues and eigenvectors of square tensors with $d$ modes. In the first part we propose two possible shifted variants of the popular (higher-order) power method, and, when the tensor is entry-wise nonnegative with a possibly reducible pattern and $p$ is strictly larger than the number of modes, we prove convergence of both schemes to the Perron $\ell^p$-eigenvector and to the maximal corresponding $\ell^p$-eigenvalue of the tensor. Then, in the second part, motivated by the slow rate of convergence that the proposed methods achieve for certain real-world tensors when $p\approx d$, the number of modes, we introduce an extrapolation framework based on the simplified topological $\varepsilon$-algorithm to efficiently accelerate the shifted power sequences. Numerical results for synthetic and real world problems show the improvements gained by the introduction of the shifting parameter and the efficiency of the acceleration technique.

Full Text (PDF) [892 KB], BibTeX

Key words

$\ell^p$-eigenvalues, tensors, shifted higher-order power method, extrapolation methods, Shanks transformations, $\varepsilon$-algorithms

AMS subject classifications

15A69, 15A18, 65B05, 65B10, 65B99, 65F15

< Back