Abstract
We develop heuristic interpolation methods for the functions $t \mapsto \log \det \left( \mathbf{A} + t \mathbf{B} \right)$ and $t \mapsto \operatorname{trace}\left( (\mathbf{A} + t \mathbf{B})^{p} \right)$ where the matrices $\mathbf{A}$ and $\mathbf{B}$ are Hermitian and positive (semi) definite and $p$ and $t$ are real variables. These functions are featured in many applications in statistics, machine learning, and computational physics. The presented interpolation functions are based on the modification of sharp bounds for these functions. We demonstrate the accuracy and performance of the proposed method with numerical examples, namely, the marginal maximum likelihood estimation for Gaussian process regression and the estimation of the regularization parameter of ridge regression with the generalized cross-validation method.
Introduction
The computational cost of evaluating the log-determinant or the trace of the inverse of a large matrix function $\mathbf{A} + t\mathbf{B}$ represents a significant hurdle in modern statistics and machine learning. These operations are central to tasks such as hyperparameter tuning in Gaussian Process (GP) regression and determining the optimal regularization parameter in Ridge Regression. For a matrix of size $n \times n$, exact computation typically requires Cholesky or LU factorization, which scales as $O(n^3)$. In iterative optimization loops where $t$ varies, this cost becomes prohibitive. While randomized estimators like Hutchinson’s method or Stochastic Lanczos Quadrature (SLQ) offer some relief, they still require significant resources if re-evaluated for every value of $t$. This paper presents a heuristic interpolation method that achieves high accuracy with only a few exact evaluations, effectively bypassing the $O(n^3)$ bottleneck.
Methodology
The core of the approach lies in leveraging the predictable asymptotic behavior of the functions $t \mapsto \log \det(\mathbf{A} + t\mathbf{B})$ and $t \mapsto \text{trace}((\mathbf{A} + t\mathbf{B})^{-1})$. The authors derive sharp upper and lower bounds based on matrix inequalities and a unified Schatten-type operator. These bounds provide a rigid framework that constrains the function's behavior at the extremes ($t \to 0$ and $t \to \infty$).
To interpolate between these bounds, two classes of functions are proposed. Rational polynomials, such as Padé approximations, are highly effective for small values of $t$ but can suffer from numerical instability or singularities at higher orders. To address this, the authors introduce Orthogonalized Inverse-Monomials. These basis functions are specifically designed to remain stable over the wide logarithmic scales often encountered in parameter optimization.
The stability of these functions is achieved through an orthogonalization process. The resulting basis functions $\phi_i^\perp(t)$ (shown in Figure 1) allow for high-order interpolation without the ill-conditioning typical of standard polynomial bases. The coefficients $a_{ij}$ and normalization constants $\alpha_i$ required to construct these functions are pre-calculated and provided for various orders $i$, as shown in the table below.
Experimental Evaluation
The effectiveness of the interpolation was demonstrated through two primary case studies. In Gaussian Process regression with $n=2,500$, the method achieved a relative error of less than 0.01% across a parameter range spanning seven orders of magnitude ($10^{-4}$ to $10^3$) using only 9 interpolation points.
In the context of Ridge Regression, the method was used to compute the Generalized Cross-Validation (GCV) curve. The interpolation reduced the time required for trace computations by a factor of 100, leading to a 10-fold reduction in total optimization time. Crucially, the accuracy of the final optimized weights remained within 1% of the exact solution. Furthermore, the method shows strong synergy with stochastic solvers; when paired with SLQ, it achieved a 20-fold speedup while maintaining an error rate comparable to exhaustive stochastic evaluation.
Conclusion
The proposed interpolation method offers a powerful tool for scaling matrix-dependent statistical models. By combining rigorous mathematical bounds with stable basis functions like orthogonalized inverse-monomials, the authors provide a solution that is both fast and accurate. While users must be cautious of potential singularities in rational polynomial approximations, the overall framework significantly reduces the computational burden of log-determinant and trace evaluations. The implementation of these methods in the open-source imate package ensures their accessibility for large-scale applications in machine learning and computational physics.
Summary updated