In modern machine learning and large-scale scientific computing, we frequently encounter the need to evaluate a function applied to a massive matrix. Whether we are computing the inverse square root of a preconditioner in second-order optimization, calculating the matrix exponential for graph diffusion, or estimating spectral norms and ranks, the core mathematical challenge is the same: we need to compute $f(\mathbf{A})$ or its action on a vector $f(\mathbf{A})\mathbf{b}$.
The textbook approach to this problem relies on the spectral theorem. If a symmetric matrix $\mathbf{A}$ has an eigengap and can be diagonalized as $\mathbf{A} = \mathbf{V} \mathbf{\Lambda} \mathbf{V}^\top$, then the matrix function is defined by applying the scalar function to its eigenvalues: $f(\mathbf{A}) = \mathbf{V} f(\mathbf{\Lambda}) \mathbf{V}^\top$. However, for a matrix with dimensions in the tens of thousands or millions, computing the full eigendecomposition requires $O(n^3)$ time—an insurmountable computational bottleneck.
To bypass this bottleneck, a powerful paradigm has emerged: matrix function approximation. Instead of decomposing the matrix, we treat $f(\mathbf{A})$ through the lens of approximation theory, replacing the complex scalar function $f(x)$ with a low-degree polynomial $p(x)$ or a rational function $r(x)$. Because a polynomial of a matrix involves only repeated matrix-matrix or matrix-vector multiplications, this shift transforms an intractable global decomposition problem into a sequence of highly parallelizable, localized operations.
Shifting from Decomposition to Multiplication
To understand why polynomial approximation works, consider the simplest case: approximating $f(\mathbf{A})\mathbf{b}$ using a standard polynomial $p(x) = c_0 + c_1 x + c_2 x^2 + \dots + c_d x^d$. When we evaluate this polynomial on the matrix $\mathbf{A}$ and apply it to $\mathbf{b}$, we get:
$$p(\mathbf{A})\mathbf{b} = c_0 \mathbf{b} + c_1 \mathbf{A}\mathbf{b} + c_2 \mathbf{A}(\mathbf{A}\mathbf{b}) + \dots + c_d \mathbf{A}(\dots \mathbf{A}\mathbf{b})$$
Notice that we never actually compute $\mathbf{A}^2$ or $\mathbf{A}^3$ explicitly. Instead, we compute a chain of matrix-vector products. If $\mathbf{A}$ is sparse or structured, each product takes near-linear time.
The core challenge then shifts from linear algebra to approximation theory: How do we find a low-degree polynomial that closely matches $f(x)$ over the entire spectrum of $\mathbf{A}$?
The Power of Chebyshev Polynomials
A naive choice would be to use a Taylor series expansion. However, Taylor series expand around a single point and can require an exceptionally high degree to achieve accuracy across a wide interval. As Braverman demonstrates in Approximations of Schatten Norms via Taylor Expansions, while Taylor expansions can simplify implementation by avoiding complex coefficient calculations for certain spectral functions like the Schatten $p$-norm, they are often outperformed in convergence rate by orthogonal polynomials when the matrix spectrum is wide.
To minimize the maximum approximation error over a bounded interval, researchers turn to Chebyshev polynomials. Chebyshev polynomials wiggle uniformly between $-1$ and $1$, preventing the error from exploding at the boundaries of the spectrum.
Taylor Expansion (Error grows rapidly away from the expansion point)
\ /
\_______*_______/
Chebyshev Approximation (Error is distributed uniformly across the interval)
_.-'-._.-'-._.-'-._
[===================] <- Bounded Spectrum Interval
By scaling and shifting the matrix spectrum to fit within $[-1, 1]$, Chebyshev polynomials provide a near-optimal approximation using the minimum possible degree. For instance, Allen-Zhu et al. in Faster Principal Component Regression and Stable Matrix Chebyshev Approximation leverage stable matrix Chebyshev polynomials to accelerate Principal Component Regression. By replacing exact eigenvector computations with these polynomial proxies, the authors reduce the computational complexity from a quadratic dependence on the precision parameter to a linear one ($O(\gamma^{-2})$ to $O(\gamma^{-1})$), providing a massive speedup for high-precision applications.
Similarly, Lee et al. show in An $\widetilde\mathcalO(m/\varepsilon^3.5)$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints that when the matrix spectrum is bounded, Chebyshev polynomial expansions can be used to compute the diagonal entries of a matrix exponential far more efficiently than Taylor series. This reduces the cost of matrix-vector products in optimization loops from a linear dependence on the error parameter to a square-root dependence.
Rational Functions for Sharp Transitions
While polynomials are excellent for smooth functions like the exponential, they struggle with functions that exhibit sharp transitions, discontinuities, or poles—such as the matrix sign function $\text{sign}(\mathbf{A})$, the step function (used for rank estimation), or the inverse square root $\mathbf{A}^{-1/2}$ near zero. To approximate a sharp step, a polynomial requires a very high degree, which introduces unwanted oscillations (the Gibbs phenomenon).
To solve this, researchers use rational functions—ratios of two low-degree polynomials, $r(x) = p(x)/q(x)$. Rational functions can place poles close to the boundaries or discontinuities, allowing them to mimic sharp transitions with an exponentially lower degree than pure polynomials.
Zolotarev and Resolvent Expansions
A prime example of this is found in Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG. In this work, Jin et al. utilize Zolotarev rational functions to approximate the matrix sign function. While a polynomial approximation requires a degree that scales linearly with the inverse of the eigengap, the Zolotarev rational approximation requires a degree that scales logarithmically. This drastic reduction in degree allows spectral projection and regression tasks to run in nearly linear time, even when the gap between eigenvalues is extremely small.
Another way to express rational approximations is through resolvent expansions, which represent a matrix function as a sum of learnable poles:
$$f(\mathbf{A}) \approx \sum_{i=1}^k c_i (\mathbf{A} - z_i \mathbf{I})^{-1}$$
In Equivariant Matrix Function Neural Networks, Batatia et al. use these resolvent expansions within Graph Neural Networks (GNNs). By learning the poles $z_i$ and coefficients $c_i$, the network can capture long-range, non-local interactions across a graph without resorting to the quadratic cost of Transformers. Because evaluating a resolvent involves solving a sparse linear system rather than a full factorization, the model maintains linear scaling while strictly respecting physical symmetries.
To bridge the gap between general functions and the specific convergence properties of linear system solvers, Amsel et al. demonstrate in Nearly Optimal Approximation of Matrix Functions by the Lanczos Method that iterative subspace methods implicitly construct these optimal rational approximations, providing a unified framework for computing the action of complex matrix functions.
Scaling Up via Randomized Sketching
Even when using low-degree polynomials or rational functions, evaluating the function across an entire matrix can still be expensive if we need global properties like the trace or the diagonal entries. To scale these methods to massive matrices, polynomial approximation is frequently paired with randomized sketching.
Trace and Diagonal Estimation
Suppose we want to estimate the Schatten $p$-norm of a matrix, which is equivalent to computing $\text{Tr}(|\mathbf{A}|^p)$. We can combine a polynomial approximation of $f(x) = |x|^p$ with the Hutchinson trace estimator. The Hutchinson estimator approximates the trace of any implicit matrix $\mathbf{M}$ by taking the average of $\mathbf{x}^\top \mathbf{M} \mathbf{x}$ for several random vectors $\mathbf{x}$ drawn from a Rademacher distribution.
When $\mathbf{M} = p(\mathbf{A})$, the core operation becomes evaluating $\mathbf{x}^\top p(\mathbf{A}) \mathbf{x}$, which reduces entirely to the efficient matrix-vector products we established earlier. Han et al. apply this exact combination in Stochastic Chebyshev Gradient Descent for Spectral Optimization. By pairing randomized trace estimators with a variance-optimal stochastic truncation of Chebyshev expansions, they compute unbiased stochastic gradients for spectral functions, enabling fast optimization for large-scale Gaussian Process regression and matrix completion.
The Nyström Bridge
When a low-rank structure is present, Nyström approximations serve as a bridge between projection-based methods and function approximations. In Algorithm-Agnostic Low-Rank Approximation of Operator Monotone Matrix Functions, Persson et al. prove a powerful structural property: if any projection-based method yields a good low-rank approximation of a matrix $\mathbf{A}$, a Nyström approximation derived from it will automatically yield a good low-rank approximation of $f(\mathbf{A})$ for any operator monotone function. This allows practitioners to decouple the choice of low-rank sketching algorithms from the function evaluation itself.
Composition and Practical Applications
In practice, these mathematical pieces are assembled into highly specialized pipelines to solve distinct engineering challenges across machine learning.
1. Distributed Computing and Composite Polynomials
When data is distributed across multiple machines, communication is often the primary bottleneck. In Distributed Estimation of Generalized Matrix Rank: Efficient Algorithms and Lower Bounds, Zhang et al. show that instead of using a single high-degree polynomial, one can nest multiple polynomial functions. By combining a coarse Chebyshev approximation with a boosting polynomial, the error decays exponentially rather than polynomially. This composite approach drastically reduces the number of communication rounds required to estimate the generalized rank of a distributed matrix.
2. Accelerating Deep Learning Optimizers
Second-order optimizers like Shampoo achieve faster convergence by computing the inverse roots of preconditioner matrices (e.g., $\mathbf{A}^{-1/2}$ or $\mathbf{A}^{-1/4}$). However, computing these roots exactly at every training step is too expensive.
In DASH: Faster Shampoo via Batched Block Preconditioning and Efficient Inverse-Root Solvers, Modoranu et al. implement Chebyshev polynomial approximations via Clenshaw's algorithm to estimate these matrix roots without direct decomposition. Because the polynomial is composed entirely of matrix-matrix multiplications, it can be batched and parallelized perfectly on modern hardware accelerators, speeding up optimizer steps by up to 5.6×.
Similarly, Sebe et al. demonstrate in Fast Differentiable Matrix Square Root and Inverse Square Root that using polynomial or rational series (such as Taylor or Padé approximants) allows for highly efficient backpropagation through matrix roots, making second-order features practical for deep neural networks.
3. Graph and Spectral Clustering
In large-scale graph clustering, iterative solvers often stall when the "eigengap" (the difference between consecutive eigenvalues) is narrow. To accelerate convergence, van der Pol et al. introduce SPED (Stochastic Parallelizable Eigengap Dilation) in Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering. SPED applies a polynomial expansion to the graph Laplacian that artificially "stretches" or dilates the differences between eigenvalues. By widening this gap via cheap matrix powers, iterative eigensolvers converge orders of magnitude faster without altering the underlying cluster structure.
Summary
Matrix function approximation works because it shifts the computational burden from structural decomposition ($O(n^3)$) to iterative multiplication. By selecting the right approximation tool—Chebyshev polynomials for bounded intervals, rational functions for sharp discontinuities, and randomized sketching for dimensionality reduction—we can evaluate complex matrix transformations at a scale that would otherwise be computationally impossible.
Key Foundational Work
Faster Principal Component Regression and Stable Matrix Chebyshev Approximation (2017) — contributed 1 concept elements to this direction.
Approximating Spectral Sums of Large-Scale Matrices using Stochastic Chebyshev Approximations (2017) — contributed 1 concept elements to this direction.
Approximating Subadditive Hadamard Functions on Implicit Matrices (2015) — contributed 1 concept elements to this direction.