PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved bounds on sample size for implicit matrix trace estimators

Farbod Roosta-Khorasani, Uri Ascher

arXiv:1308.2475v2math.NA

TL;DR

The paper studies how many matrix-vector probes are needed to estimate the trace of an implicitly accessed matrix with probabilistic relative-error guarantees. It proves and evaluates bounds for Hutchinson, Gaussian, and uniform unit-vector estimators, including matrix-dependent guidance and a necessary Gaussian bound. The results improve earlier estimates and indicate how matrix properties can favor one sampling distribution over another, while the general sufficient bounds are not guaranteed to be tight.

  • Problem

    The paper addresses how to guarantee accurate trace estimation when a matrix is available only through matrix-vector products, and how different sampling distributions handle different matrix types.

  • Method

    The paper proves six sufficient and one necessary sample-size bounds for Hutchinson, Gaussian, and uniform unit-vector estimators, then verifies their predicted trends numerically.

  • Results

    The improved Hutchinson bound removes rank(A), while the bounds collectively provide general and matrix-dependent guidance across the three estimator families.

  • Takeaways & Limitations

    The bounds can indicate which estimator suits particular matrix properties, and in large problems general bounds may assure that N is much smaller than n.

  • Takeaways & Limitations

    The six sufficient bounds are not generally tight, and matrix-dependent quantities used by several bounds are not easily computable for implicit matrices.

Abstract

from arXiv · show

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.

1 Introduction

The paper improves probabilistic sample-size bounds for implicit trace estimation and extends them across Hutchinson, Gaussian, and uniform unit-vector estimators. The bounds include general guarantees and matrix-dependent conditions that help characterize when each distribution may be effective.

  • The improved Hutchinson bound removes the previous rank(A) term and holds for every SPSD matrix.The corresponding general bounds are independent of matrix size and other matrix properties, so they may be pessimistic for specific matrices.
  • Matrix-dependent bounds are introduced to indicate which matrix types favor Hutchinson, Gaussian, or unit-vector sampling, although these quantities are generally difficult to compute implicitly.The unit-vector analysis also distinguishes sampling with replacement from sampling without replacement, with the latter receiving a tighter bound.
  • The Gaussian analysis improves the earlier sufficient bound by a factor of 2.5 and adds a necessary lower bound on N.The Gaussian bounds include both a general sufficient estimate and a matrix-property-dependent alternative.
  • Numerical examples verify that the theoretical trends occur in practice.The paper studies the estimators through numerical examples after developing the corresponding bounds.

2 Hutchinson estimator bounds

For Hutchinson estimation of SPSD matrices, the paper gives a rank-independent general bound and a matrix-dependent bound based on off-diagonal energy. The latter can improve sample-size guidance for suitable matrices but may be pessimistic when its maximum dominates typical values.

  • 2.1 Improving the bound in [4]: The improved Hutchinson bound applies to every SPSD matrix without the previous rank(A) factor.The result provides the same type of probabilistic relative-error guarantee while removing the rank dependence from the earlier bound.
  • 2.2 A matrix-dependent bound: The matrix-dependent Hutchinson bound uses KH, the maximum relative ℓ2 off-diagonal energy, to identify matrices for which sampling may require fewer realizations.The bound is worth considering relative to the general bound when KH < 3.
  • 2.2 A matrix-dependent bound: The KH-based bound can be pessimistic when most column-wise off-diagonal energies are far below their maximum.Simulations indicate that Hutchinson can remain efficient despite large outliers when most values are concentrated near zero.
  • 2.2 A matrix-dependent bound: When KH = 0, the matrix is diagonal and Hutchinson recovers the trace in one sample; increasing off-diagonal energy is expected to increase the required N.This connects the bound directly to the matrix’s diagonal-versus-off-diagonal structure.

3 Gaussian estimator bounds

The Gaussian estimator receives sufficient bounds, including a matrix-dependent bound, and a rank-dependent necessary lower bound. These results identify matrices for which Gaussian sampling can be efficient or practically unusable.

  • Sufficient bounds: The first sufficient Gaussian bound improves the prior result by a factor of 2.5, while the matrix-dependent bound can be more informative.The matrix-dependent bound is potentially less available but reflects properties of A.
  • Sufficient bounds: A small ratio ∥A∥/tr(A), such as when eigenvalues are approximately equal, implies that the Gaussian estimator requires only a small sample size.The same behavior is supported by the estimator’s variance, which depends on the Frobenius norm.
  • Sufficient bounds: The sufficient bound’s constant is inversely proportional to stable rank, suggesting Gaussian estimation may become inefficient when stable rank is low.This intuition is further supported by the paper’s necessary condition.
  • A necessary bound: A rank-dependent necessary condition is computable when rank(A) is known and is nearly tight for equal-eigenvalue matrices.The paper demonstrates this tightness analytically and with Figure 1.
  • A necessary bound: For low-rank matrices with small Hutchinson-specific factors, the necessary Gaussian condition can certify a smaller required sample size for Hutchinson.The comparison cannot be made directly from the sufficient bounds because those bounds are not tight.
  • A necessary bound: For low-rank matrices, the necessary sample size can exceed n, making the Gaussian method practically useless for those instances.For n = 1000 and r ≤30, Figure 1 reports necessarily N > n.

