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

तकनीकी सारांश: दर-स्वतंत्र फलन (Rate-Independent Functionals) के लिए न्यूनतम पर्याप्त सांख्यिकी (Minimal Sufficient Statistic) के रूप में एक्सट्रीमम स्टैक (Extremum Stack)

समस्या विवरण
यह शोध पत्र दर-स्वतंत्र फलन (rate-independent functionals) द्वारा नियंत्रित अनुक्रमों के डेटा संपीड़न (data compression) के मौलिक प्रश्न को संबोधित करता है। एक फलन $F$ दर-स्वतंत्र है यदि उसका आउटपुट इनपुट के स्थानीय चरम मानों (local extrema) के क्रम पर निर्भर करता है, न कि उनके अस्थायी अंतराल, परिवर्तन की गति, या गैर-चरम बिंदुओं पर उनके पूर्ण मानों पर। यह गुण फेरोमैग्नेटिक हिस्टेरेसिस (ferromagnetic hysteresis), इलास्टोप्लास्टिक प्रणालियों और वित्तीय थ्रेशोल्ड मॉडल जैसी घटनाओं के मॉडलिंग के लिए केंद्रीय है।

यद्यपि यह स्थापित है कि एक्सट्रीमम स्टैक ($\Pi_n$)—जो स्थानीय अधिकतम (maxima) और न्यूनतम (minima) का एक वैकल्पिक क्रम है—प्रिसैक (Preisach) फलनों के लिए एक पर्याप्त सांख्यिकी है, यह एक खुला प्रश्न था कि क्या यह प्रतिनिधित्व न्यूनतम भी है। विशेष रूप से, क्या एक छोटा प्रतिनिधित्व $\mathcal{R}$ वर्ग के गणनीय (computable), कारणत्मक (causal), दर-स्वतंत्र फलनों के लिए सभी प्रश्नों का उत्तर देने में सक्षम है? इसके अतिरिक्त, पिछले अनौपचारिक दावों ने सुझाव दिया था कि स्टैक का ओवरहेड $O(\log n)$ या $O(\log K(\Pi_n))$ है, लेकिन सटीक कोलमोगोरोव जटिलता (Kolmogorov complexity) सीमाओं को कठोरता से स्थापित नहीं किया गया था।

कार्यप्रणाली
लेखक किसी अनुक्रम $u_{0:n}$ को निरूपित करने के लिए आवश्यक सूचना की मात्रा को मापने के लिए कोलमोगोरोव जटिलता सिद्धांत का उपयोग करते हैं ताकि किसी भी $F \in \mathcal{R}$ के लिए $F[u](n)$ की गणना की जा सके।

• परिभाषाएँ: शोध पत्र $\Pi_n$ को $(M_i, m_i)$ के युग्मों के एक अनुक्रम के रूप में परिभाषित करता है जो जीवित स्थानीय चरम मानों का प्रतिनिधित्व करता है, जिसे एक "वाइपिंग" (wiping) तंत्र के माध्यम से अपडेट किया जाता है जहाँ नए चरम मान पुराने और छोटे चरम मानों को मिटा देते हैं।
• पर्याप्तता प्रमाण (Sufficiency Proof): ऊपरी सीमा (upper bound) प्रिसैक हिस्टेरेसिस ऑपरेटर के शास्त्रीय वाइपिंग गुण से प्राप्त की गई है। चूंकि किसी भी दर-स्वतंत्र फलन का आउटपुट $\Pi_n$ पर निर्भर करता है, इसलिए एक निश्चित गणनीय फलन $\Pi_n$ को फलन आउटपुट में मैप कर सकता है।
• न्यूनतमता प्रमाण (Minimality Proof): यह सिद्ध करने के लिए कि कोई छोटा प्रतिनिधित्व मौजूद नहीं है, लेखक फलनों के एक परिमित संकेतक परिवार (finite indicator family) का निर्माण करते हैं। प्रत्येक संभावित ग्रिड मान युग्म $(M, m)$ के लिए, एक संकेतक फलन $F_{(M,m)}$ परिभाषित किया गया है जो 1 लौटाता है यदि $(M, m)$ स्टैक $\Pi_n$ में मौजूद है और अन्यथा 0 लौटाता है। शोध पत्र यह प्रदर्शित करता है कि $\mathcal{R}$ के सभी प्रश्नों का उत्तर देने में सक्षम कोई भी प्रतिनिधित्व, इन संकेतकों के माध्यम से पूर्ण स्टैक $\Pi_n$ के पुनर्निर्माण की अनुमति देकर, अनिवार्य रूप से पूर्ण स्टैक $\Pi_n$ को पुनर्गठित करने में सक्षम होना चाहिए।

प्रमुख योगदान

