Conjuntos de algoritmos y métodos que reconstruyen un polinomio (univariante o multivariante) que se asume tiene pocos términos no nulos a partir de sus evaluaciones, explotando la esparsidad para reducir el número de muestras y operaciones respecto a la interpolación densa.

Principio

Aprovechar la hipótesis de que el polinomio objetivo tiene un soporte pequeño (pocos monomios) para transformar los datos de evaluación en un sistema estructurado lineal o no lineal (tipo Prony, resultantes esparsas, enfoques inspirados en compressed sensing) que identifica exponentes de monomios y coeficientes con muchas menos sondas que los métodos densos basados en el grado.

Demostración

Para un polinomio univariante con a lo sumo t términos no nulos y grado ≤ n, métodos tipo Prony/Borodin–Tiwari recuperan posiciones de exponentes y coeficientes a partir de O(t log n) evaluaciones cuidadosamente elegidas, a menudo formando una matriz de Hankel/Toeplitz y calculando su núcleo o resolviendo un sistema tipo Vandermonde; para polinomios multivariantes se puede usar sustitución de Kronecker o técnicas de resultantes multivariantes esparsas, reconociendo la mayor dificultad combinatoria y la frecuente necesidad de aleatorización para reducir variables.

Aplicación incorrecta

Asumir esparsidad cuando el polinomio no es esparso conduce a fallos de recuperación o modelos incorrectos; usar muy pocas muestras en relación con la esparsidad real, o aplicar un algoritmo esparso sin considerar ruido o coeficientes aproximados, produce reconstrucciones inestables o erróneas. Tratar la interpolación esparsa como una caja negra sin límites de grado o soporte genera ambigüedad.

Consecuencia

La interpolación esparsa correcta reduce drásticamente la complejidad de muestreo y cómputo cuando la esparsidad se cumple, permitiendo la recuperación con muchas menos evaluaciones y produciendo representaciones compactas interpretables; no obstante, las ventajas disminuyen o desaparecen si la hipótesis de esparsidad falla o si el ruido/errores de redondeo son significativos.

Inversión

Interpolación densa: ignorar la esparsidad y usar métodos clásicos (Newton, Lagrange, evaluación multipunto o enfoques basados en bases de Gröbner) que requieren O(n) muestras para polinomios de grado n y devuelven coeficientes para todos los monomios hasta el grado, a cambio de estabilidad y sencillez uniformes.

Límite

Requiere un modelo de esparsidad válido (t conocido o acotado), puntos de evaluación adecuados (evitando degeneraciones) y a menudo aritmética exacta o un modelo de ruido robusto; los problemas multivariantes imponen mayor complejidad combinatoria y pueden necesitar proyecciones de variables o desplazamientos aleatorios para evitar colisiones de exponentes.

Tensión semántica

Existe tensión entre la interpolación esparsa como problema algebraico de reconstrucción y los enfoques de compressed sensing procedentes del procesamiento de señales: ambos explotan esparsidad pero difieren en dominios de coeficientes, modelos de ruido, garantías deterministas frente a probabilísticas y en la estructura algebraica de exponentes frente a matrices de medida genéricas.

Síntesis

La interpolación esparsa agrupa estrategias de reconstrucción que cambian la parsimonia del modelo (pocos monomios activos) por costes mucho menores de muestreo y cálculo al convertir evaluaciones en sistemas algebraicos estructurados cuya solución revela soporte de exponentes y coeficientes, con éxito condicionado a cotas de esparsidad exactas, sondas apropiadas y manejo del ruido.