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

Resumo Técnico: A Pilha de Extremos como Estatística Suficiente Mínima para Funcionais Independentes de Taxa

Enunciado do Problema
O artigo aborda a questão fundamental da compressão de dados para sequências governadas por funcionais independentes de taxa. Um funcional $F$ é independente de taxa se sua saída depende exclusivamente da sequência de extremos locais da entrada, e não do espaçamento temporal, da velocidade de variação ou dos valores absolutos em pontos não extremos. Essa propriedade é central para a modelagem de fenômenos como histerese ferromagnética, sistemas elastoplásticos e modelos financeiros de limiar.

Embora seja estabelecido que a pilha de extremos ($\Pi_n$)—uma sequência alternada de máximos e mínimos locais mantida em uma ordem específica—é uma estatística suficiente para funcionais de Preisach, permanecia uma questão em aberto se essa representação é mínima. Especificamente, existe uma representação estritamente mais curta que possa responder a todas as consultas para a classe $\mathcal{R}$ de funcionais computáveis, causais e independentes de taxa? Além disso, afirmações informais anteriores sugeriam que a sobrecarga do uso da pilha era $O(\log n)$ ou $O(\log K(\Pi_n))$, mas os limites precisos de complexidade de Kolmogorov não haviam sido rigorosamente estabelecidos.

Metodologia
O autor emprega a teoria da complexidade de Kolmogorov para quantificar o conteúdo de informação necessário para representar uma sequência $u_{0:n}$ de modo que qualquer funcional na classe $\mathcal{R}$ possa ser computado.

• Definições: O artigo define $K_R(u_{0:n})$ como o comprimento do programa mais curto que, dado qualquer $F \in \mathcal{R}$, computa $F[u](n)$. A pilha de extremos $\Pi_n$ é definida como uma sequência de pares $(M_i, m_i)$ representando extremos locais sobreviventes, atualizada por meio de um mecanismo de "apagamento" onde novos extremos apagam extremos menores e mais antigos.
• Prova de Suficiência: O limite superior é derivado da clássica propriedade de apagamento do operador de histerese de Preisach. Como a saída de qualquer funcional independente de taxa depende apenas de $\Pi_n$, uma função computável fixa pode mapear $\Pi_n$ para a saída do funcional.
• Prova de Minimalidade: Para provar que nenhuma representação mais curta existe, o autor constrói uma família indicadora finita de funcionais. Para cada par possível de valores de grade $(M, m)$, é definido um funcional indicador $F_{(M,m)}$ que retorna 1 se $(M, m)$ estiver presente na pilha $\Pi_n$ e 0 caso contrário. O artigo demonstra que qualquer representação capaz de responder a todas as consultas em $\mathcal{R}$ deve, por necessidade, permitir a reconstrução da pilha completa $\Pi_n$ por meio desses indicadores.

Principais Contribuições

1. Suficiência Mínima: O artigo prova que a pilha de extremos $\Pi_n$ é uma estatística suficiente mínima para a classe $\mathcal{R}$. Estabelece que qualquer compressão sem perdas que preserve a capacidade de responder a todas as consultas independentes de taxa deve reter pelo menos $K(\Pi_n) - O(1)$ bits.
2. Limites de Complexidade Apertados: Os autores estabelecem a relação precisa de complexidade de Kolmogorov:
   $$K(\Pi_n) - O(1) \le K_R(u_{0:n}) \le K(\Pi_n) + O(1)$$
   Isso corrige e aperta os limites informais anteriores de $O(\log n)$ ou $O(\log K(\Pi_n))$. A sobrecarga de $O(1)$ é mostrada como independente do comprimento da sequência $n$ e da profundidade da pilha $k$.
3. Justificativa Teórica para Compressão: O resultado fornece uma garantia formal de otimalidade para algoritmos de compressão baseados em pilha (denominados PSTACK). Diferentemente dos métodos padrão de compressão de séries temporais (por exemplo, PAA, SAX, PLR), que oferecem garantias heurísticas ou de aproximação $L_p$, a abordagem baseada em pilha é assintoticamente ótima para a classe específica de funcionais independentes de taxa.

Resultados

• Limite Superior: O comprimento do programa mais curto que responde a todas as consultas $\mathcal{R}$ é limitado superiormente por $K(\Pi_n) + O(1)$. Isso decorre do teorema da invariância prefixada, uma vez que o mapeamento de $\Pi_n$ para qualquer $F[u](n)$ é uma função computável fixa.
• Limite Inferior: O comprimento é limitado inferiormente por $K(\Pi_n) - O(1)$. Isso é provado mostrando que a representação ótima $R(u_{0:n})$ permite a reconstrução de $\Pi_n$ por meio de uma função computável $\Phi$ aplicada à família indicadora. Como $\Pi_n$ pode ser recuperado da representação, a representação não pode ser significativamente mais curta que a complexidade da própria pilha.
• Eficiência Algorítmica: O artigo observa que a pilha pode ser mantida em tempo amortizado $O(1)$ por passo com espaço $O(k)$, onde $k$ é a profundidade atual da pilha.

Significado e Alegações
O artigo alega que a pilha de extremos não é meramente uma estrutura de dados conveniente, mas é necessária do ponto de vista da teoria da informação para processamento independente de taxa.

• Otimalidade: A representação baseada em pilha é assintoticamente ótima. Qualquer tentativa de comprimir ainda mais um fluxo guiado por histerese, preservando a classe completa de consultas independentes de taxa, resultaria em perda de informação.
• Independência do Comprimento da Sequência: A sobrecarga de $O(1)$ implica que, para sinais com longas corridas monótonas (pequeno $k$ em relação a $n$), a taxa de compressão $n/k$ pode ser arbitrariamente grande sem aumentar a lacuna de otimalidade.
• Escopo: Os resultados aplicam-se especificamente a sequências discretas sobre uma grade finita $G_L$. O artigo observa explicitamente que, sobre os reais contínuos $\mathbb{R}$, a família indicadora seria não enumerável, e o framework de Kolmogorov não se aplicaria diretamente.

O trabalho conclui que o mecanismo de "apagamento" inerente ao operador de Preisach não é apenas uma curiosidade física ou matemática, mas representa o limite fundamental de retenção de informação para sistemas independentes de taxa.