4 Random unit vector bounds, with and without replacement, for general square matrices

The unit-vector estimators are analyzed for sampling with and without replacement through variance and probabilistic sample-size bounds. Without replacement can be advantageous, especially when diagonal entries are similar.

  • Estimator setup: Unit-vector estimators use columns of the scaled identity matrix, and deterministic trace recovery is possible in N = n steps.The stochastic goal is to approximate the trace with N ≪n steps.
  • Variance and sampling strategies: Sampling without replacement has smaller variance than sampling with replacement, and the difference is small when N ≪n.The variances coincide for N = 1 and both vanish when all diagonal entries are equal.
  • Bounds for unit-vector estimators: The without-replacement strategy may generally require smaller sample sizes, formalizing the intuition that it can improve on sampling with replacement.The analysis uses a separate bound for each strategy.
  • Bounds for unit-vector estimators: Unit-vector sampling is efficient when diagonal entries have similar values, requiring only one sample when they are all equal.The corresponding prior expression does not reflect the one-sample extreme case.
  • Bounds for unit-vector estimators: The bound for U2 is more resilient than U1 to the distribution of diagonal values, while the bounds are similar for very small KU.Figure 2 compares bounds (18) and (19) for n = 1000 and ε = δ = 0.05.

5 Numerical Examples

The numerical examples show that estimator performance depends strongly on matrix structure, with different methods excelling for different matrices. Experiments broadly support the paper’s matrix-dependent bounds while also showing that the sufficient bounds are not generally tight.

  • Example 1: For the all-ones matrix, the unit vector estimator converges in one sample, whereas Hutchinson and Gaussian estimators often require many samples.Here KU = 0 and N = 1 for the unit vector method; the figure reports average N around 50 for Hutchinson and Gaussian.
  • Special cases: For diagonal matrices, Hutchinson requires only one sample, while for scalar multiples of the identity Gaussian is the only method requiring more than one.These contrasting cases illustrate that no estimator dominates across all matrix structures.
  • Example 2: In the rank-1 decaying-vector experiment, Gaussian sample size changes little with decay, while unit-vector performance worsens as off-diagonal energy increases.Hutchinson’s sufficient condition worsens for heavier tails, but its actual required sample size can decrease for large decay parameters.
  • Example 3: For dense SPSD matrices, Hutchinson and Gaussian perform similarly, while both unit-vector estimators require approximately twice as many samples.The relatively balanced eigenvalue distribution helps Gaussian performance, while moderate unit-vector indicators permit decent unit-vector performance.
  • Examples 4–5: Gaussian sample size increases as rank decreases or eigenvalue distributions become more skewed, consistent with the rank- and KG-dependent experiments.For fixed rank, larger KG corresponds to a larger required sample size.
  • Interpretation: The experiments show that KH, KG, and KU values alone can mislead, because the distributions of the quantities they maximize also affect estimator performance.The six sufficient bounds are not guaranteed to be tight, reflecting the generality of the results.

6 Conclusions and further thoughts

The paper establishes six sufficient sample-size bounds and one necessary Gaussian bound, validating them numerically across examples. The conclusions emphasize when bounds are computable, how matrix structure and rank affect estimator choice, and when deterministic trace computation is preferable.

  • 6 Conclusions and further thoughts: Six sufficient bounds and one necessary Gaussian bound characterize the sample size needed for relative trace accuracy with probability 1 − δ.The bounds cover Hutchinson, Gaussian, and unit-vector estimators and were numerically verified across many examples.
  • 6 Conclusions and further thoughts: N-independent Hutchinson and Gaussian bounds can certify N ≪ n, although they may be pessimistic and generally have comparable quality.This is particularly relevant when n is very large and ε need not be very small.
  • 6 Conclusions and further thoughts: Variance should not be the sole comparison criterion, because lower variance does not necessarily imply lower tail probability.The paper notes that a linear combination can have smaller variance yet higher tail probability.
  • 6 Conclusions and further thoughts: The Gaussian lower bound can better predict the required N when rank r is known, while also indicating possible inferiority when r is small.Hutchinson lacks a comparable theory but does not empirically show the same disadvantage.
  • 6 Conclusions and further thoughts: Matrix-dependent quantities KH, KG, and KU can identify matrices for which one estimator is expected to be efficient, but they are difficult to compute implicitly.The corresponding sufficient conditions do not characterize matrices for which an estimator is inefficient.
  • 6 Conclusions and further thoughts: If a stochastic method requires N > n, deterministic unit-vector probing may be preferable because it obtains tr(A) in n applications.The deterministic alternative provides a practical fallback when stochastic sampling becomes too costly.
Loading 1308.2475v2…