Low-rank approximation of analytic kernels

Résumé technique : Approximation de rang faible de noyaux analytiques

Énoncé du problème
De nombreuses matrices et de nombreux noyaux dans le calcul scientifique et la science des données présentent une structure « presque de rang faible », ce qui signifie qu'ils peuvent être bien approximés par des matrices de rang faible dans diverses normes. Comprendre les fondements théoriques de cette structure est essentiel pour l'analyse et le développement d'algorithmes de haute performance. Bien que les explications existantes reposent sur l'approximation de fonctions lisses par des polynômes (produisant une décroissance exponentielle basée sur les ellipses de Bernstein) ou sur la structure de déplacement (via les équations de Sylvester), ces approches produisent souvent des bornes d'erreur pessimistes ou ne parviennent pas à exploiter pleinement les propriétés analytiques du noyau. Plus précisément, les bornes actuelles basées sur l'interpolation polynomiale décroissent à un taux déterminé par la plus grande ellipse de Bernstein, ce qui peut être nettement inférieur au taux de convergence réel réalisable par l'approximation rationnelle.

Méthodologie
L'article introduit un nouveau cadre pour borner l'erreur d'approximation de rang faible des matrices issues d'échantillons d'un noyau $K(x,y)$ qui est prolongable analytiquement en une variable (disons $y$) d'un ensemble compact $E$ vers un grand ensemble ouvert contenant un ensemble compact disjoint $F$.

Le cœur de la méthodologie est une décomposition d'opérateur dérivée de la formule intégrale de Cauchy :
$$K = K' \mathcal{C}$$
où :

1. $\mathcal{C}$ est un opérateur de transformée de Cauchy reliant $L^2_\mu(E)$ à un espace de fonctions analytiques $H(F)$.
2. $K'$ est un opérateur « dual de Grothendieck » reliant $H(F)$ à $C(D)$. Cet opérateur traduit les singularités de $K(x, \cdot)$ dans $F$ en une action (telle que l'évaluation, la dérivation ou la convolution) sur des fonctions définies sur $F$.

L'approximation de rang faible $K_n$ est construite en approximant la transformée de Cauchy $\mathcal{C}$ par un opérateur de rang $n$, $\mathcal{C}_n$. Le noyau de $\mathcal{C}_n$ est dérivé d'une fonction rationnelle $\phi \in R_n$ (fonctions rationnelles de type $(n,n)$). La borne d'erreur est régie par les nombres de Cauchy–Zolotarev, définis par :
$$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)}$$
Ces nombres décroissent exponentiellement avec $n$, avec un taux déterminé par le module conforme $\rho(E,F)$, qui quantifie la séparation entre $E$ et $F$.

La construction de l'approximateur $K_n$ est montrée comme étant équivalente à l'interpolation rationnelle du noyau $K(x, \cdot)$. Les nœuds et les pôles d'interpolation sont les racines et les pôles de la fonction rationnelle optimale $\phi$ qui minimise le nombre de Cauchy–Zolotarev. Pour des géométries spécifiques (par exemple, des intervalles disjoints), ces fonctions optimales sont les fonctions rationnelles de Zolotarev classiques.

Contributions clés

1. Cadre théorique : L'article établit le Théorème 1.1, fournissant une borne sur l'erreur d'approximation de rang faible impliquant les nombres de Cauchy–Zolotarev et la norme de l'opérateur dual de Grothendieck $K'$. Cela unifie les noyaux continus et les matrices/tenseurs discrets sous un cadre unique.
2. Taux de convergence supérieurs : La théorie démontre que le taux de convergence est contrôlé par le module conforme $\rho(E,F)$, qui est souvent significativement plus grand que le paramètre de la plus grande ellipse de Bernstein utilisé dans les bornes d'interpolation polynomiale. Cela explique pourquoi les approximations rationnelles surpassent souvent les approximations polynomiales pour les noyaux analytiques.
3. Algorithme constructif : La preuve est constructive, montrant que l'approximateur de rang faible optimal est un interpolant rationnel. Les nœuds et les pôles d'interpolation sont explicitement identifiés comme les racines et les pôles de la fonction rationnelle de Zolotarev optimale.
4. Structure de déplacement via la dualité : Ce travail révèle une structure de déplacement latente dans les noyaux analytiques à travers le prisme de la dualité de Grothendieck, connectant les propriétés de prolongement analytique du noyau à la résolubilité des équations de déplacement.
5. Gestion des singularités : Le cadre accepte les cas où la transformée de Cauchy est non bornée (par exemple, $L^2 \to L^1$) en utilisant l'opérateur dual de Grothendieck, à condition que $n \ge 1$.

Résultats
L'article valide la théorie par des exemples numériques :

• Matrices Gamma/Hankel : Pour la matrice $A_{i,j} = \Gamma(i+j+1/2)/\Gamma(i+j+1)$, les nouvelles bornes (Théorème 1.1) et les interpolants rationnels correspondants surpassent de manière significative les bornes existantes basées sur l'interpolation polynomiale (Little–Reade) et la structure de déplacement (Beckermann–Townsend). La décroissance de l'erreur correspond étroitement aux valeurs singulières de la matrice.
• Matrices et tenseurs de Cauchy : Le cadre récupère les résultats optimaux connus pour les matrices de Cauchy et les étend aux tenseurs de Cauchy, confirmant que l'erreur est bornée par le nombre de Zolotarev des ensembles sous-jacents.
• Matrices Log-Cauchy et Hankel tordues : La théorie parvient à borner l'erreur pour les noyaux présentant des singularités logarithmiques et des transformées de Hankel, où l'opérateur dual de Grothendieck implique l'intégration ou des pondérations spécifiques.
• Matrices Beta-Cauchy : L'approche est appliquée à des matrices issues d'un changement de base entre polynômes orthogonaux, montrant que l'interpolation rationnelle avec les nœuds de Zolotarev atteint les bornes théoriques.

Dans tous les cas, les approximations rationnelles calculables (utilisant les nœuds et pôles de Zolotarev) atteignent les bornes d'erreur théoriques, et la décroissance de l'erreur est exponentielle avec un taux déterminé par la séparation des ensembles de domaine et de singularité.

Signification
L'article affirme que ce cadre fournit une caractérisation plus précise et souvent plus serrée de l'approximabilité de rang faible pour les noyaux analytiques que les méthodes précédentes. En déplaçant l'attention de l'interpolation polynomiale (ellipses de Bernstein) vers l'interpolation rationnelle (module conforme), la théorie explique la performance supérieure des approximations rationnelles en pratique. L'introduction de l'opérateur dual de Grothendieck permet un traitement unifié des noyaux avec diverses structures de singularités, y compris ceux où la transformée de Cauchy est non bornée. De plus, la nature constructive de la preuve mène à des algorithmes rapides pour construire ces approximations en utilisant l'interpolation rationnelle avec des pôles prescrits, limitée uniquement par la capacité de calculer les fonctions de Zolotarev optimales pour les ensembles spécifiques impliqués. Le travail suggère que les améliorations futures du calcul des fonctions de Zolotarev pour des ensembles discrets pourraient encore accroître l'utilité pratique de ces bornes.