⚡ electrical engineering

Uncertainty Principle for Vertex-Time Graph Signal Processing

यह शोध पत्र वर्टेक्स-टाइम ग्राफ सिग्नल प्रोसेसिंग के लिए एक एकीकृत अनिश्चितता सिद्धांत प्रस्तावित करता है जो स्थानिक और लौकिक डोमेन में सिग्नल स्थानीयकरण को परिभाषित करता है, जिससे मजबूत पुनर्निर्माण के लिए इष्टतम सिग्नल परमाणुओं का निर्माण और ग्राफ टोपोलॉजी अनुमान की एक नवीन विधि सक्षम होती है, जिसे सिंथेटिक और वास्तविक डेटासेट पर बेहतर प्रदर्शन द्वारा मान्य किया गया है।

मूल लेखक: Yanan Zhao, Xingchao Jian, Feng Ji, Wee Peng Tay, Antonio Ortega

प्रकाशित 2026-02-05

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Yanan Zhao, Xingchao Jian, Feng Ji, Wee Peng Tay, Antonio Ortega

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप दोस्तों के एक नेटवर्क (शीर्षों/vertices) में समय (समय/time) के साथ चल रही एक जटिल कहानी को समझने की कोशिश कर रहे हैं। शायद यह किसी अफवाह के फैलने को ट्रैक कर रहा है, या शहर में यातायात के प्रवाह को, या फिर अलग-अलग काउंटियों में वायरस के प्रसार को।

सिग्नल प्रोसेसिंग की दुनिया में, एक प्रसिद्ध नियम है जिसे अनिश्चितता का सिद्धांत (Uncertainty Principle) कहा जाता है। इसे एक कैमरे की तरह समझें: आप इस पर ध्यान केंद्रित कर सकते हैं कि कोई चीज़ कहाँ हो रही है, या आप इस पर ध्यान केंद्रित कर सकते हैं कि वह क्या कर रही है (उसकी आवृत्ति/लय), लेकिन आप एक ही समय में दोनों पर पूरी तरह से सटीक नहीं हो सकते। यदि आप स्थान पर बहुत अधिक ज़ूम करते हैं, तो लय धुंधली हो जाती है, और इसके विपरीत भी।

यह शोधपत्र एक नया, सुपर-पावर्ड संस्करण पेश करता है जो विशेष रूप से ग्राफ सिग्नल्स (Graph Signals) के लिए है—ऐसा डेटा जो एक नेटवर्क (जैसे सोशल नेटवर्क या सड़क मानचित्र) पर रहता है और समय के साथ बदलता है।

यहाँ लेखकों द्वारा किए गए कार्यों का सरल उपमाओं के माध्यम से विवरण दिया गया है:

1. समस्या: "गायब पहेली के टुकड़े" (The Missing Puzzle Pieces)

कल्पना कीजिए कि आप बिखरे हुए कुछ फ्रेमों से एक फिल्म को फिर से बनाने की कोशिश कर रहे हैं।

समस्या: वास्तविक जीवन में (जैसे सेंसर नेटवर्क या सोशल मीडिया में), डेटा अव्यवस्थित होता है। कुछ सेंसर बंद हो जाते हैं, कुछ लोग हफ्तों तक पोस्ट नहीं करते हैं, और कुछ काउंटियाँ केवल धूप वाले दिनों में ही डेटा रिपोर्ट करती हैं। आपके पास किसने रिपोर्ट किया (स्थान) और कब रिपोर्ट किया (समय), दोनों में "अंतराल" या "गैप" हैं।
पुराना तरीका: पिछले तरीकों ने इन अंतरालों को भरने के लिए निश्चित टेम्पलेट्स का उपयोग करने की कोशिश की, जैसे कि एक मानक ग्रिड। लेकिन यदि आपका डेटा बिखरा हुआ और अनियमित है, तो एक कठोर ग्रिड अच्छी तरह से फिट नहीं बैठता है। यह एक चौकोर टुकड़े को गोल छेद में फिट करने जैसा है।

