In modern machine learning and scientific computing, we frequently encounter "matrix functions"—operations like the matrix square root ($A^{1/2}$), the matrix exponential ($e^A$), or the log-determinant ($\log \det A$). While these are easy to define for a scalar $x$, computing them for a large matrix $A$ typically requires an eigendecomposition or Singular Value Decomposition (SVD).
For a matrix of size $n \times n$, these decompositions cost $O(n^3)$ time, a "cubic bottleneck" that becomes prohibitive as datasets grow. To bypass this, researchers have developed a suite of techniques that replace exact decompositions with polynomial and rational approximations. By treating the matrix function as a scalar approximation problem over the matrix's spectrum, these methods transform expensive global operations into sequences of fast, GPU-friendly matrix-vector products.
The Spectral Mapping Intuition
The core "magic" of this field, as described by Sushant Sachdeva and Nisheeth K Vishnoi in Approximation Theory and the Design of Fast Algorithms, relies on the spectral mapping theorem. If a polynomial $p(x)$ closely approximates a scalar function $f(x)$ over the range of a matrix's eigenvalues (its spectrum), then the matrix polynomial $p(A)$ will be an equally good approximation of the matrix function $f(A)$.
This shifts the problem from linear algebra to approximation theory: how can we find a low-degree polynomial or rational function that mimics $f(x)$?
Polynomial Approximations: Taylor vs. Chebyshev
The simplest way to approximate a function is a Taylor expansion, which represents a function as a sum of powers ($A^0, A^1, A^2, \dots$). While easy to implement, Taylor series often converge slowly and can be numerically unstable, particularly for ill-conditioned matrices.
To achieve better performance, researchers like Vladimir Braverman and Christos Boutsidis have utilized Chebyshev polynomials. Unlike Taylor series, which are accurate near a single point, Chebyshev approximations are "minimax optimal"—they minimize the maximum error across a specific interval.
As shown in Large-scale log-determinant computation through stochastic Chebyshev expansions, this approach allows for the estimation of log-determinants for matrices with millions of variables. By combining Chebyshev expansions with the Hutchinson trace estimator, the $O(n^3)$ cost is reduced to a series of matrix-vector products that scale linearly with the number of non-zero entries in the matrix.
Rational Functions and the Power of Poles
While polynomials are excellent for smooth functions, they struggle with functions that have singularities or sharp transitions, such as the matrix inverse or square root. In these cases, rational functions—the ratio of two polynomials—are far more efficient.
Yue Song and colleagues demonstrate in Fast Differentiable Matrix Square Root that Padé approximants (a type of rational approximation) converge significantly faster than Taylor series for computing $A^{1/2}$. This is critical for deep learning tasks like ZCA whitening or global covariance pooling, where the operation must be both fast and differentiable.
Another powerful rational approach is the resolvent expansion or pole expansion. As used by Ilyes Batatia and Gabor Csanyi in Equivariant Matrix Function Neural Networks, this method represents a matrix function as a weighted sum of matrix inverses: $$f(A) \approx \sum w_i (A - z_i I)^{-1}$$ By learning the weights $w_i$ and poles $z_i$, neural networks can model complex, non-local interactions in physical systems (like molecules) without the quadratic cost of Transformers.
Iterative Solvers and Instance Optimality
In many applications, we don't need the full matrix $f(A)$, but rather its action on a vector, $f(A)b$. This is the domain of Krylov subspace methods, such as the Lanczos algorithm.
Recent theoretical work by Noah Amsel, Cameron Musco, and Christopher Musco has provided a "near-optimality" guarantee for these methods. In Near-Optimality Guarantees for Approximating Rational Matrix Functions by the Lanczos Method, they prove that for rational functions, the Lanczos method performs nearly as well as the best possible algorithm for any specific matrix and vector. This bridges the gap between the method's long-standing empirical success and its theoretical foundations.
Why It Works: Hardware and Parallelism
The shift from decompositions to approximations isn't just a mathematical trick; it's a hardware necessity. Traditional SVD and eigendecomposition algorithms are sequential and involve heavy branching, making them difficult to accelerate on GPUs.
In contrast, polynomial and rational approximations rely almost entirely on dense matrix-matrix multiplications or matrix-vector products. As highlighted in Fast Differentiable Matrix Square Root and Inverse Square Root, these operations are the "native language" of modern hardware accelerators. By reformulating matrix functions as iterative multiplications, researchers have achieved speedups of over 20x in computer vision and optimization tasks while maintaining high numerical precision.