Uncertainty Principle for Vertex-Time Graph Signal Processing

ملخص تقني: مبدأ عدم اليقين لمعالجة الإشارات على الرسوم البيانية (الرؤوس-الزمن)

بيان المشكلة
تركز أطر معالجة الإشارات على الرسوم البيانية (GSP) الحالية بشكل أساسي على التمركز ضمن نطاق الرؤوس أو نطاق الزمن-التردد الكلاسيكي. وبينما تم وضع مبادئ عدم اليقين لكل من إشارات الرسم البياني (الرؤوس مقابل الطيف) والإشارات المستمرة زمنياً (الزمن مقابل التردد)، إلا أن هناك نقصاً في وجود إطار عمل موحد يعالج الإشارات المعرفة على نطاقات "رأس-زمن" غير منتظمة. فالتطبيقات الواقعية، مثل شبكات الاستشعار والشبكات الاجتماعية، غالباً ما تواجه ملاحظات متفرقة أو غير منتظمة أو مقيدة حيث تسجل المستشعرات بيانات في فترات زمنية غير متساوية، أو تفشل بشكل متقطع، أو تبلغ فقط عن مجموعات فرعية من الشبكة. إن الطرق التقليدية، مثل تحويل فوريه قصير المدى للرؤوس (STVFT) وتحويل المويجات طيفي الزمن-الرؤوس (STVWT)، تعتمد على قواعد ثابتة أو افتراضات أخذ عينات منتظمة، مما يجعلها غير ملائمة لالتقاط طاقة الإشارة المركزة فوق مجموعات فرعية من الرؤوس وفترات زمنية تعتمد على البيانات. علاوة على ذلك، فإن طرق تعلم الرسم البياني الحالية غالباً ما تتجاهل المقايضات الجوهرية بين التمركز في نطاق الرؤوس ونطاق الطيف.

المنهجية
يقترح البحث مبدأ عدم يقين معمم لإشارات الرسم البياني (رؤوس-زمن) يوحد مبادئ عدم اليقين الكلاسيكية للزمن-التردد والرسوم البيانية. وتتقدم المنهجية عبر الخطوات التالية:

1. الصياغة النظرية:

• يعرف المؤلفون تحويل فوريه مشترك (JFT) لإشارات الرؤوس-الزمن $f: \mathcal{V} \times \mathcal{T} \to \mathbb{C}$، والذي ينقل الإشارات من نطاق الرؤوس-الزمن إلى النطاق الطيفي-الترددي ($\Lambda \times \Omega$).
• يقدمون مفهوم الانتشار الرأسي-الزمني ($\alpha_{VT}$) والانتشار الطيفي-الترددي ($\beta_{SF}$) بناءً على تركيز الطاقة فوق الفضاءات الجزئية المغلقة لـ $L^2(\mathcal{V} \times \mathcal{T})$ و $L^2(\Lambda \times \Omega)$ على التوالي.
• يحدد النظرية 1 مبدأ عدم اليقين، حيث يحدد منطقة مجازية $\Theta$ للزوج $(\alpha_{VT}, \beta_{SF})$. هذه المنطقة محصورة بأكبر قيمة ذاتية لمؤلف العمليات $\Pi_{SF}\Pi_{VT}\Pi_{SF}$، حيث يمثل $\Pi$ مؤثرات الإسقاط المتعامد.
• يحدد البحث الشروط التي يمكن للإشارات من خلالها تحقيق تمركز مثالي في كلا النطاقين في آن واحد، ويصف الإشارات التي تعظم التركيز عندما يكون التمركز المثالي مستحيلاً.

2. تعلم قاموس الرؤوس-الزمن (إعادة بناء الإشارة):

