{
  "id": "2311.07035",
  "version": "v1",
  "published": "2023-11-13T02:36:41.000Z",
  "updated": "2023-11-13T02:36:41.000Z",
  "title": "ContHutch++: Stochastic trace estimation for implicit integral operators",
  "authors": [
    "Jennifer Zvonek",
    "Andrew Horning",
    "Alex Townsend"
  ],
  "categories": [
    "math.NA",
    "cs.NA"
  ],
  "abstract": "Hutchinson's estimator is a randomized algorithm that computes an $\\epsilon$-approximation to the trace of any positive semidefinite matrix using $\\mathcal{O}(1/\\epsilon^2)$ matrix-vector products. An improvement of Hutchinson's estimator, known as Hutch++, only requires $\\mathcal{O}(1/\\epsilon)$ matrix-vector products. In this paper, we propose a generalization of Hutch++, which we call ContHutch++, that uses operator-function products to efficiently estimate the trace of any trace-class integral operator. Our ContHutch++ estimates avoid spectral artifacts introduced by discretization and are accompanied by rigorous high-probability error bounds. We use ContHutch++ to derive a new high-order accurate algorithm for quantum density-of-states and also show how it can estimate electromagnetic fields induced by incoherent sources.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-11-13T02:36:41.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "stochastic trace estimation",
      "implicit integral operators",
      "estimates avoid spectral artifacts",
      "hutchinsons estimator",
      "matrix-vector products"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}