Ensembles d'algorithmes et de méthodes qui reconstruisent un polynôme (univarié ou multivarié) supposé ne comporter que peu de termes non nuls à partir de ses évaluations, en exploitant la parcimonie pour réduire le nombre d'échantillons et les opérations par rapport à l'interpolation dense.

Principe

Exploiter l'hypothèse que le polynôme cible a un support petit (peu de monômes) pour transformer les données d'évaluation en un système structuré linéaire ou non linéaire (de type Prony, résultante parcimonieuse, approches inspirées du compressed sensing) qui identifie les exposants des monômes et les coefficients correspondants avec beaucoup moins de sondes que les méthodes denses basées sur le degré.

Démonstration

Pour un polynôme univarié à au plus t termes non nuls et de degré ≤ n, les méthodes de type Prony/Borodin–Tiwari retrouvent les positions d'exposants et les coefficients à partir de O(t log n) évaluations judicieusement choisies, souvent en formant une matrice de Hankel/Toeplitz et en calculant son noyau ou en résolvant un système de type Vandermonde ; pour les polynômes multivariés on peut recourir à la substitution de Kronecker ou aux résultantes multivariées parcimonieuses, en reconnaissant une difficulté combinatoire accrue et le recours fréquent à la randomisation pour réduire les variables.

Mauvaise application

Supposer la parcimonie alors que le polynôme n'est pas parcimonieux conduit à un échec de reconstruction ou à un modèle incorrect ; utiliser trop peu d'échantillons par rapport à la parcimonie réelle, ou appliquer un algorithme parcimonieux sans tenir compte du bruit ou des coefficients approximatifs, produit des reconstructions instables ou erronées. Traiter l'interpolation parcimonieuse comme une boîte noire sans bornes sur le degré ou le support engendre des ambiguïtés.

Conséquence

Une interpolation parcimonieuse correcte réduit fortement la complexité d'échantillonnage et de calcul quand la parcimonie est vraie, permettant la récupération avec beaucoup moins d'évaluations et produisant des représentations compactes interprétables ; toutefois les gains diminuent ou disparaissent si l'hypothèse de parcimonie est violée ou si le bruit/arrondi est significatif.

Inversion

Interpolation dense : ignorer la parcimonie et utiliser des méthodes classiques (Newton, Lagrange, évaluation multi-points ou approches fondées sur les bases de Gröbner) qui exigent O(n) échantillons pour un polynôme de degré n et fournissent des coefficients pour tous les monômes jusqu'au degré, échangeant la parcimonie contre une stabilité et une simplicité plus uniformes.

Limite

Nécessite un modèle de parcimonie valide (t connu ou majoré), des points d'évaluation appropriés (évitant les dégénérescences) et souvent de l'arithmétique exacte ou un modèle de bruit robuste ; les problèmes multivariés impliquent une complexité combinatoire plus importante et peuvent nécessiter des projections de variables ou des décalages aléatoires pour éviter les collisions d'exposants.

Tension sémantique

Tension entre l'approche algébrique de reconstruction par interpolation parcimonieuse et les approches du compressed sensing issues du traitement du signal : toutes exploitent la parcimonie mais divergent sur les domaines de coefficients autorisés, les modèles de bruit, les garanties déterministes vs probabilistes et sur la structure algébrique des exposants monomiaux vs matrices de détection génériques.

Synthèse

L'interpolation parcimonieuse regroupe les stratégies de reconstruction qui troquent la parcimonie du modèle (peu de monômes actifs) contre une complexité d'échantillonnage et de calcul beaucoup moindre en convertissant les évaluations en systèmes algébriques structurés dont la résolution révèle le support des exposants et les coefficients, le succès dépendant de bornes de parcimonie exactes, de sondes appropriées et d'un traitement du bruit.