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

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 for the computation of $\ell^p$-eigenpairs proving the convergence of both the schemes to the Perron $\ell^p$-eigenvector of the tensor, and the maximal corresponding $\ell^p$-eigenvalue, when the tensor is entrywise nonnegative and $p$ is strictly larger than the number of modes. Then, 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, in the second part we introduce an extrapolation framework based on the simplified topological $\varepsilon$-algorithm to efficiently accelerate the shifted power sequences. Numerical results on synthetic and real world problems show the improvements gained by the introduction of the shifting parameter and the efficiency of the acceleration technique.

Please cite this work as:

@article{cipolla2019shifted,
  title = {Shifted and extrapolated power methods for tensor $\ell^p$-eigenpairs},
  author = {Cipolla, Stefano and Redivo-Zaglia, Michela and Tudisco, Francesco},
  journal = {ETNA: Electronic Transactions on Numerical Analysis},
  volume = {53},
  pages = {1--27},
  year = {2020}
}

Keywords: nonnegative tensors tensor eigenvectors extrapolation power method