Low-rank approximation of analytic kernels

Technical Summary: Low-rank approximation of analytic kernels

Problem Statement
Many matrices and kernels in scientific computing and data science exhibit a "nearly-low-rank" structure, meaning they can be well-approximated by low-rank matrices in various norms. Understanding the theoretical underpinnings of this structure is essential for the analysis and development of high-performance algorithms. While existing explanations rely on the approximation of smooth functions by polynomials (yielding exponential decay based on Bernstein ellipses) or displacement structure (via Sylvester equations), these approaches often yield pessimistic error bounds or fail to fully exploit the analytic properties of the kernel. Specifically, current bounds based on polynomial interpolation often decay at a rate determined by the largest Bernstein ellipse, which may be significantly smaller than the true convergence rate achievable by rational approximation.

Methodology
The paper introduces a new framework for bounding the low-rank approximation error of matrices arising from samples of a kernel $K(x,y)$ that is analytically continuable in one variable (say $y$) from a compact set $E$ to a large open set containing a disjoint compact set $F$.

The core of the methodology is an operator decomposition derived from the Cauchy integral formula:
$$K = K' \mathcal{C}$$
where:

1. $\mathcal{C}$ is a Cauchy transform operator mapping $L^2_\mu(E)$ to a space of analytic functions $H(F)$.
2. $K'$ is a "Grothendieck dual" operator mapping $H(F)$ to $C(D)$. This operator translates the singularities of $K(x, \cdot)$ in $F$ into an action (such as evaluation, differentiation, or convolution) on functions defined on $F$.

The low-rank approximation $K_n$ is constructed by approximating the Cauchy transform $\mathcal{C}$ with a rank-$n$ operator $\mathcal{C}_n$. The kernel of $\mathcal{C}_n$ is derived from a rational function $\phi \in R_n$ (rational functions of type $(n,n)$). The error bound is governed by the Cauchy–Zolotarev numbers, defined as:
$$Z_n(L^p_\mu(E), L^q_\nu(F)) = \inf_{\phi \in R_n} \left\| \frac{\phi(z)^{-1}\phi(y)}{y-z} \right\|_{L^p_\mu(E) \to L^q_\nu(F)}$$
These numbers decay exponentially with $n$, with a rate determined by the conformal modulus $\rho(E,F)$, which quantifies the separation between $E$ and $F$.

The construction of the approximant $K_n$ is shown to be equivalent to rational interpolation of the kernel $K(x, \cdot)$. The interpolation nodes and poles are the roots and poles of the optimal rational function $\phi$ that minimizes the Cauchy–Zolotarev number. For specific geometries (e.g., disjoint intervals), these optimal functions are the classical Zolotarev rational functions.

Key Contributions

1. Theoretical Framework: The paper establishes Theorem 1.1, providing a bound on the low-rank approximation error involving the Cauchy–Zolotarev numbers and the norm of the Grothendieck dual operator $K'$. This unifies continuous kernels and discrete matrices/tensors under a single framework.
2. Superior Convergence Rates: The theory demonstrates that the convergence rate is controlled by the conformal modulus $\rho(E,F)$, which is often significantly larger than the parameter of the largest Bernstein ellipse used in polynomial interpolation bounds. This explains why rational approximations often outperform polynomial ones for analytic kernels.
3. Constructive Algorithm: The proof is constructive, showing that the optimal low-rank approximant is a rational interpolant. The interpolation nodes and poles are explicitly identified as the roots and poles of the optimal Zolotarev rational function.
4. Displacement Structure via Duality: The work reveals a latent displacement structure in analytic kernels through the lens of Grothendieck duality, connecting the kernel's analytic continuation properties to the solvability of displacement equations.
5. Handling Singularities: The framework accommodates cases where the Cauchy transform is unbounded (e.g., $L^2 \to L^1$) by utilizing the Grothendieck dual operator, provided $n \ge 1$.

Results
The paper validates the theory through several numerical examples:

• Gamma/Hankel Matrices: For the matrix $A_{i,j} = \Gamma(i+j+1/2)/\Gamma(i+j+1)$, the new bounds (Theorem 1.1) and the corresponding rational interpolants significantly outperform existing bounds based on polynomial interpolation (Little–Reade) and displacement structure (Beckermann–Townsend). The error decay matches the singular values of the matrix closely.
• Cauchy Matrices and Tensors: The framework recovers known optimal results for Cauchy matrices and extends them to Cauchy tensors, confirming that the error is bounded by the Zolotarev number of the underlying sets.
• Log-Cauchy and Twisted Hankel Matrices: The theory successfully bounds the error for kernels with logarithmic singularities and Hankel transforms, where the Grothendieck dual operator involves integration or specific weightings.
• Beta-Cauchy Matrices: The approach is applied to matrices arising in change-of-basis between orthogonal polynomials, showing that rational interpolation with Zolotarev nodes achieves the theoretical bounds.

In all cases, the computable rational approximations (using Zolotarev nodes and poles) achieve the theoretical error bounds, and the error decay is exponential with a rate determined by the separation of the domain and singularity sets.

Significance
The paper claims that this framework provides a more precise and often tighter characterization of low-rank approximability for analytic kernels than previous methods. By shifting the focus from polynomial interpolation (Bernstein ellipses) to rational interpolation (conformal modulus), the theory explains the superior performance of rational approximations in practice. The introduction of the Grothendieck dual operator allows for a unified treatment of kernels with various singularity structures, including those where the Cauchy transform is unbounded. Furthermore, the constructive nature of the proof leads to fast algorithms for building these approximations using rational interpolation with prescribed poles, limited only by the ability to compute the optimal Zolotarev rational functions for the specific sets involved. The work suggests that future improvements in computing Zolotarev functions for discrete sets could further enhance the practical utility of these bounds.