Interpolating Log-Determinant and Trace of the Powers of Matrix $\mathbf{A} + t \mathbf{B}$

Siavash Ameli, Shawn C. Shadden

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.

Orthogonalized inverse-monomial basis functions $\phi_i^\perp(t)$ plotted on a logarithmic scale for $t$.

The coefficients for these orthogonalized functions are pre-calculated to ensure efficiency and stability in the implementation, as shown in the table below.

Coefficients $\alpha_i$ and $a_{ij}$ used to construct the orthogonalized basis functions for interpolation.

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

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.
BibTeX
@article{ameli2022interpolating,
  author = {Siavash Ameli and Shawn C. Shadden},
  title = {{Interpolating Log-Determinant and Trace of the Powers of Matrix $\textbackslash\{\}mathbf\{A\} + t \textbackslash\{\}mathbf\{B\}$}},
  journal = {Stat. Comput.},
  year = {2022},
  doi = {10.1007/s11222-022-10173-4},
}

Loading related content...

Figure