Fast estimation of tr(f(A)) via stochastic Lanczos quadrature

Shashanka Ubaru, Jie Chen, Yousef Saad

Research output: Contribution to journalArticlepeer-review

89 Scopus citations

Abstract

The problem of estimating the trace of matrix functions appears in applications ranging from machine learning and scientific computing, to computational biology. This paper presents an inexpensive method to estimate the trace of f(A) for cases where f is analytic inside a closed interval and A is a symmetric positive definite matrix. The method combines three key ingredients, namely, the stochastic trace estimator, Gaussian quadrature, and the Lanczos algorithm. As examples, we consider the problems of estimating the log-determinant (f(t) = log(t)), the Schatten p-norms (f(t) = tp/2), the Estrada index (f(t) = et), and the trace of the matrix inverse (f(t) = t-1). We establish multiplicative and additive error bounds for the approximations obtained by this method. In addition, we present error bounds for other useful tools such as approximating the log-likelihood function in the context of maximum likelihood estimation of Gaussian processes. Numerical experiments illustrate the performance of the proposed method on di erent problems arising from various applications.

Original languageEnglish (US)
Pages (from-to)1075-1099
Number of pages25
JournalSIAM Journal on Matrix Analysis and Applications
Volume38
Issue number4
DOIs
StatePublished - 2017

Bibliographical note

Funding Information:
The work of the first and third authors was supported by NSF under grant NSF/CCF- 1318597. The second author's work was supported in part by the XDATA program of the Defense Advanced Research Projects Agency (DARPA), administered through Air Force Research Laboratory contract FA8750-12-C-0323.

Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics.

Keywords

  • Fast approximate algo-rithms
  • Gaussian processes
  • Lanczos algorithm
  • Log-determinants
  • Schatten norms
  • Trace estimation

Fingerprint

Dive into the research topics of 'Fast estimation of tr(f(A)) via stochastic Lanczos quadrature'. Together they form a unique fingerprint.

Cite this