Bounding matrix functionals via partial global block Lanczos decomposition

Approximations of expressions of the form If:=trace(WTf(A)W)If:=trace(WTf(A)W), where A∈Rm×mA∈Rm×m is a large symmetric matrix, W∈Rm×kW∈Rm×k with k≪mk≪m, and f   is a function, can be computed without evaluating f(A)f(A) by applying a few steps of the global block Lanczos method to A with initial block-vector W. This yields a partial global Lanczos decomposition of A. We show that for suitable functions f   upper and lower bounds for IfIf can be determined by exploiting the connection between the global block Lanczos method and Gauss-type quadrature rules. Our approach generalizes techniques advocated by Golub and Meurant for the standard Lanczos method (with block size one) to the global block Lanczos method. We describe applications to the computation of upper and lower bounds of the trace of f(A)f(A) and consider, in particular, the computation of upper and lower bounds for the Estrada index, which arises in network analysis. We also discuss an application to machine learning.