2. समाधान: "स्मार्ट स्पॉटलाइट" (The Smart Spotlight)

लेखकों ने एक नया गणितीय ढांचा (अनिश्चितता का सिद्धांत) बनाया है जो स्थान (कौन से दोस्त/स्थान) और समय (कब) के बीच के संतुलन को समझता है।

उन्होंने विशेष प्रकार के सिग्नल खोजे जो "स्मार्ट स्पॉटलाइट्स" की तरह कार्य करते हैं।

एक साधारण टॉर्च की तरह जो हर जगह समान रूप से रोशनी डालती है, ये स्पॉटलाइट्स जानती हैं कि सिग्नल की ऊर्जा कहाँ केंद्रित है।
यदि वायरस केवल 100 से 200 दिनों के बीच 5 विशिष्ट काउंटियों में सक्रिय है, तो यह विधि एक ऐसा "स्पॉटलाइट" बनाएगी जो केवल उन 5 काउंटियों पर और उन 100 दिनों के दौरान ही रोशनी डालेगी। यह बाकी सब को अनदेखा कर देती है।
ये स्पॉटलाइट्स एक नए शब्दकोश (dictionary) के "परमाणु" (बिल्डिंग ब्लॉक्स) हैं। सोचिए कि एक शब्दकोश शब्दों की किताब नहीं, बल्कि इन पूर्ण, कस्टम-फिट स्पॉटलाइट्स का एक टूलबॉक्स है।

3. उन्होंने इसका उपयोग कैसे किया: दो मुख्य तरकीबें

तरकीब A: गायब फिल्म का पुनर्निर्माण करना (Signal Reconstruction)

लक्ष्य: वायरस या यातायात की "फिल्म" में छूटे हुए डेटा बिंदुओं को भरना।
विधि: उन्होंने अपने "स्मार्ट स्पॉटलाइट्स" का उपयोग करके एक शब्दकोश बनाने के लिए किया। उन्होंने कंप्यूटर को यह सीखने के लिए प्रशिक्षित किया कि कौन सी काउंटियाँ और समय अंतराल सबसे अधिक ऊर्जा (सबसे अधिक गतिविधि) रखते हैं।
परिणाम: जब उन्होंने वास्तविक डेटा (जैसे कैलिफोर्निया में COVID-1ース के मामले) पर इसका परीक्षण किया, तो उनकी विधि पुराने तरीकों की तुलना में गायब संख्याओं का अनुमान लगाने में बहुत बेहतर थी। यह तब भी अधिक मजबूत थी जब डेटा शोर (noise) से भरा था (जैसे जब सेंसर गलत रीडिंग देते हैं)। यह एक ऐसे जासूस की तरह था जो किसी अपराध स्थल के गायब सुरागों का अनुमान एक मानक अन्वेषक की तुलना में बहुत बेहतर तरीके से लगा सकता है।

तरकीब B: मानचित्र का पता लगाना (Graph Topology Inference)

लक्ष्य: कभी-कभी आपको मानचित्र भी पता नहीं होता! आपके पास डेटा (वायरस के मामले) है, लेकिन आप नहीं जानते कि कौन सी काउंटियाँ आपस में जुड़ी हुई हैं।
विधि: उन्होंने अनिश्चितता के सिद्धांत का उल्टा उपयोग किया। उन्होंने पूछा: "किस तरह का मानचित्र इस डेटा को सबसे अधिक व्यवस्थित और केंद्रित दिखाएगा?"
परि kết: इस "स्मार्ट स्पॉटलाइट" नियम के लिए सबसे उपयुक्त मानचित्र को खोजकर, वे काउंटियों के बीच के संबंधों का अनुमान लगाने में सक्षम हुए। उनकी विधि पिछले तकनीकों की तुलना में सही मानचित्र बनाने में अधिक सटीक थी।