1. न्यूनतम पर्याप्तता (Minimal Sufficiency): शोध पत्र सिद्ध करता है कि एक्सट्रीमम स्टैक $\Pi_n$ वर्ग $\mathcal{R}$ के लिए एक न्यूनतम पर्याप्त सांख्यिकीय है। यह स्थापित करता है कि कोई भी लॉसलेस संपीड़न (lossless compression) जो सभी दर-स्वतंत्र प्रश्नों का उत्तर देने की क्षमता बनाए रखता है, उसे कम से कम $K(\Pi_n) - O(1)$ बिट्स को बनाए रखना होगा।
2. सटीक जटिलता सीमाएँ (Tight Complexity Bounds): लेखक सटीक कोलमोगोरोव जटिलता संबंध स्थापित करते हैं:
   $$K(\Pi_n) - O(1) \le K_R(u_{0:n}) \le K(\Pi_n) + O(1)$$
   यह $O(\log n)$ या $O(\log K(\Pi_n))$ के पिछले अनौपचारिक बंधों को ठीक और सुदृढ़ करता है। $O(1)$ ओवरहेड को दिखाया गया है कि यह अनुक्रम की लंबाई $n$ से स्वतंत्र है।
3. संपीड़न के लिए सैद्धांतिक औचित्य: यह परिणाम स्टैक-आधारित संपीड़न एल्गोरिदम (जिसे PSTACK कहा जाता है) के लिए एक औपचारिक इष्टतमता गारंटी प्रदान करता है। PAA, SAX, PLR जैसे मानक टाइम-सीरीज संपीड़न विधियों के विपरीत, जो अनुमानी (heuristic) या $L_p$-अनुमान गारंटी प्रदान करते हैं, स्टैक-आधारित दृष्टिकोण दर-स्वतंत्र फलनों के विशिष्ट वर्ग के लिए स्पर्शोन्मुख रूप से (asymptotically) इष्टतम है।

परिणाम

• ऊपरी सीमा (Upper Bound): सभी $\mathcal{R}$-प्रश्नों का उत्तर देने वाले सबसे छोटे प्रोग्राम की लंबाई $K(\Pi_n) + O(1)$ द्वारा सीमित है। यह प्रीफिक्स-फ्री इनवेरिएंस प्रमेय का अनुसरण करता है, क्योंकि $\Pi_n$ से किसी भी $F[u](n)$ में मैपिंग एक निश्चित गणनीय फलन है।
• निचली सीमा (Lower Bound): लंबाई $K(\Pi_n) - O(1)$ द्वारा सीमित है। यह दिखाते हुए सिद्ध किया गया है कि इष्टतम प्रतिनिधित्व $R(u_{0:n})$, संकेतक परिवार के माध्यम से $\Pi_n$ के पुनर्निर्माण की अनुमति देता है। चूंकि $\Pi_n$ को प्रतिनिधित्व से पुनः प्राप्त किया जा सकता है, इसलिए प्रतिनिधित्व स्वयं स्टैक की जटिलता से काफी छोटा नहीं हो सकता है।
• एल्गोरिद्मिक दक्षता: शोध पत्र नोट करता है कि स्टैक को प्रति चरण अमोर्टाइज्ड (amortized) $O(1)$ समय में और $O(k)$ स्पेस के साथ बनाए रखा जा सकता है, जहाँ $k$ वर्तमान स्टैक गहराई है।

महत्व और दावे
शोध पत्र का दावा है कि एक्सट्रीमम स्टैक केवल एक सुविधाजनक डेटा संरचना नहीं है बल्कि दर-स्वतंत्र प्रसंस्करण के लिए सूचनात्मक रूप से आवश्यक है।

• इष्टतमता (Optimality): स्टैक-आधारित प्रतिनिधित्व स्पर्शोन्मुख रूप से इष्टतम है। हिस्टेरेसिस-संचालित स्ट्रीम को और अधिक कंप्रेस करने का कोई भी प्रयास जो पूर्ण दर-स्वतंत्र प्रश्नों के वर्ग को संरक्षित करता है, सूचना की हानि का कारण बनेगा।
• अनुक्रम की लंबाई से स्वतंत्रता: $O(1)$ ओवरहेड यह दर्शाता है कि लंबे मोनोटोन रन (छोटे $k$ के सापेक्ष $n$) वाले संकेतों के लिए, संपीड़न अनुपात $n/k$ इष्टतमता अंतराल को बढ़ाए बिना अनिश्चित रूप से बड़ा हो सकता है।
• क्षेत्र (Scope): परिणाम विशेष रूप से एक परिमित ग्रिड $G_L$ पर असतत अनुक्रमों पर लागू होते हैं। शोध पत्र स्पष्ट रूप से नोट करता है कि निरंतर वास्तविक संख्याओं $\mathbb{R}$ पर, संकेतक परिवार अगणनीय होगा, और कोलमोगोरोव ढांचा सीधे लागू नहीं होगा।

कार्य यह निष्कर्ष निकालता है कि प्रिसैक ऑपरेटर में अंतर्निहित "वाइपिंग" तंत्र न केवल एक भौतिक या गणितीय जिज्ञासा है, बल्कि दर-स्वतंत्र प्रणालियों के लिए सूचना प्रतिधारण (information retention) की मौलिक सीमा का प्रतिनिधित्व करता है।