Low-rank approximation of analytic kernels

Basic Information

• Paper ID: 2509.14017
• Title: Low-rank approximation of analytic kernels
• Author: Marcus Webb (University of Manchester)
• Classification: math.NA cs.NA
• Publication Date: October 15, 2025 (arXiv version v3)
• Paper Link: https://arxiv.org/abs/2509.14017

Abstract

Many algorithms in scientific computing and data science exploit low-rank approximations of matrices and kernel functions. Understanding why approximate low-rank structures arise is crucial for their analysis and further development. This paper provides a framework of bounds on the best low-rank approximation error for matrices arising from samples of kernel functions that can be analytically continued to an open region of the complex plane in one variable. Elegantly, the low-rank approximations used in the proof can be computed through rational interpolation using the roots and poles of Zolotarev rational functions, yielding a fast constructive algorithm.

Research Background and Motivation

1. Core Problem: Many matrices and kernel functions in scientific computing and data science exhibit approximate low-rank structure, yet lack a unified theoretical framework to understand and quantify this phenomenon. Existing methods are primarily based on polynomial approximation theory for smooth functions, but tend to be overly conservative for kernel functions with analytic properties.
2. Problem Significance: Low-rank approximation is a core technique in modern numerical algorithms, with widespread applications in system identification, particle simulation, image compression, recommendation systems, and other fields. Understanding the fundamental causes of low-rank structure is essential for algorithm analysis and performance optimization.
3. Limitations of Existing Methods:
   • Methods based on Chebyshev polynomial interpolation (Little-Reade theory) are overly pessimistic
   • Beckermann-Townsend's displacement structure theory ignores the analyticity of kernel functions
   • Lack of a unified framework for handling continuous kernel functions and discrete matrices
4. Research Motivation: The author observes that many analytic kernel functions possess latent displacement structure through the Cauchy integral formula, providing a new perspective for establishing more precise low-rank approximation theory.

Core Contributions

1. Theoretical Framework: Proposes a new theoretical framework based on Cauchy-Zolotarev numbers for bounding low-rank approximation errors of analytic kernel functions
2. Unified Approach: Establishes a unified framework for handling continuous kernel functions and discrete matrices/tensors
3. Computable Approximation: Proves that optimal low-rank approximations can be constructed through rational interpolation of Zolotarev rational functions
4. Grothendieck Duality Theory: Introduces Grothendieck duality theory from functional analysis to numerical analysis
5. Practical Algorithm: Provides a fast algorithm based on rational interpolation that achieves or approaches optimal performance in multiple instances

Detailed Methodology

Problem Definition

Given a kernel function $K \in C(D \times E)$, where $D$ and $E$ are compact metric spaces, the goal is to find a rank-$n$ kernel function $K_n$ that minimizes the operator norm $\|K - K_n\|_{L^2_\mu(E) \to L^2_\lambda(D)}$.

Core Theoretical Framework

