Tensor CUR Decomposition under the Linear-Map-Based Tensor-Tensor Multiplication

ملخص تقني: تفكيك Tensor CUR تحت ضرب التنسور-تنسور القائم على الخريطة الخطية

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

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

2. المنهجية

بنى المؤلفون عملهم على إطار ضرب التنسور-تنسور القائم على الخريطة الخطية (الضرب $\ast_M$)، والذي يعمم عملية الضرب (T-product) الكلاسيكية.

• الإطار الجبري: يعامل الضرب $\ast_M$ التنسور من الدرجة الثالثة $\mathcal{A}$ كمجموعة من الشرائح الأمامية ويطبق خريطة خطية $M$ لتحويل التنسور إلى مجال مختلف ($\hat{\mathcal{A}} = \mathcal{A} \times_3 M$). وهذا يسمح لعمليات التنسور بمحاكاة عمليات المصفوفات.
• تفكيك $\ast_M$-CUR المقترح:
  1. اختيار الفهرس: بالنظر إلى التنسور $\mathcal{A}$، يتم اختيار مجموعات فهرس صفوف محددة ($I$) ومجموعات فهرس أعمدة محددة ($J$).
  2. التحويل: يتم تحويل التنسور $\mathcal{A}$ والتنسورات الفرعية الخاصة به (الأعمدة $\mathcal{C}$، والصفوف $\mathcal{R}$، والتقاطع $\mathcal{U}$) إلى المجال المتحول باستخدام حاصل الضرب في النمط 3 مع $M$.
  3. التفكيك على مستوى الشريحة: في المجال المتحول، يتم إجراء تفكيك CUR مصفوفي قياسي على كل شريحة أمامية: $\hat{\mathcal{A}}(k) \approx \hat{\mathcal{C}}(k)(\hat{\mathcal{U}}(k))^+ \hat{\mathcal{R}}(k)$.
  4. إعادة البناء: يتم إعادة بناء التقريب في المجال الأصلي باستخدام الضرب $\ast_M$: $\mathcal{A} \approx \mathcal{C} \ast_M \mathcal{U}^+ \ast_M \mathcal{R}$.
• التحليل النظري: قدم المؤلفون براهين رياضية لـ:
  • الدقة: تحت شرط أن الرتبة المتعددة (multirank) لـ $\mathcal{U}$ تساوي الرتبة المتعددة لـ $\mathcal{A}$ (في حالة كون $M$ قابلة للعكس)، يكون إعادة البناء دقيقاً.
  • حدود الاضطراب: وضعوا حدوداً للخطأ في تقريب $\ast_M$-CUR بحيث يكون الخطأ في تقريب التنسور محدوداً، مما يوسع نتائج اضطراب المصفوفات الكلاسيكية إلى مجال التنسور.

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

• تفكيك جديد: أول تقديم لتفكيك CUR ضمن إطار ضرب التنسور-تنسور القائم على الخريطة الخطية.
• التأسيس النظري: التأسيس الصارم لشروط الدقة واستقرار الاضطراب لطريقة $\ast_M$-CUR.
• تعدد الاستخدامات: أظهرت الطريقة إمكانية تطبيقها عبر أنواع مختلفة من الخرائط الخطية $M$: القابلة للعكس (إعادة بناء دقيقة)، الشمولية (تقريب في الفضاء المسقط)، والداخلية (pseudo-CUR غير التجميعي).
• التنفيذ الخوارزمي: دمج طريقة الاستيفاء التجريبي المنفصل المعتمدة على Q (طريقة Q-DEIM) لاختيار الفهرس بكفاءة أثناء عملية التفكيك.

** 4. النتائج**

قيم المؤلفون الطريقة باستخدام فصل مقدمة وخلفية الفيديو ($\mathcal{X} = \mathcal{L} + \mathcal{S}$، حيث $\mathcal{L}$ منخفض الرتبة و$\mathcal{S}$ متفرق).

• الأداء الكمي: باستخدام مجموعة بيانات SBI، أظهرت طريقة $\ast_M$-CUR أداءً تنافسياً عبر مقاييس مثل متوسط خطأ المستوى الرمادي (AGE)، ونسبة بكسلات الخطأ (pEPs)، ونسبة ذروة الإشارة إلى الضجيج (PSNR). وقد تفوقت باستمرار أو ساوت الطرق الموجودة عبر تحويلات مختلفة (DCT، DFT، DST، و $U_3$ المعتمد على البيانات).
• الأداء النوعي: أظهرت المقارنات البصرية في مجموعة بيانات CDnet أن $\ast_M$-CUR ينتج ضجيجاً بصرياً أقل بكثير وحدود أجسام أكثر حدة مقارنة بـ:
  • CUR المصفوفي القوي (Robust Matrix-wise CUR): الذي احتوى على المزيد من الضجيج.
  • Tensor BM و SS-SVD: اللذين أنتجا آثاراً رأسية ملحوية في إعادة بناء المقدمة.
• الكفاءة: بينما تعد الطريقة فعالة حوسبياً، إلا أن وقت التشغيل يعتمد بشدة على اختيار $M$ (الخرائط الشمولية هي الأسرع والداخلية هي الأبطأ).

5. الأهمية

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