Abstract
Stochastic trace estimation is a critical tool for large-scale linear algebra, particularly when matrices are too large to be explicitly formed. This paper introduces a novel estimator based on Mutually Unbiased Bases (MUBs), a concept originating in quantum information theory. By leveraging the property that MUBs provide maximum uncertainty between measurements, we derive an estimator that achieves significantly lower variance than the industry-standard Hutchinson estimator. Furthermore, the MUBs estimator is highly efficient in terms of randomness, requiring only $O(\log n)$ random bits compared to the $O(n)$ bits required by traditional methods. Empirical evaluations on synthetic "spiky" matrices and real-world graph datasets demonstrate that the MUBs approach consistently outperforms existing state-of-the-art techniques.
Introduction
Computing the trace of a large matrix $A$—the sum of its diagonal elements—is a fundamental operation in machine learning, physics, and network analysis. In many practical scenarios, $A$ is only accessible via matrix-vector products $Ax$. Stochastic trace estimation addresses this by using the identity $\text{Tr}(A) = \mathbb{E}[x^T Ax]$, where $x$ is a random vector with zero mean and identity covariance. While Gaussian and Rademacher (Hutchinson) noise are standard choices for $x$, they often suffer from high variance, particularly when the diagonal of $A$ is non-uniform or "spiky."
Methodology: Mutually Unbiased Bases
The core innovation of this work is the application of Mutually Unbiased Bases (MUBs) to trace estimation. In a $n$-dimensional complex vector space, two bases are mutually unbiased if the inner product of any vector from the first basis with any vector from the second basis has a constant magnitude of $1/\sqrt{n}$.
The MUBs Estimator
Instead of generating $n$ independent random variables for each entry of $x$, the MUBs estimator selects one basis from a set of $n+1$ possible MUBs at random, and then selects one specific vector from that basis at random. This strategy ensures that the information about the diagonal is spread evenly across the sampling space.
Efficiency and Construction
- Randomness Efficiency: Because the estimator only needs to index a basis and a vector, it requires only $\approx 2 \log_2(n)$ random bits, a significant reduction from the $O(n)$ bits needed for Gaussian or Hutchinson estimators.
- Computational Complexity: The authors provide an $O(n)$ construction using shift and phase matrices (roots of unity), ensuring the method remains computationally competitive with standard FFT-based approaches.
Experimental Evaluation
Synthetic "Spiky" Matrices
A common failure mode for trace estimators occurs when a few diagonal elements are much larger than the rest. The MUBs estimator is theoretically robust to such distributions. As shown in Figure 1, the MUBs estimator achieves an RMSE several orders of magnitude lower than Gaussian, Hutchinson, or Unit vector estimators when applied to a "spiky" ones matrix.
Real-World Graph Datasets
The method was also tested on real-world social and citation networks from the SNAP database (wiki-Vote, cit-HepTh, ca-GrQc, and ca-AstroPh) for the task of triangle counting. In these applications, the trace of the cube of the adjacency matrix relates to the number of triangles in the graph.
As illustrated in Figure 3, the MUBs estimator consistently provides the lowest RMSE across all tested network topologies. This confirms that the theoretical variance reduction translates effectively to practical, high-dimensional data.
Key Insights and Results
- Variance Reduction: The authors prove that the worst-case variance for the MUBs estimator is approximately $\frac{n-1}{n+1} \text{Tr}(A^2)$, which is roughly half that of the Hutchinson estimator ($\approx \frac{2(n-1)}{n} \text{Tr}(A^2)$).
- Log-Determinant Estimation: The MUBs approach also improves the approximation of log-determinants for kernel matrices, which is vital for Gaussian Process regression.
Conclusion
By bridging quantum information theory and classical numerical linear algebra, this paper provides a more robust and randomness-efficient method for stochastic trace estimation. While the current implementation is most efficient for dimensions that are prime powers and involves complex arithmetic, its superior variance properties make it a compelling alternative to traditional Hutchinson-style estimators in large-scale applications.
Summary updated