Main Theorem 1.1: Let $K \in C(D \times E)$ admit analytic continuation such that $K \in C(D \times F')$ and for each $x \in D$, $K(x, \cdot)$ is analytic in $F'$. Then for $n = 1,2,3,\ldots$, there exists a rank-$n$ kernel function $K_n \in C(D \times E)$ satisfying:

$\|K - K_n\|_{L^2_\mu(E) \to L^2_\lambda(D)} \leq Z_n(L^2_\mu(E), L^p_\nu(F)) \|K'\|_{H^p_\nu(F) \to L^2_\lambda(D)}$

where $Z_n(L^2_\mu(E), L^p_\nu(F))$ is the Cauchy-Zolotarev number:

$Z_n(L^2_\mu(E), L^p_\nu(F)) = \inf_{\phi \in \mathcal{R}_n} \left\|\frac{\phi(z)^{-1}\phi(y)}{y-z}\right\|_{L^2_\mu(E) \to L^p_\nu(F)}$

Key Technical Components

1. Operator Decomposition: Establishes decomposition $K = K' \circ C$ through the Cauchy integral formula, where:
   • $C$: Cauchy transform operator, $C[g](z) = \int_E \frac{g(y)}{y-z} d\mu(y)$
   • $K'$: Grothendieck dual operator, $K'[h](x) = \frac{1}{2\pi i} \int_\Gamma K(x,\xi)h(\xi)d\xi$
2. Cauchy-Zolotarev Numbers: A new concept combining classical Zolotarev numbers and the Cauchy transform, providing guarantees of exponential decay.
3. Rational Interpolation Construction: Low-rank approximation is constructed via Hermite integral formula: $K_n(x,y) = \frac{1}{2\pi i} \int_\Gamma K(x,\xi) \left(1 - \frac{\phi(y)}{\phi(\xi)}\right) \frac{1}{y-\xi} d\xi$

Technical Innovations

1. Exploitation of Analyticity: First systematic utilization of analytic properties of kernel functions to establish low-rank approximation theory
2. Displacement Structure Revelation: Reveals latent displacement structure of analytic kernel functions through Cauchy integral formula
3. Functional Analysis Tools: Introduces Grothendieck duality theory to numerical analysis, providing new analytical tools
4. Constructive Proof: The proof not only provides error bounds but also furnishes computable approximation methods

Experimental Setup

Test Matrix Types

1. Gamma Function Matrix: $A_{i,j} = \frac{\Gamma(i+j+1/2)}{\Gamma(i+j+1)}$
2. Cauchy Matrix: $A_{i,j} = \frac{1}{x_i + y_j}$
3. Log-Cauchy Matrix: $A_{i,j} = \log(x_i + y_j)$
4. Twisted Hankel Transform Matrix: $A_{i,j} = H^{(1)}_0(\omega_i \omega_j / \omega_{N+1}) e^{-i\omega_i \omega_j / \omega_{N+1}}$
5. Beta-Cauchy Matrix: $A_{i,j} = B(i+j+\alpha, \beta)$

Evaluation Metrics

• Relative error: $\|A - A_n\|_2 / \|A\|_2$
• Comparison with optimal singular values: $\sigma_{n+1}(A) / \sigma_1(A)$

Comparison Methods

1. Little-Reade Bound: Based on Chebyshev polynomial interpolation
2. Beckermann-Townsend Bound: Based on displacement structure
3. Optimal Singular Values: Theoretical best performance
4. Proposed Method: Theorem 1.1 bound and Zolotarev rational interpolation

Implementation Details

• Matrix size: typically $N = 50$ to $N = 100$
• Zolotarev rational functions computed via Trefethen-Wilber algorithm
• Barycentric form used for numerically stable rational interpolation evaluation

Experimental Results

Main Results

The proposed method significantly outperforms existing theoretical bounds across all test cases:

1. Gamma Function Matrix ($N=100$): New bound is approximately 6 orders of magnitude tighter than Little-Reade method, and 3 orders of magnitude tighter than Beckermann-Townsend method
2. Cauchy Matrix: Completely recovers Beckermann-Townsend results, validating theoretical correctness
3. Log-Cauchy Matrix: Zolotarev rational interpolation performs approximately 50 times better than methods based on classical Zolotarev numbers
4. Twisted Hankel Transform Matrix: Semi-discrete Zolotarev interpolation achieves near-optimal performance

Key Findings

1. Exponential Decay: All test cases exhibit exponential singular value decay
2. Achievable Bounds: Low-rank approximations constructed via rational interpolation nearly achieve theoretical bounds
3. Discrete Optimization: Zolotarev rational functions optimized on discrete point sets typically outperform continuous versions
4. Practical Utility: The method exhibits good numerical stability in practical applications

Ablation Studies

• Validates advantages of Cauchy-Zolotarev numbers over classical Zolotarev numbers
• Demonstrates importance of Grothendieck dual operator norms
• Compares effectiveness of different interpolation node selection strategies

Related Work

Main Research Directions

1. Smooth Kernel Function Theory: Methods by Little-Reade and others based on polynomial approximation
2. Displacement Structure Theory: Methods by Beckermann-Townsend and others based on Sylvester equations
3. Rational Approximation Theory: Zolotarev numbers and conformal mapping methods
4. Functional Analysis: Grothendieck duality theory and holomorphic function spaces

Advantages of This Work

1. More Precise Bounds: Exploits analyticity to obtain tighter error bounds than existing methods
2. Unified Framework: Handles both continuous and discrete cases simultaneously
3. Constructive Method: Provides computable optimal approximations
4. Theoretical Depth: Establishes deep connections with functional analysis

Conclusions and Discussion

Main Conclusions

1. Low-rank structure of analytic kernel functions can be precisely quantified through Cauchy integral formula and Zolotarev rational functions
2. Cauchy-Zolotarev numbers provide tighter error bounds than existing methods
3. Optimal low-rank approximations can be efficiently computed via rational interpolation
4. Grothendieck duality theory provides new theoretical tools for numerical analysis

Limitations

1. Analyticity Requirement: Method applies only to analytically continuable kernel functions
2. Zolotarev Computation: Computing optimal Zolotarev rational functions for general sets remains difficult
3. Higher-Order Singularities: Handling higher-order singularities like $(y-x)^{-2}$ requires Sobolev spaces
4. Algorithm Reliability: 90% reliability of Trefethen-Wilber algorithm limits practical applicability

Future Directions

1. Zolotarev Computation: Develop more reliable methods for computing Zolotarev rational functions on discrete sets
2. Higher-Order Singularities: Extend theory to Cauchy-Sobolev-Zolotarev numbers
3. Potential Theory Applications: Apply theory to potential-theoretic methods in analytic function approximation
4. Adaptive Algorithms: Develop adaptive interpolation strategies when set $F$ is unknown

In-Depth Evaluation

Strengths

1. Theoretical Innovation: First complete theoretical framework for low-rank approximation of analytic kernel functions
2. Practical Value: Provides computable algorithms with excellent performance on practical problems
3. Mathematical Depth: Skillfully combines tools from complex analysis, functional analysis, and numerical analysis
4. Comprehensive Experiments: Validates theory through multiple representative examples
5. Clear Presentation: Well-structured paper with rigorous mathematical derivations

Weaknesses

1. Limited Scope: Restricted to analytic kernel functions; not applicable to general smooth kernels
2. Computational Complexity: Computation of Zolotarev rational functions remains difficult in some cases
3. Numerical Stability: Analysis of numerical stability for ill-conditioned problems is insufficient
4. Parameter Selection: Choice of sets $E$ and $F$ significantly affects results but lacks systematic guidance

Impact

1. Theoretical Contribution: Provides new perspectives and tools for low-rank approximation theory
2. Application Prospects: Broad potential applications in scientific computing and data science
3. Interdisciplinary Bridge: Promotes cross-disciplinary fusion between numerical analysis and functional analysis
4. Algorithm Development: Provides new theoretical foundations for fast algorithm design

Applicable Scenarios

1. Scientific Computing: PDE solving, integral equation discretization
2. Data Science: Kernel methods, recommendation systems, image processing
3. Signal Processing: Fast transforms, filtering algorithms
4. Machine Learning: Kernel machine learning, Gaussian processes

References

The paper cites 35 important references covering classical works in complex analysis, functional analysis, numerical analysis, and scientific computing, particularly relevant literature on Zolotarev rational approximation theory, displacement structure theory, and Grothendieck duality theory.

This paper makes important contributions at both theoretical and practical levels, providing powerful tools for understanding and exploiting low-rank structure of analytic kernel functions. Despite certain limitations, its innovation and practical value make it a significant advance in the field.