The Extremum Stack is a Minimal Sufficient Statistic for Rate-Independent Functionals: A Kolmogorov Complexity Characterisation

Resumen Técnico: La Pila de Extremos como Estadístico Suficiente Mínimo para Funcionales Independientes de la Tasa

Enunciado del Problema
El artículo aborda la pregunta fundamental de la compresión de datos para secuencias gobernadas por funcionales independientes de la tasa. Un funcional $F$ es independiente de la tasa si su salida depende únicamente de la secuencia de extremos locales de la entrada, en lugar de depender del espaciado temporal, la velocidad de cambio o los valores absolutos en puntos no extremales. Esta propiedad es central para modelar fenómenos como la histéresis ferromagnética, los sistemas elasto-plásticos y los modelos financieros de umbrales.

Aunque está establecido que la pila de extremos ($\Pi_n$)—una secuencia alternada de máximos y mínimos locales mantenida en un orden específico—es un estadístico suficiente para los funcionales de Preisach, permaneció como una cuestión abierta si esta representación es mínima. Específicamente, ¿existe una representación estrictamente más corta que pueda responder a todas las consultas para la clase $\mathcal{R}$ de funcionales independientes de la tasa, computables y causales? Además, afirmaciones informales previas sugerían que la sobrecarga de usar la pila era $O(\log n)$ u $O(\log K(\Pi_n))$, pero los límites precisos de la complejidad de Kolmogorov no habían sido establecidos rigurosamente.

Metodología
El autor emplea la teoría de la complejidad de Kolmogorov para cuantificar el contenido de información requerido para representar una secuencia $u_{0:n}$ de tal manera que cualquier funcional en la clase $\mathcal{R}$ pueda ser computado.

• Definiciones: El artículo define $K_R(u_{0:n})$ como la longitud del programa más corto que, dado cualquier $F \in \mathcal{R}$, computa $F[u](n)$. La pila de extremos $\Pi_n$ se define como una secuencia de pares $(M_i, m_i)$ que representan extremos locales supervivientes, actualizada mediante un mecanismo de "borrado" donde nuevos extremos eliminan a extremos más pequeños y antiguos.
• Prueba de Suficiencia: El límite superior se deriva de la propiedad de borrado clásica del operador de histéresis de Preisach. Dado que la salida de cualquier funcional independiente de la tasa depende únicamente de $\Pi_n$, una función computable fija puede mapear $\Pi_n$ a la salida del funcional.
• Prueba de Minimalidad: Para probar que no existe una representación más corta, el autor construye una familia indicadora finita de funcionales. Para cada par posible de valores de la cuadrícula $(M, m)$, se define un funcional indicador $F_{(M,m)}$ que devuelve 1 si $(M, m)$ está presente en la pila $\Pi_n$ y 0 en caso contrario. El artículo demuestra que cualquier representación capaz de responder a todas las consultas en $\mathcal{R}$ debe, por necesidad, permitir la reconstrucción de la pila completa $\Pi_n$ mediante estos indicadores.

Contribuciones Clave

1. Suficiencia Mínima: El artículo prueba que la pila de extremos $\Pi_n$ es un estadístico suficiente mínimo para la clase $\mathcal{R}$. Establece que cualquier compresión sin pérdida que preserve la capacidad de responder a todas las consultas independientes de la tasa debe retener al menos $K(\Pi_n) - O(1)$ bits.
2. Límites de Complejidad Ajustados: Los autores establecen la relación precisa de complejidad de Kolmogorov:
   $$K(\Pi_n) - O(1) \le K_R(u_{0:n}) \le K(\Pi_n) + O(1)$$
   Esto corrige y ajusta los límites informales previos de $O(\log n)$ u $O(\log K(\Pi_n))$. Se demuestra que la sobrecarga $O(1)$ es independiente de la longitud de la secuencia $n$ y de la profundidad de la pila $k$.
3. Justificación Teórica para la Compresión: El resultado proporciona una garantía formal de optimalidad para algoritmos de compresión basados en pilas (denominados PSTACK). A diferencia de los métodos estándar de compresión de series temporales (por ejemplo, PAA, SAX, PLR) que ofrecen garantías heurísticas o de aproximación $L_p$, el enfoque basado en pilas es asintóticamente óptimo para la clase específica de funcionales independientes de la tasa.

Resultados

• Límite Superior: La longitud del programa más corto que responde a todas las consultas $\mathcal{R}$ está acotada superiormente por $K(\Pi_n) + O(1)$. Esto se sigue del teorema de invariancia libre de prefijos, ya que el mapeo de $\Pi_n$ a cualquier $F[u](n)$ es una función computable fija.
• Límite Inferior: La longitud está acotada inferiormente por $K(\Pi_n) - O(1)$. Esto se prueba mostrando que la representación óptima $R(u_{0:n})$ permite la reconstrucción de $\Pi_n$ mediante una función computable $\Phi$ aplicada a la familia indicadora. Dado que $\Pi_n$ puede recuperarse de la representación, la representación no puede ser significativamente más corta que la complejidad de la pila en sí misma.
• Eficiencia Algorítmica: El artículo señala que la pila puede mantenerse en tiempo amortizado $O(1)$ por paso con un espacio $O(k)$, donde $k$ es la profundidad actual de la pila.

Significado y Afirmaciones
El artículo afirma que la pila de extremos no es meramente una estructura de datos conveniente, sino que es necesaria desde el punto de vista de la teoría de la información para el procesamiento independiente de la tasa.

• Optimalidad: La representación basada en pilas es asintóticamente óptima. Cualquier intento de comprimir aún más un flujo impulsado por histéresis mientras se preserva la clase completa de consultas independientes de la tasa resultaría en pérdida de información.
• Independencia de la Longitud de la Secuencia: La sobrecarga $O(1)$ implica que para señales con corridas monótonas largas (pequeño $k$ en relación con $n$), la relación de compresión $n/k$ puede ser arbitrariamente grande sin aumentar la brecha de optimalidad.
• Alcance: Los resultados se aplican específicamente a secuencias discretas sobre una cuadrícula finita $G_L$. El artículo señala explícitamente que sobre los reales continuos $\mathbb{R}$, la familia indicadora sería no numerable, y el marco de Kolmogorov no se aplicaría directamente.

El trabajo concluye que el mecanismo de "borrado" inherente al operador de Preisach no es solo una curiosidad física o matemática, sino que representa el límite fundamental de la retención de información para sistemas independientes de la tasa.