4. प्रमाण: वास्तविक दुनिया के परीक्षण

लेखकों ने केवल कागज पर गणित नहीं किया; उन्होंने इसका परीक्षण किया:

वास्तविक डेटा: उन्होंने कैलिफोर्निया के COVID-19 के वास्तविक डेटा और ट्रैफ़िक डेटा का उपयोग किया। उनकी विधि ने पुराने तरीकों की तुलना में बहुत अधिक सटीकता के साथ (लगभग 4 dB बेहतर, जो सिग्नल गुणवत्ता में एक महत्वपूर्ण उछाल है) डेटा को पुनर्गठित किया और शोर को बहुत बेहतर तरीके से संभाला।
नकली डेटा: उन्होंने "मानचित्र बनाने" की तरकीब का परीक्षण करने के लिए नकली ग्राफ और सिग्नल बनाए। उनकी विधि प्रतिस्पर्धा की तुलना में अधिक बार सही कनेक्शन ढूंढ पाई।

सारांश

इस शोधपत्र को डेटा को देखने के लिए एक नए प्रकार के लेंस के आविष्कार के रूप में समझें, जो समय के साथ एक नेटवर्क पर चलते हैं।

पुराने लेंस: कठोर, निश्चित ग्रिड जो छूटे हुए या अव्यवस्थित डेटा के साथ संघर्ष करते हैं।
नया लेंस: एक लचीला, "स्मार्ट स्पॉटलाइट" जो ठीक उसी स्थान और समय के अनुकूल होता है जहाँ गतिविधि हो रही है।

स्थान और समय एक-दूसरे के विरुद्ध कैसे संतुलन बनाते हैं (अनिश्चितता का सिद्धांत) इसके मूलभूत नियमों को समझकर, लेखकों ने ऐसे उपकरण बनाए हैं जो न केवल गायब डेटा को अधिक सटीकता से भर सकते हैं, बल्कि नेटवर्क के स्वयं के मानचित्र को भी बना सकते हैं, और वह भी उस शोर और अंतराल को अनदेखा करते हुए जो आमतौर पर कंप्यूटर को भ्रमित कर देते हैं।

तकनीकी सारांश: वर्टेक्स-टाइम ग्राफ सिग्नल प्रोसेसिंग के लिए अनिश्चितता सिद्धांत (Uncertainty Principle)

समस्या विवरण
मौजूदा ग्राफ सिग्नल प्रोसेसिंग (GSP) ढांचे मुख्य रूप से वर्टेक्स डोमेन या शास्त्रीय समय-आवृत्ति (time-frequency) डोमेन के भीतर स्थानीयकरण (localization) पर ध्यान केंद्रित करते हैं। जबकि ग्राफ सिग्नल्स (वर्टेक्स बनाम स्पेक्ट्रल) और निरंतर-समय सिग्नल्स (समय बनाम आवृत्ति) दोनों के लिए अनिश्चितता सिद्धांत स्थापित किए जा चुके हैं, अनियमित वर्टेक्स-टाइम डोमेन पर परिभाषित सिग्नल्स को संबोधित करने वाले एक एकीकृत ढांचे का अभाव है। वास्तविक दुनिया के अनुप्रयोग, जैसे सेंसर और सोशल नेटवर्क, अक्सर उन स्थितियों का सामना करते हैं जहाँ सेंसर अनियमित अंतराल पर डेटा रिकॉर्ड करते हैं, रुक-रुक कर विफल होते हैं, या केवल नेटवर्क के कुछ उपसमुच्चयों (subsets) के लिए रिपोर्ट करते हैं। पारंपरिक विधियाँ, जैसे कि शॉर्ट टाइम-वर्टेक्स फूरियर ट्रांसफॉर्म (STVFT) और स्पेक्ट्रल टाइम-वर्टेक्स वेवलेट ट्रांसफॉर्म (STVWT), निश्चित आधारों (fixed bases) या नियमित सैंपलिंग धारणाओं पर निर्भर करती हैं, जो अनियमित या डेटा-निर्भर वर्टेक्स और समय अंतरालों पर केंद्रित सिग्नल ऊर्जा को पकड़ने के लिए अनुपयुक्त हैं। इसके अलावा, मौजूदा ग्राफ लर्निंग विधियाँ अक्सर वर्टेक्स और स्पेक्ट्रल स्थानीयकरण के बीच अंतर्निहित ट्रेड-ऑफ (trade-offs) को अनदेखा कर देती हैं।