• بالاستفادة من مبدأ عدم اليقين، يصمم المؤلفون قاموساً مركزاً للطاقة المشتركة (JECD).
• يقترحون بناءين محددين لذرات القاموس:
  • الفضاء الجزئي المحدود بالدعم: تُبنى الذرات كحاصل ضرب تينسور لمتجهات فوريه الرسم البياني المتمركزة في مجموعة رؤوس $V'$ ودوال الموجات السفيرية البرولية (PSWFs) المتمركزة في فترة زمنية $T'$. يتم تحسين المعلمات ($V'$، المركز الزمني $t_c$، المدة $\ell$) عبر خوارزمية جشعة وتقليل تبادلي لتعظيم تركيز الطاقة على البيانات المرصودة.
  • فضاء نواة الحرارة الغاوسية: تتشكل الذرات باستخدام ذرات حرارة الرسم البياني ونواة غاوس الزمنية. يتم اختيار مقاييس الانتشار ($\tau_v, \tau_t$) عبر بحث شبكي لتعظيم درجة التركيز.
• تتم إعادة بناء الإشارة من خلال حل مشكلة الترميز المتناثر باستخدام القاموس المتعلم، مما يستوعب البيانات غير المنتظمة والمفقودة دون الحاجة إلى إعادة أخذ العينات.

3. استنتاج طوبولوجيا الرسم البياني:

• يقدم البحث خوارزمية تعلم الرسم البياني المركز للطاقة (ECGL).
• يقوم هذا النهج بتعلم لايبليان الرسم البياني $L$ (ومتجهات القيم الذاتية $U$) من خلال تعظيم تركيز الطاقة الطيفية-الترددية مع احترام مقايضة التمركز الرأسي-الطيفي التي يمليها مبدأ عدم اليقين.
• تعمل عملية التحسين على تقدير قاعدة فوريه الرسم البياني، والمعاملات المتناثرة، ومصفوفة اللايبليان بشكل مشترك، مع دمج تنظيم التباين الكلي والقيود لضمان الحصول على لايبليان توافقات (combinatorial Laplacians) صالحة.

المساهمات الرئيسية

1. مبدأ عدم اليقين المعمم: صياغة مبدأ عدم يقين موحد لإشارات الرسم البياني (رؤوس-زمن) يوسع نماذج عدم اليقين للرسوم البيانية والزمن المستمر من خلال مقياس تمركز قائم على الفضاءات الجزئية.
2. الإشارات ذات التركيز الأقصى: تحديد فئة من إشارات الرؤوس-الزمن التي تحقق أقصى تركيز في نطاقات الرؤوس-الزمن والطيف-التردد، والتي تعمل كذرات أساسية لقاموس جديد.
3. إطار عمل مبتكر لإعادة البناء: تطوير طريقة JECD، التي تتعلم قواعد مركزة الطاقة مصممة لتناسب أنماط الملاحظة غير المنتظمة، مما يحسن دقة إعادة البناء تحت القيود العملية.
4. نهج تعلم الرسم البياني: اقتراح ECGL، وهو طريقة لاستنتاج الرسم البياني تدمج صراحة مقايضات التمركز التي يفرضها مبدأ عدم اليقين لتعلم طوبولوجيا الرسوم البيانية التي تتوافق مع هياكل الإشارات الجوهرية.

النتائج التجريبية
يتحقق المؤلفون من نهجهم باستخدام مجموعات بيانات اصطناعية وواقعية:

• إعادة بناء الإشارة: في تجارب على مجموعة بيانات كاليفورنيا لمرض كوفيد-19 (58 مقاطعة على مدار عامين) وبيانات تدفق حركة المرور، يتفوق JECD على النماذج المرجعية (JFT, STVFT, STVWT، وامتداد بدائي لمبدأ عدم اليقين للرسم البياني). يحقق JECD متوسط ربح قدره 4 ديسيبل في دقة إعادة البناء ويظهر متانة فائقة، محافظاً على أداء مستقر حتى عند مستويات ضوضاء تصل إلى 0 ديسيبل.
• الفضاء الجزئي الغاوسي: في رسوم إردوش-ريني (Erdős-Rényi) الاصطناعية، حققت قاعدة نواة الحرارة الغاوسية أدنى خطأ مربع نسبي (RSE) عبر مختلف نسب الإشارة إلى الضوضاء (SNR)، متفوقة على الطرق المنافسة حتى في أنظمة SNR المنخفضة.
• استنتاج طوبولوجيا الرسم البياني: في رسم بياني اصطناعي، تفوق ECGL على تعلم الرسم البياني بالتباين الكلي (TV-GL) وتعلم الرسم البياني المعتمد على الإشارة المقدرة (ESA-GL). حقق ECGL معامل ارتباط أعلى (0.9288 مقابل ~0.927) بين لايبليان المتعلم والحقيقي، وحسن استدعاء الحواف بنسبة تقارب 4.7%.

الأهمية
يزعم البحث أن أهميته الأساسية تكمن في سد الفجوة بين تحليل الزمن-التردد الكلاسيكي ومعالجة الإشارات على الرسوم البيانية للسيناريوهات غير المنتظمة ذات الزمن المستمر. ومن خلال التوصيف الدقيق للمقايضات بين التمركز في نطاق الرؤوس-الزمن ونطاق الطيف-التردد، يوفر العمل أساساً نظرياً لتصميم قواميس تتكيف مع دعامات مدفوعة بالبيانات بدلاً من الشبكات الثابتة. وهذا أمر ذو قيمة خاصة للتطبيقات التي تتضمن جمع بيانات متقطع أو غير متزامن، مثل شبكات الاستشعار، حيث تفشل الطرق التقليدية في التقاط تركيزات الطاقة الموضعية. علاوة على ذلك، فإن دمج مبدأ عدم اليقين في تعلم الرسم البياني يوفر طريقة منهجية لاستنتاج هياكل الرسوم البيانية التي تحترم القيود الفيزيائية أو الهيكلية للإشارات الكامنة.