论文标题
计算非负矩阵的规范和马尔可夫链的log-sobolev常数
Computing the norm of nonnegative matrices and the log-Sobolev constant of Markov chains
论文作者
论文摘要
我们分析了为一般混合辅助矩阵标准计算的功率迭代的全局收敛性。我们证明了一种新的全球融合定理，用于一类入口的非负矩阵，该矩阵概括并改善了混合辅助$ \ ell^p $矩阵规范的众所周知的结果。特别是，利用非负矩阵的Birkoff-Hopf收缩率，我们为一系列矩阵规范获得了新颖而明确的全球收敛保证，这些规范最近已证明其计算在一般情况下已被证明是NP-HARD，包括由不同$ \ ell $ \ ell^p $ \ ell^p $ hears ofters of verties of的混合辅助规范的案例。最后，我们使用新的结果与超额收缩不平等相结合，证明了马尔可夫链的对数Sobolev常数的新下限。
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.