कार्यप्रणाली (Methodology)
यह शोध पत्र वर्टेक्स-टाइम ग्राफ सिग्नल्स के लिए एक सामान्यीकृत अनिश्चितता सिद्धांत प्रस्तावित करता है जो शास्त्रीय समय-आवृत्ति और ग्राफ अनिश्चितता सिद्धांतों को एकीकृत करता है। कार्यप्रणाली निम्नलिखित चरणों के माध्यम से आगे बढ़ती है:

सैद्धांतिक सूत्रीकरण (Theoretical Formulation):
- लेखक वर्टेक्स-टाइम सिग्नल्स $f: \mathcal{V} \times \mathcal{T} \to \mathbb{C}$ के लिए एक संयुक्त फूरियर ट्रांसफॉर्म (JFT) को परिभाषित करते हैं, जो सिग्नल्स को वर्टेक्स-टाइम डोमेन से स्पेक्ट्रल-फ्रीक्वेंसी डोमेन ( $\Lambda \times \Omega$ ) में मैप करता है।
- वे $L^2(\mathcal{V} \times \mathcal{T})$ और $L^2(\Lambda \times \Omega)$ के क्लोज्ड सबस्पेस पर ऊर्जा एकाग्रता (energy concentration) के आधार पर वर्टेक्स-टाइम प्रसार ( $\alpha_{VT}$ ) और स्पेक्ट्रल-फ्रीक्वेंसी प्रसार ( $\beta_{SF}$ ) पेश करते हैं।
- प्रमेय 1 (Theorem 1) अनिश्चितता सिद्धांत को स्थापित करता है, जो $(\alpha_{VT}, \beta_{SF})$ के जोड़े के लिए एक व्यवहार्य क्षेत्र $\Theta$ को परिभाषित करता है। यह क्षेत्र ऑपरेटर कंपोजिशन $\Pi_{SF}\Pi_{VT}\Pi_{SF}$ के सबसे बड़े आइजनवैल्यू द्वारा सीमित है, जहाँ $\Pi$ ऑर्थोगोनल प्रोजेक्शन ऑपरेटर है।
- शोध पत्र उन स्थितियों की पहचान करता है जिनमें सिग्नल्स दोनों डोमेन में एक साथ पूर्ण स्थानीयकरण प्राप्त कर सकते हैं और उन सिग्नल्स को अभिलक्षणित (characterize) करता है जो अधिकतम एकाग्रता प्राप्त करते हैं जब पूर्ण स्थानीयकरण असंभव होता है।
वर्टेक्स-टाइम डिक्शनरी लर्निंग (सिग्नल पुनर्निर्माण):
- अनिश्चितता सिद्धांत का लाभ उठाते हुए, लेखक एक जॉइंट एनर्जी कंसन्ट्रेटेड डिक्शनरी (JECD) डिजाइन करते हैं।
- वे डिक्शनरी एटम्स (atoms) के लिए दो विशिष्ट निर्माण प्रस्तावित करते हैं:
  - सपोर्ट-लिमिटेड सबस्पेस (Support-Limited Subspace): एटम्स का निर्माण वर्टेक्स सबसेट $V'$ पर स्थानीयकृत ग्राफ आइजनवेक्टर्स और समय अंतराल $T'$ पर स्थानीयकृत प्रोलेट स्पेरॉइडल वेव फंक्शन्स (PSWFs) के टेंसर उत्पादों के रूप में किया जाता है। पैरामीटर्स ( $V'$ , केंद्र समय $t_c$ , अवधि $\ell$ ) को देखे गए डेटा पर ऊर्जा एकाग्रता को अधिकतम करने के लिए एक ग्रीडी एल्गोरिदम और अल्टरनेटिंग मिनिमाइजेशन के माध्यम से अनुकूलित किया जाता है।
  - गौसियन हीट-कर्नेल सबस्पेस (Gaussian Heat-Kernel Subspace): एटम्स को ग्राफ हीट एटम्स और टेम्पोरल गौसियन कर्नेलल्स का उपयोग करके बनाया जाता है। डिफ्यूजन स्केल्स ( $\tau_v, \tau_t$ ) को एकाग्रता स्कोर को अधिकतम करने के लिए ग्रिड सर्च के माध्यम से चुना जाता है।
- सिग्नल पुनर्निर्माण को सीखे गए डिक्शनरी का उपयोग करके एक स्पार्स कोडिंग समस्या को हल करके किया जाता है, जो बिना रीसैंपलिंग के अनियमित और लुप्त डेटा को समायोजित करता है।
ग्राफ टोपोलॉजी इन्फरेंस (Graph Topology Inference):
- शोध पत्र एक एनर्जी-कंसन्ट्रेटेड ग्राफ लर्निंग (ECGL) एल्गोरिदम पेश करता है।
- यह दृष्टिकोण ग्राफ लैपलेसियन $L$ (और इसके आइजनवेक्टर्स $U$ ) को स्पेक्ट्रल-फ्रीक्वेंसी ऊर्जा एकाग्रता को अधिकतम करके सीखता है, जबकि अनिश्चितता सिद्धांत द्वारा निर्देशित वर्टेक्स-स्पेक्ट्रल स्थानीयकरण ट्रेड-ऑफ का सम्मान करता है।
- यह अनुकूलन ग्राफ फूरियर बेसिस, स्पार्स गुणांकों और लैपलेसियन मैट्रिक्स को संयुक्त रूप से अनुमानित करता है, जिसमें वैध कॉम्बिनेटरियल लैपलेसियन्स सुनिश्चित करने के लिए टोटल वेरिएशन रेगुलराइजेशन और बाधाएं शामिल हैं।

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

सामान्यीकृत अनिश्चितता सिद्धांत: वर्टेक्स-टाइम ग्राफ सिग्नल्स के लिए एक एकीकृत अनिश्चितता सिद्धांत का सूत्रीकरण जो सबस्पेस-आधारित स्थानीयकरण माप के माध्यम से मौजूदा ग्राफ और निरंतर-समय स्वरूपों का विस्तार करता है।
मैक्सिमली कंसन्ट्रेटेड सिग्नल्स: वर्टेक्स-टाइम और स्पेक्ट्रल-फ्रीक्वेंसी डोमेन में अधिकतम एकाग्रता प्राप्त करने वाले वर्टेक्स-टाइम ग्राफ सिग्नल्स के एक वर्ग की पहचान, जो एक नए डिक्शनरी के लिए मौलिक एटम्स के रूप में कार्य करते हैं।
नया पुनर्निर्माण ढांचा: JECD पद्धति का विकास, जो अनियमित अवलोकन पैटर्न के अनुरूप ऊर्जा-केंद्रित आधारों को सीखता है, जिससे व्यावहारिक बाधाओं के तहत पुनर्निर्माण सटीकता में सुधार होता है।
ग्राफ लर्निंग दृष्टिकोण: ECGL का प्रस्ताव, जो एक ग्राफ लर्निंग विधि है जो स्पष्ट रूप से अनिश्चितता सिद्धांत के स्थानीयकरण ट्रेड-ऑफ को शामिल करती है ताकि उन ग्राफ टोपोलॉजी को सीखा जा सके जो अंतर्निहित सिग्नल संरचनाओं के साथ संरेखित हों।

प्रायोगिक परिणाम
लेखक सिंथेटिक और वास्तविक दुनिया के डेटासेट का उपयोग करके अपने दृष्टिकोण को मान्य करते हैं:

सिग्नल पुनर्निर्माण: कैलिफोर्निया COVID-19 डेटासेट (2 वर्षों में 58 काउंटियों पर) और ट्रैफिक फ्लो डेटा पर प्रयोगों से पता चलता है कि JECD, बेसलाइन्स (JFT, STVFT, STVWT, और ग्राफ अनिश्चितता सिद्धांत का एक नाइव एक्सटेंशन) से बेहतर प्रदर्शन करता है। JECD पुनर्निर्माण सटीकता में औसतन 4 dB का लाभ प्राप्त करता है और उत्कृष्ट मजबूती प्रदर्शित करता है, जो 0 dB जैसे कम शोर स्तरों पर भी स्थिर प्रदर्शन बनाए रखता है।
गौसियन सबस्पेस: सिंथेटिक Erdős-Rényi ग्राफों पर, गौसियन हीट-कर्नेल बेस ने विभिन्न SNR स्तरों पर सबसे कम रिलेटिव स्क्वायर एरर (RSE) प्राप्त किया, जो कम-SNR व्यवस्थाओं में भी प्रतिस्पर्धी तरीकों से बेहतर प्रदर्शन करता है।
ग्राफ टोपोलॉजी इन्फरेंस: एक सिंथेटिक ग्राफ पर, ECGL ने टोटल वेरिएशन ग्राफ लर्निंग (TV-GL) और एस्टिमेटेड-सिग्नल-एडेड ग्राफ लर्निंग (ESA-GL) को पछाड़ दिया। ECML ने सीखे गए और वास्तविक लैपलेसियनों के बीच उच्च सहसंबंध गुणांक (0.9288 बनाम ~0.927) प्राप्त किया और एज रिकॉल (edge recall) में लगभग 4.7% का सुधार किया।

महत्व
शोध पत्र का दावा है कि इसकी प्राथमिक महत्ता निरंतर-समय परिदृश्यों के लिए शास्त्रीय समय-आवृत्ति विश्लेषण और ग्राफ सिग्नल प्रोसेसिंग के बीच के अंतर को पाटने में निहित है। वर्टेक्स-टाइम और स्पेक्ट्रल-फ्रीक्वेंसी स्थानीयकरण के बीच के ट्रेड-ऑफ को कठोरता से अभिलक्षणित करके, यह कार्य डेटा-संचालित सपोर्ट के लिए अनुकूलित डिक्शनरी डिजाइन करने के लिए एक सैद्धांतिक आधार प्रदान करता है। यह विशेष रूप से सेंसर नेटवर्क जैसे मामलों में अत्यंत मूल्यवान है जहाँ डेटा संग्रह रुक-रुक कर या एसिंक्रोनस होता है, जहाँ पारंपरिक विधियाँ स्थानीयकृत ऊर्जा एकाग्रता को पकड़ने में विफल रहती हैं। इसके अलावा, ग्राफ लर्निंग में अनिश्चितता सिद्धांत का एकीकरण ग्राफ संरचनाओं को अनुमानित करने का एक सिद्धांत-आधारित तरीका प्रदान करता है जो अंतर्निहित सिग्नल्स के भौतिक या संरचनात्मक बाधाओं का सम्मान करते हैं।

1. समस्या: "गायब पहेली के टुकड़े" (The Missing Puzzle Pieces)

2. समाधान: "स्मार्ट स्पॉटलाइट" (The Smart Spotlight)

3. उन्होंने इसका उपयोग कैसे किया: दो मुख्य तरकीबें

4. प्रमाण: वास्तविक दुनिया के परीक्षण

सारांश

इसी तरह के और पेपर