Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product with Applications to Image and Video Restoration

إليك ملخص تقني مفصل للورقة البحثية بعنوان:
"طرق فضاء كريفوف الموتر العشوائية عبر حاصل إينشتاين المخطط مع تطبيقات في ترميم الصور والفيديو."

1. بيان المشكلة

تتناول الورقة البحثية تحدي حل الأنظمة الموترية واسعة النطاق الناشئة في ترميم الصور والفيديو (مثل إزالة الضبابية، وإزالة الضجيج). تُنمذج هذه المشكلات كمعادلات موترية خطية على الشكل التالي:
$$\Phi(X) = C$$
أو صيغة المربعات الصغرى:
$$\min_X \| \Phi(X) - C \|_F$$
حيث:

• $X$ هو الموتر عالي الأبعاد المجهول (مثل صورة ملونة أو تسلسل فيديو).
• $C$ هي البيانات المرصودة المتدهورة.
• $\Phi$ هو مؤثر موتر خطي (يتضمن غالباً التضبيب أو أخذ العينات) مُعرف عبر حاصل إينشتاين الضرب ($*_N$).

التحدي الجوهري:
تعتمد طرق كريفوف الموترية الكلاسيكية (مثل Tensor Global GMRES أو Golub–Kahan) على حاصل الضرب الفروينيوني والتعامد الكامل. بالنسبة للموترات عالية الرتبة (على سبيل المثال، $N \times N \times 3$ لصور RGB أو أبعاد أعلى للفيديو)، تصبح التكلفة الحسابية لعمليات التعامد وحسابات الضرب الداخلي باهظة بسبب الأبعاد الهائلة ($n = \prod I_k$). علاوة على ذلك، فإن عملية "تجهيز" (vectorizing) هذه الموترات تدمر بنيتها متعددة الأبعاد المتأصلة، مما يؤدي إلى اختناقات في الذاكرة.

2. المنهجية

يقترح المؤلفون طريقة فضاء كريفوف الموترية العشوائية التي تدمج التخطيط (التقليل العشوائي للأبعاد) مباشرة في إطار حاصل إينشتاين.

أ. حاصل الضرب الإينشتايني المخطط

بدلاً من حساب حاصل الضرب الفروينيوني الدقيق $\langle X, Y \rangle_F$، تقدم الطريقة حاصل ضرب مخطط $\langle X, Y \rangle_\Theta$:
$$\langle X, Y \rangle_\Theta = \langle S(X), S(Y) \rangle_F$$
حيث $S(\cdot)$ هو مؤثر تضمين موتر عشوائي.

• الآلية: يطبق المؤثر $S$ مصفوفات إسقاط عشوائية ($\Theta_k$) لكل نمط (mode-wise) على الموتر $X$، مما يضغطه في فضاء أقل أبعاداً مع الحفاظ على هندسة الفضاء الجزئي باحتمالية عالية.
• الضمان النظري: تحت فرضية تضمين الفضاء الجزئي $\epsilon$، يقرب حاصل الضرب المخطط الناتج حاصل الضرب الحقيقي بحيث أن:
  $$(1-\epsilon)\|X\|_F^2 \leq \|S(X)\|_F^2 \leq (1+\epsilon)\|X\|_F^2$$
  هذا يضمن بقاء القيم المفردة والتعامد ضمن خطأ محدد.

ب. عملية أرنولدي العالمية الموترية المخططة

تطور الورقة خوارزمية أرنولدي العالمية المخططة لبناء قاعدة متعامدة لفضاء كريفوف الموتري.

• العملية: في كل تكرار، يتم تطبيق المؤثر الموتري $\Phi$، ويتم فوراً تخطيط النتيجة ($S(\Phi(V_j))$).
• التعامد: تستخدم عملية "غرام-شميدت" حاصل الضرب المخطط $\langle \cdot, \cdot \rangle_\Theta$ بدلاً من حاصل الضرب الفروينيوني.
• النتيجة: تولد هذه العملية مصفوفة هسنبرغ مختزلة $\tilde{H}_m$ تقرب تأثير $\Phi$ على الفضاء الجزئي، مما يقلل بشكل كبير من تكلفة عمليات ضرب الموتر في الموتر والتعامد.

ج. انتظام تيكونو (Tikhonov) المخطط

للتعامل مع المشكلات سيئة التحديد (الضجيج)، تدمج الطريقة انتظام تيكونو داخل الفضاء الجزئي المختزل:
$$\min_y \| \beta e_{m+1} - \tilde{H}_m y \|_2^2 + \mu \|y\|_2^2$$
يتم اختيار معامل الانتظام $\mu$ باستخدام التحقق المتقاطع العام (GCV) على المشكلة المصغرة المسقطة، مما يتجنب الحاجة إلى حل النظام عالي الأبعاد بالكامل.

