揭示矩阵函数迹估计的理论下界，明确高效算法的极限。
Lower bounds for trace estimation via Block Krylov and other methods
- 基于块克雷洛夫子空间与哈钦森法结合，通过多项式逼近实现迹估计。
- 证明对Wishart矩阵的迹估计至少需特定次数查询，给出理论下限。
- 揭示算法步数与多项式阶数的关系，为高效设计提供理论指导。
本文研究估计矩阵函数迹 $ ext{tr}(f(A))$ 的理论下界，聚焦于结合哈钦森法与块克雷洛夫技术的方法。这些方法通过块克雷洛夫子空间近似矩阵-向量乘积 $f(A)V$，本质上等价于多项式逼近。我们通过分析标量情形下的多项式逼近上界，推导出对 $A^{-1/2}$ 与 $A^{-1}$ 等函数所需克雷洛夫步数的上界。此外，针对 Wishart 矩阵 $W$，我们建立了 $ ext{tr}(W^{-p})$ 迹估计所需的最少查询次数下界。研究阐明了块克雷洛夫方法步数与多项式逼近阶数之间的联系，将迹估计的总代价与多项式逼近的基本限制及计算所需信息量相联系。
原文摘要 · Abstract (English)
This paper studies theoretical lower bounds for estimating the trace of a matrix function, $\text{tr}(f(A))$, focusing on methods that use Hutchinson's method along with Block Krylov techniques. These methods work by approximating matrix-vector products like $f(A)V$ using a Block Krylov subspace. This is closely related to approximating functions with polynomials. We derive theoretical upper bounds on how many Krylov steps are needed for functions such as $A^{-1/2}$ and $A^{-1}$ by analyzing the upper bounds from the polynomial approximation of their scalar equivalent. In addition, we also develop lower limits on the number of queries needed for trace estimation, specifically for $\text{tr}(W^{-p})$ where $W$ is a Wishart matrix. Our study clarifies the connection between the number of steps in Block Krylov methods and the degree of the polynomial used for approximation. This links the total cost of trace estimation to basic limits in polynomial approximation and how much information is needed for the computation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。