Estimating the trace of matrix functions with application to complex networks

The approximation of trace(f(Ω)), where f is a function of a symmetric matrix Ω, can be challenging when Ω is exceedingly large. In such a case even the partial Lanczos decomposition of Ω is computationally demanding and the stochastic method investigated by Bai et al. (J. Comput. Appl. Math. 74:71–89, 1996) is preferred. Moreover, in the last years, a partial global Lanczos method has been shown to reduce CPU time with respect to partial Lanczos decomposition. In this paper we review these techniques, treating them under the unifying theory of measure theory and Gaussian integration. This allows generalizing the stochastic approach, proposing a block version that collects a set of random vectors in a rectangular matrix, in a similar fashion to the partial global Lanczos method. We show that the results of this technique converge quickly to the same approximation provided by Bai et al. (J. Comput. Appl. Math. 74:71–89, 1996), while the block approach can leverage the same computational advantages as the partial global Lanczos. Numerical results for the computation of the Von Neumann entropy of complex networks prove the robustness and efficiency of the proposed block stochastic method.