## [Interpolación Esparsa](/es/node/63569) Definición 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 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 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 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 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 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 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 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 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.