د. الخوارزميات الكتلية (Block Algorithms)

تم توسيع الإطار ليشمل طرق فضاء كريفوف الكتلية، وتحديداً:

1. Sketched Einstein Block GMRES: لحل المعادلات الموترية الخطية.
2. Sketched Einstein Block Golub–Kahan: لحل مشكلات المربعات الصغرى (ثنائية الأقطاب).
   تستخدم كلتا الخوارزميتين حاصل الضرب المخطط لجميع فحوصات التعامد وحسابات المعيار (norm).

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

1. إطار عمل جديد: تقديم RTG-GMRES (الـ GMRES الموتر العالمي العشوائي) وطرق Sketched Block Golub–Kahan، وهي الأولى التي تجمع بين حاصلات إينشتاين والتخطيط العشوائي للمعادلات الموترية.
2. تقليل التعقيد: تقلل الطريقة بشكل جذري من التعقيد الحسابي لعمليات التعامد وحسابات الضرب الداخلي عن طريق إسقاط الموترات في فضاءات أقل أبعاداً دون الحاجة لعملية التجهيز (vectorization).
3. التحليل النظري: تقدم الورقة براهين صارمة لـ:
   • تضمين الفضاء الموتري الجزئي: تحديد حدود خطأ التقريب لحاصل الضرب المخطط.
   • حدود القيم المفردة: إثبات أن القيم المفردة للتفريجات الموترية المخططة تظل قريبة من الأصل.
   • حدود البواقي (Residuals): اشتقاق حدود الخطأ للحل المنتظم لتيكونو.
4. الحفاظ على البنية: على عكس الطرق القائمة على التجهيز (vectorization)، يحافظ هذا النهج على البنية متعددة الخطية للبيانات (مثل الارتباطات المكانية والقنوية في الصور)، مما يؤدي إلى نمذجة أكثر دقة.

4. النتائج العددية

تم اختبار الطرق في مهام إزالة الضبابية من صور RGB وترميم الفيديو تحت تأثير ضبابية غاوسية وضجيج غاوسي مضاف.

• مقاييس الأداء: الخطأ النسبي (RE) ونسبة الإشارة إلى الضجيج القصوى (PSNR).
• المقارنة: تمت مقارنة الطرق المخططة المقترحة مع طريقة Tensor GKB الكلاسيكية (بدون تخطيط) وطريقة Einstein Block GMRES القياسية.
• النتائج:
  • الدقة: حققت الطرق المخططة PSNR وخطأً نسبياً مماثلاً أو أفضل قليلاً من الطرق غير المخططة. على سبيل المثال، عند مستوى ضجيج $10^{-3}$، حققت Sketched Block Golub-Kahan قيمة PSNR بلغت 24.42 مقابل 24.22 لطريقة Classical GKB.
  • الكفاءة: كان المكسب الأكبر في وقت المعالجة (CPU time). قللت الطرق المخططة من وقت الحساب بنسبة 40-60%.
    • مثال: استغرقت Sketched Block Golub-Kahan حوالي 3.32 ثانية مقابل 18.45 ثانية لطريقة Classical GKB عند مستويات الضجيج المنخفضة.
  • القابلية للتوسع: كان التسريع متسقاً عبر مستويات الضجيج المختلفة، مما يجعل الطريقة مناسبة جداً للتطبيقات واسعة النطاق والحساسة للوقت.

5. الأهمية

تمثل هذه الورقة طفرة في الحسابات الموترية واسعة النطاق لتطبيقات التصوير.

• الأثر العملي: تتيح ترميم الصور الملونة عالية الدقة وتسلسلات الفيديو التي كانت غير قابلة للتنفيذ حسابياً في السابق بسبب قيود الذاكرة والوقت.
• الابتكار الخوارزمي: من خلال الدمج الناجح لـ التخطيط العشوائي (Randomized Sketching) مع الجبر الموتري، أثبت المؤلفون أنه يمكن التضحية بقدر ضئيل جداً من الدقة (يتحكم به $\epsilon$) لاكتساب كفاءة حسابية هائلة.
• التطبيقات المستقبلية: لا يقتهصر الإطار على ترميم الصور؛ بل يقدم أداة قابلة للتعميم لحل المعادلات التفاضلية الجزئية عالية الأبعاد، والتصوير فائقة الطيف، وغيرها من المشكلات العكسية متعددة الأبعاد حيث يكون الحفاظ على البنية الموترية أمراً حاسماً.

في الختام، توفر طرق فضاء كريفوف الكتلية المخططة (Sketched Einstein Block Krylov methods) توازناً ممتازاً بين الكفاءة والدقة، مما يوفر حلاً قوياً وقابلاً للتوسع لتحديات ترميم البيانات متعددة الأبعاد الحديثة.