Improved bounds on sample size for implicit matrix trace estimators

Farbod Roosta-Khorasani, Uri M. AscherFound. Comput. Math 2013 · DOI · OpenReview

TL;DR

This paper refines theoretical bounds on the number of samples needed for accurate estimation of the trace of large, implicitly defined matrices using Monte Carlo methods. The authors introduce new, tighter bounds for Hutchinson and Gaussian estimators, and provide matrix-dependent bounds that offer insights into which estimation method is best suited for different matrix structures.

What Problem Does This Paper Address?

Estimating the trace of a large matrix (sum of its diagonal elements) is crucial in many scientific and engineering applications. When the matrix is "implicit," meaning we can only compute matrix-vector products (Aw) but not access its elements directly, Monte Carlo methods are often employed. These methods approximate the trace by averaging results from random vector probes. A key challenge is determining the minimum number of probes (sample size, N) required to achieve a desired accuracy with a certain probability. Previous work by Avron and Toledo (2011) provided bounds, but these were sometimes overly conservative or lacked insight into how matrix properties affect estimator performance. This paper aims to improve these bounds, making them tighter and more informative about method suitability.

Methods

The paper focuses on three main Monte Carlo trace estimation methods:

  • Hutchinson Estimator: Uses Rademacher random vectors (components are +1 or -1 with equal probability). The authors improve existing bounds by removing a term related to the matrix rank, making the bound more general and comparable to the Gaussian estimator. They also derive a new matrix-dependent bound that sheds light on when this method is efficient.
  • Gaussian Estimator: Uses standard normal random vectors. The paper provides a tighter sufficient bound and a new, practically useful necessary bound that depends on matrix properties. This matrix-dependent bound helps identify when the Gaussian estimator might be inefficient.
  • Uniform Unit Vector Estimator: Uses random unit vectors. The authors analyze both sampling with and without replacement, deriving bounds and showing that sampling without replacement can offer a smaller variance.

The core mathematical tools involve probability inequalities (like Markov's and Hoeffding's), Chernoff-like analysis, and properties of eigenvalues and matrix norms.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments with synthetically generated matrices.

Key Insights and Ideas

  • Rank-Independent Bounds: The authors successfully remove the matrix rank from the general bounds for the Hutchinson estimator, simplifying and improving them. This suggests that the rank might not be as critical as previously thought for these general bounds.
  • Matrix-Dependent Insights: The introduction of matrix-dependent bounds (using quantities like $K_H$, $K_G$, and $K_U$) is a significant contribution. These bounds reveal that the "best" estimator is not universal; it depends on the matrix's structure (e.g., eigenvalue distribution, distribution of off-diagonal elements).
  • Hutchinson vs. Gaussian: While general bounds are improved, the matrix-dependent bounds highlight scenarios where one method might be significantly better than the other. For instance, a skewed eigenvalue distribution might favor Hutchinson over Gaussian.
  • Unit Vector Estimator's Niche: The unit vector estimator, especially without replacement, can be surprisingly efficient for certain matrices, particularly those with similar diagonal elements, sometimes requiring only one sample.
  • Necessary vs. Sufficient Bounds: The paper emphasizes the distinction between sufficient bounds (guaranteeing accuracy if N is met) and necessary bounds (indicating a minimum N required). The necessary bound for the Gaussian estimator is particularly useful for identifying cases where it might be inefficient.

Key Results

  • Improved General Bounds: The paper provides tighter, general bounds for the Hutchinson and Gaussian estimators, reducing the required sample size $N$ compared to prior work. For example, the bound for the Gaussian estimator is improved by a factor of 2.5.
  • Matrix-Dependent Bounds: New bounds are derived that depend on matrix properties like $K_H$ (related to off-diagonal energy for Hutchinson) and $K_G$ (related to eigenvalue distribution for Gaussian). These bounds offer more precise guidance on sample size requirements for specific matrix types.
  • Unit Vector Estimator Performance: Analysis shows that the unit vector estimator can be very efficient when diagonal elements are similar, sometimes requiring $N=1$.
  • Numerical Verification: Extensive numerical experiments (summarized in Figures 5-10) validate the theoretical findings, demonstrating how the actual sample size required aligns with the predictions of the derived bounds and how different matrix properties influence estimator performance.

Limitations and Future Work

  • Matrix-Dependent Bounds Not Always Computable: The matrix-dependent bounds, while insightful, rely on quantities ($K_H, K_G, K_U$) that are not easily computable for implicit matrices. This limits their direct practical application for choosing an estimator without prior knowledge of these quantities.
  • Pessimism of General Bounds: The paper acknowledges that the general, easily computable bounds (like (4) and (5)) can be overly pessimistic, especially for large matrices or when high accuracy is not strictly needed.
  • Future Work: The authors suggest that exploring examples where a linear combination of $\chi^2$ random variables has smaller variance but higher tail probability would be valuable. They also note that the necessary bound for the Gaussian estimator can help predict required $N$ when rank is known, implying further potential for tailored analysis. The paper also hints at the possibility of extending results to complex-valued matrices.

Summary updated

Abstract

This article is concerned with Monte-Carlo methods for the estimation of the trace of an implicitly given matrix $A$ whose information is only available through matrix-vector products. Such a method approximates the trace by an average of $N$ expressions of the form $\ww^t (A\ww)$, with random vectors $\ww$ drawn from an appropriate distribution. We prove, discuss and experiment with bounds on the number of realizations $N$ required in order to guarantee a probabilistic bound on the relative error of the trace estimation upon employing Rademacher (Hutchinson), Gaussian and uniform unit vector (with and without replacement) probability distributions. In total, one necessary bound and six sufficient bounds are proved, improving upon and extending similar estimates obtained in the seminal work of Avron and Toledo (2011) in several dimensions. We first improve their bound on $N$ for the Hutchinson method, dropping a term that relates to $rank(A)$ and making the bound comparable with that for the Gaussian estimator. We further prove new sufficient bounds for the Hutchinson, Gaussian and the unit vector estimators, as well as a necessary bound for the Gaussian estimator, which depend more specifically on properties of the matrix $A$. As such they may suggest for what type of matrices one distribution or another provides a particularly effective or relatively ineffective stochastic estimation method.
BibTeX
@inproceedings{roostakhorasani2013improved,
  author = {Farbod Roosta-Khorasani and Uri M. Ascher},
  title = {{Improved bounds on sample size for implicit matrix trace estimators}},
  booktitle = {Found. Comput. Math},
  year = {2013},
  doi = {10.1007/s10208-014-9220-1},
}
Figure