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

Riepilogo Tecnico: Lo Stack degli Estremi come Statistica Sufficiente Minima per Funzionali Indipendenti dalla Velocità

Enunciato del Problema
Il lavoro affronta la questione fondamentale della compressione dei dati per sequenze governate da funzionali indipendenti dalla velocità. Un funzionale $F$ è indipendente dalla velocità se il suo output dipende esclusivamente dalla sequenza degli estremi locali dell'input, piuttosto che dalla spaziatura temporale, dalla velocità di variazione o dai valori assoluti nei punti non estremali. Questa proprietà è centrale nella modellazione di fenomeni quali l'isteresi ferromagnetica, i sistemi elastoplastici e i modelli finanziari basati su soglie.

Sebbene sia stabilito che lo stack degli estremi ($\Pi_n$)—una sequenza alternata di massimi e minimi locali mantenuta in un ordine specifico—sia una statistica sufficiente per i funzionali di Preisach, rimaneva una questione aperta se tale rappresentazione fosse minima. Nello specifico, esiste una rappresentazione strettamente più breve in grado di rispondere a tutte le interrogazioni per la classe $\mathcal{R}$ dei funzionali indipendenti dalla velocità, computabili e causali? Inoltre, precedenti affermazioni informali suggerivano che il sovraccarico dell'uso dello stack fosse $O(\log n)$ o $O(\log K(\Pi_n))$, ma i limiti precisi della complessità di Kolmogorov non erano stati rigorosamente stabiliti.

Metodologia
L'autore impiega la teoria della complessità di Kolmogorov per quantificare il contenuto informativo necessario a rappresentare una sequenza $u_{0:n}$ tale che qualsiasi funzionale nella classe $\mathcal{R}$ possa essere calcolato.

• Definizioni: Il lavoro definisce $K_R(u_{0:n})$ come la lunghezza del programma più breve che, dato un qualsiasi $F \in \mathcal{R}$, calcola $F[u](n)$. Lo stack degli estremi $\Pi_n$ è definito come una sequenza di coppie $(M_i, m_i)$ che rappresentano gli estremi locali sopravvissuti, aggiornati tramite un meccanismo di "cancellazione" (wiping) in cui nuovi estremi cancellano quelli più piccoli e precedenti.
• Dimostrazione della Sufficienza: Il limite superiore è derivato dalla classica proprietà di cancellazione (wiping property) dell'operatore di isteresi di Preisach. Poiché l'output di qualsiasi funzionale indipendente dalla velocità dipende solo da $\Pi_n$, una funzione computabile fissa può mappare $\Pi_n$ nell'output del funzionale.
• Dimostrazione della Minimalità: Per dimostrare che non esiste una rappresentazione più breve, l'autore costruisce una famiglia finita di indicatori di funzionali. Per ogni possibile coppia di valori della griglia $(M, m)$, è definito un funzionale indicatore $F_{(M,m)}$ che restituisce 1 se $(M, m)$ è presente nello stack $\Pi_n$ e 0 altrimenti. Il lavoro dimostra che qualsiasi rappresentazione capace di rispondere a tutte le interrogazioni in $\mathcal{R}$ deve, per necessità, permettere la ricostruzione dell'intero stack $\Pi_n$ tramite questi indicatori.

Contributi Chiave

1. Sufficienza Minima: Il lavoro dimostra che lo stack degli estremi $\Pi_n$ è una statistica sufficiente minima per la classe $\mathcal{R}$. Stabilisce che qualsiasi compressione senza perdita che preservi la capacità di rispondere a tutte le interrogazioni indipendenti dalla velocità deve conservare almeno $K(\Pi_n) - O(1)$ bit.
2. Limiti di Complessità Rigorosi: Gli autori stabiliscono la relazione precisa di complessità di Kolmogorov:
   $$K(\Pi_n) - O(1) \le K_R(u_{0:n}) \le K(\Pi_n) + O(1)$$
   Questo corregge e restringe i precedenti limiti informali di $O(\log n)$ o $O(\log K(\Pi_n))$. Il sovraccarico $O(1)$ è dimostrato essere indipendente dalla lunghezza della sequenza $n$ e dalla profondità dello stack $k$.
3. Giustificazione Teorica per la Compressione: Il risultato fornisce una garanzia formale di ottimalità per gli algoritmi di compressione basati su stack (denominati PSTACK). A differenza dei metodi standard di compressione delle serie temporali (ad esempio PAA, SAX, PLR) che offrono garanzie euristico o di approssimazione $L_p$, l'approccio basato su stack è asintoticamente ottimale per la specifica classe di funzionali indipendenti dalla velocità.

Risultati

• Limite Superiore: La lunghezza del programma più breve che risponde a tutte le interrogazioni $\mathcal{R}$ è limitata superiormente da $K(\Pi_n) + O(1)$. Questo deriva dal teorema di invarianza prefisso-libera, poiché la mappatura da $\Pi_n$ a qualsiasi $F[u](n)$ è una funzione computabile fissa.
• Limite Inferiore: La lunghezza è limitata inferiormente da $K(\Pi_n) - O(1)$. Ciò è dimostrato mostrando che la rappresentazione ottimale $R(u_{0:n})$ permette la ricostruzione di $\Pi_n$ tramite una funzione computabile $\Phi$ applicata alla famiglia di indicatori. Poiché $\Pi_n$ può essere recuperato dalla rappresentazione, quest'ultima non può essere significativamente più breve della complessità dello stack stesso.
• Efficienza Algoritmica: Il lavoro nota che lo stack può essere mantenuto in tempo $O(1)$ ammortizzato per passo con spazio $O(k)$, dove $k$ è la profondità corrente dello stack.

Significato e Affermazioni
Il lavoro afferma che lo stack degli estremi non è meramente una struttura dati conveniente, ma è necessario dal punto di vista dell'informazione per l'elaborazione indipendente dalla velocità.

• Ottimalità: La rappresentazione basata su stack è asintoticamente ottimale. Qualsiasi tentativo di comprimere ulteriormente un flusso guidato dall'isteresi preservando l'intera classe di interrogazioni indipendenti dalla velocità comporterebbe una perdita di informazioni.
• Indipendenza dalla Lunghezza della Sequenza: Il sovraccarico $O(1)$ implica che per segnali con lunghe corse monotone (piccolo $k$ rispetto a $n$), il rapporto di compressione $n/k$ può essere arbitrariamente grande senza aumentare il divario di ottimalità.
• Ambito di Applicazione: I risultati si applicano specificamente a sequenze discrete su una griglia finita $G_L$. Il lavoro nota esplicitamente che sui reali continui $\mathbb{R}$, la famiglia di indicatori sarebbe non numerabile e il framework di Kolmogorov non si applicherebbe direttamente.

Il lavoro conclude che il meccanismo di "cancellazione" (wiping) intrinseco nell'operatore di Preisach non è solo una curiosità fisica o matematica, ma rappresenta il limite fondamentale della ritenzione informativa per i sistemi indipendenti dalla velocità.