Pour un ensemble compact F dans un espace linéaire normé et un entier n, la largeur n de Kolmogorov est la moindre erreur d'approximation au pire cas possible lorsqu'on projette les éléments de F sur n'importe quel sous-espace linéaire de dimension n ; formellement d_n(F)=inf_{V, dim V=n} sup_{f in F} dist(f,V).

Principe

Organiser la qualité d'approximation par l'erreur minimax sur tous les sous-espaces linéaires de dimension n : choisir le sous-espace linéaire qui minimise la distance maximale de F à ce sous-espace.

Démonstration

Approcher la boule unité d'un espace de Sobolev par un sous-espace polynomial de dimension n : la largeur n décroît à une vitesse fixée par la régularité et la dimension ambiante, donnant une borne concrète sur l'erreur en norme suprémum pour toutes les fonctions de la boule.

Mauvaise application

Employer la largeur n de Kolmogorov pour évaluer des schémas d'approximation non linéaires (réseaux de neurones, dictionnaires adaptatifs) comme s'ils étaient limités à des sous-espaces linéaires ; cela sous-estime la puissance des méthodes non linéaires.

Conséquence

Une petite largeur n implique que F peut être approximé uniformément par des modèles linéaires de faible dimension, conduisant à la compression, à la réduction de modèles et à des garanties d'erreur déterministes au pire cas pour les approximations linéaires.

Inversion

Inverser la perspective en fixant l'erreur d'approximation et en demandant le n minimal pour l'atteindre ; comparer avec les largeurs duales (par ex. largeurs de Gelfand) qui mesurent l'approximation via des fonctionnelles linéaires plutôt que par des sous-espaces.

Limite

S'applique uniquement aux sous-espaces linéaires et aux erreurs au pire cas (suprémum) dans une norme donnée ; les valeurs dépendent fortement de la norme, requièrent la compacité ou la précompacité de F pour être finies, et ne décrivent pas l'approximation aléatoire ou en moyenne.

Tension sémantique

Conflit avec des mesures d'approximation non linéaire (dimension de variété, largeurs non linéaires) et avec des notions duales comme les largeurs de Gelfand ; les termes proches peuvent confondre linéarité, erreur au pire versus en moyenne, ou dépendance à la norme ambiante.

Synthèse

La largeur n de Kolmogorov mesure la compressibilité linéaire au pire cas d'un ensemble compact dans une norme donnée : c'est l'infimum sur les sous-espaces de dimension n de la distance maximale de l'ensemble au sous-espace, fournissant une mesure précise du pouvoir d'approximation linéaire.