The Global Convergence of the Nonlinear Power Method for Mixed-Subordinate Matrix Norms

Abstract

We analyze the global convergence of the power iterates for the computation of a general mixed-subordinate matrix norm. We prove a new global convergence theorem for a class of entrywise nonnegative matrices that generalizes and improves a well-known results for mixed-subordinate $\ell^p$ matrix norms. In particular, exploiting the Birkoff–Hopf contraction ratio of nonnegative matrices, we obtain novel and explicit global convergence guarantees for a range of matrix norms whose computation has been recently proven to be NP-hard in the general case, including the case of mixed-subordinate norms induced by the vector norms made by the sum of different $\ell^p$-norms of subsets of entries. Finally, we use the new results combined with hypercontractive inequalities to prove a new lower bound on the logarithmic Sobolev constant of a Markov chain.

Please cite this paper as:

@article{gautier2021global,
  title={The Global Convergence of the Nonlinear Power Method for Mixed-Subordinate Matrix Norms},
  author={Gautier, Antoine and Hein, Matthias and Tudisco, Francesco},
  journal={Journal of Scientific Computing},
  volume={88},
  number={1},
  pages={1--28},
  year={2021},
  publisher={Springer}
}

Keywords: Perron-Frobenius theory nonlinear eigenvalues Matrix norms power method Markov chain