Abstract
Computing the log-determinant and trace of matrix powers for large-scale matrices is a significant computational bottleneck in statistics and machine learning. We present a heuristic interpolation framework for functions of the form $t \mapsto \log \det (\mathbf{A} + t \mathbf{B})$ and $t \mapsto \operatorname{trace}((\mathbf{A} + t \mathbf{B})^{p})$, where $\mathbf{A}$ and $\mathbf{B}$ are Hermitian positive (semi)definite matrices. By leveraging mathematical bounds and orthogonal basis functions, our method achieves high accuracy with minimal function evaluations, offering up to two orders of magnitude speedup in optimization tasks such as Gaussian process regression and ridge regression.
Introduction
In many scientific and engineering disciplines, from climate modeling to quantum physics, researchers encounter the challenge of optimizing parameters within matrix-heavy functions. Specifically, the log-determinant $\log \det(\mathbf{A} + t\mathbf{B})$ is central to Maximum Likelihood Estimation (MLE), while the trace of matrix powers $\operatorname{trace}((\mathbf{A} + t\mathbf{B})^p)$ is essential for Generalized Cross-Validation (GCV).
For a matrix of size $n$, these operations typically scale as $O(n^3)$. When optimization algorithms require hundreds of evaluations across different values of $t$, the computational cost becomes prohibitive for large datasets. While stochastic estimators offer a path forward, they are often noisy and still require significant repetition. This research proposes an alternative: computing the function exactly at a small set of "anchor" points and using intelligent interpolation to fill the gaps.
Methodology
The proposed interpolation schemes are grounded in matrix analysis rather than simple polynomial fitting, ensuring they respect the underlying mathematical properties of the functions.
Schatten-Class Bounds
The framework utilizes Schatten-type norms (for $p \ge 1$) and "anti-norms" (for $p < 1$). These provide sharp inequalities that serve as a mathematical scaffold. Because these functions exhibit subadditive or superadditive properties, the true curve is guaranteed to lie on one side of specific chords, allowing the interpolation to be "physics-informed" regarding the function's curvature.
Orthogonal Basis Functions
To handle general interpolation without the numerical instability common in high-degree polynomials, the authors employ a linear combination of "inverse-monomial" basis functions. These are orthogonalized using the Gram-Schmidt process with respect to a Haar measure on a logarithmic scale. This approach is particularly robust when the parameter $t$ spans several orders of magnitude.
The coefficients for these orthogonalized functions are pre-calculated to ensure efficiency and stability in the implementation, as shown in the table below.
Rational Polynomials and Software
For cases involving ill-conditioned matrices or very small values of $t$, the method employs Padé approximations and Chebyshev rational functions. These are adept at capturing asymptotic behavior as $t \to 0$ or $t \to \infty$. These methods are integrated into imate, a high-performance Python library supporting CPU and GPU acceleration.
Applications and Key Results
The effectiveness of the interpolation was tested on synthetic datasets mimicking real-world challenges, including Gaussian Process Regression (using a correlation matrix from 2,500 spatial points) and Ridge Regression (using an ill-conditioned design matrix to test near-singularities).
The results demonstrate that evaluating the function at just 5 to 9 points is sufficient to reach a relative error of approximately $0.01\%$. In the Ridge Regression example, this translated to a two-order-of-magnitude speedup in finding the optimal regularization parameter compared to exact methods. Furthermore, the method is compatible with both exact solvers and randomized estimators like the Stochastic Lanczos Quadrature.
Limitations and Future Work
While highly effective, the method has some constraints. Padé approximations can occasionally introduce poles (singularities) within the domain of interest if anchor points are poorly chosen. Additionally, Chebyshev rational functions require tuning a scale parameter $\alpha$. Current research is focused on extending these one-parameter affine functions to multi-parameter scenarios (e.g., $\mathbf{A} + t_1\mathbf{B}_1 + t_2\mathbf{B}_2$), which remains a significant open challenge.
Summary updated