hutch

trace.hutch(
    A,
    batch=32,
    pdf='rademacher',
    converge='default',
    seed=None,
    full=False,
    callback=None,
    **kwargs,
)

Estimates the trace of a symmetric A via the Girard-Hutchinson estimator.

This function uses random vectors to estimate of the trace of A via the approximation: \mathrm{tr}(A) = \sum_{i=1}^n e_i^T A e_i \approx n^{-1}\sum_{i=1}^n v^T A v When v are isotropic, this approximation forms an unbiased estimator of the trace.

Note

Convergence behavior is controlled by the estimator parameter: “confidence” uses the central limit theorem to generate confidence intervals on the fly, which may be used in conjunction with atol and rtol to upper-bound the error of the approximation.

Parameters

Name Type Description Default
A Union[LinearOperator, np.ndarray] real symmetric matrix or linear operator. required
batch int Number of random vectors to sample at a time for batched matrix multiplication. 32
pdf Union[str, Callable] Choice of zero-centered distribution to sample random vectors from. 'rademacher'
converge Union[str, ConvergenceCriterion] Convergence criterion to test for estimator convergence. See details. 'default'
seed Union[int, np.random.Generator, None] Seed to initialize the rng entropy source. Set seed > -1 for reproducibility. None
full bool Whether to return additional information about the computation. False
callback Optional[Callable] Optional callable to execute after each batch of samples. None
**kwargs dict Additional keyword arguments to parameterize the convergence criterion. {}

Returns

Name Type Description
Union[float, tuple] Estimate the trace of f(A). If info = True, additional information about the computation is also returned.

See Also

  • lanczos: the lanczos tridiagonalization algorithm.
  • MeanEstimator: Standard estimator of the mean from iid samples.
  • ConfidenceCriterion: Criterion for convergence that uses the central limit theorem.

Reference

  1. Ubaru, S., Chen, J., & Saad, Y. (2017). Fast estimation of tr(f(A)) via stochastic Lanczos quadrature. SIAM Journal on Matrix Analysis and Applications, 38(4), 1075-1099.
  2. Hutchinson, Michael F. “A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines.” Communications in Statistics-Simulation and Computation 18.3 (1989): 1059-1076.

Examples

from primate.trace import hutch