High-dimensional sparse trigonometric approximation in the uniform norm and consequences for sampling recovery

Imaginez que vous essayez de décrire une ville massive et chaotique à un ami qui n'en a jamais vu. Vous disposez d'un temps limité et de seulement quelques phrases pour le faire. Si vous essayez de décrire chaque bâtiment, chaque rue et chaque personne, vous aurez épuisé votre temps avant même d'avoir atteint le premier pâté de maisons. C'est la « malédiction de la dimensionnalité ». Dans le monde des mathématiques et des sciences, lorsque nous essayons de comprendre des choses avec de nombreuses variables différentes (comme la température, l'humidité, la vitesse du vent et le temps, tout cela en même temps), la quantité d'informations nécessaires pour obtenir une image parfaite explose généralement, croissant si vite qu'il devient impossible de la gérer.

Cependant, beaucoup de signaux du monde réel ne sont pas des désordres chaotiques ; ils sont « parcimonieux » (ou « sparses »). Pensez à une ville qui est principalement composée de champs vides avec seulement quelques points de repère clés. Si vous savez que la ville est parcimonieuse, vous n'avez pas besoin de décrire chaque champ vide ; vous devez simplement trouver les points de repère. Ce document s'inscrit dans le domaine de la théorie de l'approximation, qui est essentiellement la science des meilleurs raccourcis possibles. Elle pose la question suivante : si nous avons une fonction multidimensionnelle complexe (une description mathématique d'une forme ou d'un signal), comment pouvons-nous la reconstruire en utilisant seulement une infime poignée de ses parties les plus importantes ? Plus précisément, les auteurs étudient l'approximation trigonométrique, qui revient à reconstruire une onde sonore ou une image complexe en utilisant seulement quelques notes de musique ou couleurs spécifiques, plutôt que tout le spectre. L'objectif est de voir si nous pouvons maintenir l'efficacité de ces raccourcis même lorsque le nombre de variables (les dimensions) devient énorme, sans que les mathématiques ne s'effondrent.

Les auteurs de cet article, Moritz Moeller, Serhii Stasyuk et Tino Ullrich, s'attaquent à un problème délicat : ils veulent savoir à quel point nous pouvons approximer ces formes complexes de haute dimension en utilisant le plus petit nombre possible de « notes » (termes) tout en garantissant que le résultat respecte une marge d'erreur spécifique dans chaque détail, et non seulement en moyenne. En termes mathématiques, ils s'intéressent à la norme uniforme, ce qui signifie que l'erreur doit être faible partout, et pas seulement en moyenne. Ils se concentrent sur un type spécifique d'espace mathématique appelé classes de Wiener, où les « notes » de la fonction décroissent suffisamment vite pour être considérées comme parcimonieuses.

Voici ce qu'ils ont trouvé : ils ont prouvé que pour ces types spécifiques de fonctions, on peut effectivement obtenir une reconstruction très précise en utilisant un nombre étonnamment faible de termes, même lorsque la dimension $d$ est grande. Le nombre de termes dont vous avez besoin, appelons-le $m$, n'a pas besoin de croître de manière exponentielle avec la dimension (ce qui serait un désastre). Au lieu de cela, il croît de manière gérable. Plus précisément, pour obtenir un certain niveau de précision (disons une erreur de $\varepsilon$), le nombre de termes $m$ évolue au plus de façon quadratique par rapport à l'inverse de la précision ($1/\varepsilon$), bien que le taux exact dépende également d'un paramètre $\theta$ qui définit la parcimonie de la classe de fonctions.

L'article fournit des formules précises. Par exemple, si vous travaillez avec une classe de fonctions spécifique définie par un paramètre $\theta$ (où $0 < \theta \le 1$), l'erreur obtenue avec $m$ termes chute à un taux de $m^{-(1/\theta - 1/2)}$. C'est un très bon taux. Les auteurs ont également calculé les constantes exactes de ces formules, montrant que l'influence de la dimension $d$ est maîtrisée, apparaissant principalement comme un terme logarithmique inoffensif (comme $\log(d)$) plutôt que comme un terme exponentiel effrayant.

Pour obtenir ces résultats, l'équipe a utilisé une stratégie astucieuse en deux étapes. Premièrement, ils ont examiné le problème dans un cadre plus « souple » (la norme $L_q$, qui est une erreur moyenne) où les mathématiques sont plus faciles, et ils ont prouvé que les constantes ne s'envolent pas à mesure que la dimension augmente. Ensuite, ils ont utilisé une version raffinée d'un outil classique appelé inégalité de Nikol'skii pour « extrapoler » ces résultats à la « norme uniforme » (l'erreur dans le pire des cas). Cette étape a été cruciale car elle leur a permis de montrer que, même dans le sens le plus strict, la dimension $d$ n'ajoute qu'une petite pénalité logarithmique à la taille du spectre (la plage de fréquences utilisées), plutôt que de tout gâcher.

L'article fait également le lien avec la récupération par échantillonnage (sampling recovery), qui est le problème pratique de la reconstruction d'une fonction à partir d'un nombre limité de mesures (comme prendre quelques photos d'un objet en 3D). Ils montrent que, puisque leur approximation parcimonieuse fonctionne si bien, on peut récupérer ces fonctions de haute dimension à partir d'un nombre limité d'échantillons en utilisant une technique appelée minimisation de la norme $\ell_1$ (une méthode populaire en détection compressée ou « compressed sensing »). Le résultat est que, pour ces classes de fonctions spécifiques, le problème est « traitable », ce qui signifie qu'il est soluble en un temps raisonnable et avec une quantité de données raisonnable, même lorsque le nombre de variables augmente.

Une chose que l'article note avec prudence est que ces résultats nets et spécifiques s'appliquent aux fonctions possédant un certain type de parcimonie (la condition de sommabilité $\ell_1$). Si les fonctions ne possèdent pas cette structure spécifique, ou si l'on examine différents types d'espaces de régularité (comme ceux avec $\theta = \infty$), les mathématiques deviennent plus complexes, et l'on pourrait voir apparaître des facteurs logarithmiques supplémentaires. Mais pour les classes qu'ils ont étudiées, la « malédiction de la dimensionnalité » est effectivement domptée. Ils n'ont pas seulement deviné cela ; ils ont fourni des preuves mathématiques rigoureuses avec des constantes explicites, montrant exactement comment l'erreur se comporte. Par exemple, ils ont montré que pour un cas spécifique impliquant des espaces de Besov à régularité mixte, l'erreur dans la norme uniforme est bornée par une formule impliquant $d \log(d)$ et un taux de décroissance de $m^{-1/2}$, prouant que l'impact de la dimension est bien moins sévère que redouté auparavant pour ces types de signaux.

En bref, cet article est une victoire pour l'efficacité des mathématiques de haute dimension. Il prouve que si un signal est suffisamment parcimonieux, nous n'avons pas à craindre le nombre de variables. Nous pouvons extraire les quelques notes les plus importantes pour reconstruire la chanson entière, et les mathématiques garantissent que nous n'aurons pas besoin d'un million de notes simplement parce que la chanson possède un million de dimensions. Les auteurs nous ont donné la carte précise de combien de notes nous avons besoin et de la manière dont la taille de la ville (la dimension) affecte le voyage, garantissant que le chemin reste praticable à mesure que la ville grandit.