2025-11-16T15:10:11.983649

A note on generalized tensor CUR approximation for tensor pairs and tensor triplets based on the tubal product

Ahmadi-Asl, Rezaeian
In this note, we briefly present a generalized tensor CUR (GTCUR) approximation for tensor pairs (X,Y) and tensor triplets (X,Y,Z) based on the tubal product (t-product). We use the tensor Discrete Empirical Interpolation Method (TDEIM) to do these extensions. We show how the TDEIM can be utilized to generalize the classical tensor CUR (TCUR) approximation, which acts only on a single tensor, to jointly compute the TCUR of two and three tensors. This approach can be used to sample relevant lateral/horizontal slices of one data tensor relative to one or two other data tensors. For some special cases, the Generalized TCUR (GTCUR) approximation is reduced to the classical TCUR for both tensor pairs and tensor triplets in a similar fashion as shown for the matrices.
academic

ملاحظة حول تقريب موتر CUR المعمم لأزواج الموترات والثلاثيات الموترية بناءً على المنتج الأنبوبي

المعلومات الأساسية

  • معرّف الورقة: 2305.00754
  • العنوان: A note on generalized tensor CUR approximation for tensor pairs and tensor triplets based on the tubal product
  • المؤلفون: سلمان أحمدي-أسل (جامعة إينوبوليس)، نعيم رضائيان (جامعة الصداقة بين الشعوب الروسية)
  • التصنيف: math.NA cs.NA
  • وقت النشر: ورقة arXiv، مايو 2023 (أحدث نسخة يناير 2025)
  • رابط الورقة: https://arxiv.org/abs/2305.00754

الملخص

تقترح هذه الورقة طريقة تقريب موتر CUR المعمم (GTCUR) بناءً على المنتج الأنبوبي (t-product) لأزواج الموترات (X,Y) والثلاثيات الموترية (X,Y,Z). يستخدم المؤلفون طريقة الاستيفاء التجريبي المنفصل للموترات (TDEIM) لتحقيق هذه الامتدادات، ويوضحون كيفية استخدام TDEIM لتعميم تقريب موتر CUR الكلاسيكي (TCUR) الذي يعمل على موتر واحد فقط إلى حساب TCUR المشترك لموترين أو ثلاثة موترات. يمكن تطبيق الطريقة على أخذ عينات من الشرائح الجانبية/الأفقية ذات الصلة لموتر بيانات واحد بالنسبة إلى موتر بيانات واحد أو اثنين آخرين.

خلفية البحث والدافع

  1. المشكلة المراد حلها: التحليل الكلاسيكي CUR يمكنه فقط التعامل مع مصفوفة واحدة أو موتر واحد، وغير قادر على التعامل مع هياكل بيانات متعددة مرتبطة في نفس الوقت. في التطبيقات العملية، غالباً ما يكون من الضروري تحليل عدة بيانات موترية مرتبطة في نفس الوقت، واستخراج أكثر الميزات تمييزاً لمجموعة بيانات واحدة بالنسبة إلى مجموعات بيانات أخرى.
  2. أهمية المشكلة:
    • مجموعات البيانات في العالم الحقيقي عادة ما تتمتع بهياكل متعددة الأبعاد، وتتطلب الحفاظ على بنية موتر البيانات
    • في تطبيقات مثل اكتشاف المجموعات الفرعية واستعادة البيانات من الضوضاء الملونة والتحليل الارتباطي القانوني، يلزم التعامل مع عدة موترات في نفس الوقت
    • لا تستطيع الطرق التقليدية الاستفادة الفعالة من المعلومات المشتركة بين عدة موترات
  3. قيود الطرق الموجودة:
    • يمكن لـ CUR للمصفوفات (MCUR) فقط التعامل مع مصفوفة واحدة
    • طرق تحليل الموترات الموجودة مثل تحليل Tucker وتحليل CP لا توفر تقريباً منخفض الرتبة الأمثل عند القطع
    • يفتقر إلى إطار عمل موحد للتعامل مع عدة موترات
  4. دافع البحث: مستوحاة من التطبيق الناجح لـ MCUR المعمم في حالة المصفوفات، يسعى المؤلفون إلى توسيع هذه الفكرة إلى حالة الموترات، والاستفادة من الخصائص الممتازة لـ SVD للموترات بناءً على t-product، وتطوير طريقة GTCUR التي يمكنها التعامل مع عدة موترات في نفس الوقت.

المساهمات الأساسية

  1. اقتراح طريقة موتر CUR المعممة (GTCUR): توسيع تقريب CUR لأول مرة من حالة موتر واحد إلى حالة أزواج الموترات والثلاثيات الموترية
  2. تطوير استراتيجية أخذ العينات بناءً على TDEIM: استخدام طريقة الاستيفاء التجريبي المنفصل للموترات لاختيار الشرائح الجانبية/الأفقية المثلى
  3. إنشاء اتصالات نظرية: إثبات أن GTCUR يمكن أن يتدهور إلى TCUR الكلاسيكي في حالات خاصة، مشابهة لحالة المصفوفات
  4. توفير خوارزميات فعالة: تقديم خوارزميات سريعة لحساب GTCUR، بما في ذلك التنفيذ الفعال في المجال الفوريير
  5. توسيع نظرية تحليل الموترات: إنشاء إطار نظري كامل بناءً على SVD للموترات المعممة (GTSVD) و SVD للموترات المقيدة (t-RSVD)

شرح الطريقة

تعريف المهمة

GTCUR لأزواج الموترات: بالنظر إلى موترين X∈RI1×I2×I3\mathbf{X} \in \mathbb{R}^{I_1 \times I_2 \times I_3} و Y∈RI4×I2×I3\mathbf{Y} \in \mathbb{R}^{I_4 \times I_2 \times I_3}، ابحث عن التقريب: X≈C1∗U1∗R1,Y≈C2∗U2∗R2\mathbf{X} \approx \mathbf{C}_1 \ast \mathbf{U}_1 \ast \mathbf{R}_1, \quad \mathbf{Y} \approx \mathbf{C}_2 \ast \mathbf{U}_2 \ast \mathbf{R}_2

GTCUR لثلاثيات الموترات: بالنظر إلى ثلاثة موترات X∈RI1×I2×I3\mathbf{X} \in \mathbb{R}^{I_1 \times I_2 \times I_3}, Y∈RI1×I4×I3\mathbf{Y} \in \mathbb{R}^{I_1 \times I_4 \times I_3}, Z∈RI5×I2×I3\mathbf{Z} \in \mathbb{R}^{I_5 \times I_2 \times I_3}، ابحث عن التقريبات المقابلة.

معمارية النموذج

1. العمليات الأساسية للموترات

تستند الورقة على المنتج الأنبوبي (t-product) لتعريف سلسلة من عمليات الموترات:

  • المنتج الأنبوبي: C=X∗Y=fold(circ(X)⋅unfold(Y))\mathbf{C} = \mathbf{X} \ast \mathbf{Y} = \text{fold}(\text{circ}(\mathbf{X}) \cdot \text{unfold}(\mathbf{Y}))
  • تبديل الموتر: إجراء تبديل على جميع الشرائح الأمامية وعكس الترتيب
  • موتر متعامد: يرضي XT∗X=X∗XT=I\mathbf{X}^T \ast \mathbf{X} = \mathbf{X} \ast \mathbf{X}^T = \mathbf{I}

2. SVD للموترات (t-SVD)

X≈U∗S∗VT\mathbf{X} \approx \mathbf{U} \ast \mathbf{S} \ast \mathbf{V}^T حيث U\mathbf{U} و V\mathbf{V} موترات متعامدة، و S\mathbf{S} موتر قطري-f.

3. خوارزمية TDEIM

الفكرة الأساسية هي بناء عامل إسقاط الاستيفاء للموترات: P=U∗(ST∗U)−1∗ST\mathbf{P} = \mathbf{U} \ast (\mathbf{S}^T \ast \mathbf{U})^{-1} \ast \mathbf{S}^T

عملية أخذ العينات:

  1. اختر أول هيكل أنبوبي بأكبر معيار إقليدسي
  2. اختر بشكل متكرر الفهرس بأكبر معيار في شريحة البقايا
  3. استخدم عامل الإسقاط لإزالة تأثير الاتجاهات المختارة بالفعل

نقاط الابتكار التقني

  1. إطار عمل موحد لمعالجة عدة موترات: تحقيق التحليل المشترك لعدة موترات من خلال مشاركة مصفوفات العوامل
  2. اختيار الفهرس بناءً على GTSVD: استخدام العوامل المشتركة التي توفرها SVD للموترات المعممة لأخذ عينات متسقة من الشرائح
  3. الحساب الفعال في المجال الفوريير: يمكن تنفيذ جميع العمليات بالتوازي في المجال الترددي، مما يحسن كفاءة الحساب بشكل كبير
  4. ضمانات نظرية: توفير حد أعلى للخطأ ∥X−C∗U∗R∥F2≤(η~p+η~q)∑i=1I3∑t>R(σti)2\|\mathbf{X}-\mathbf{C} \ast \mathbf{U} \ast \mathbf{R}\|_F^2 \leq (\tilde{\eta}_p + \tilde{\eta}_q)\sum_{i=1}^{I_3}\sum_{t>R}(\sigma_t^i)^2

إعداد التجارب

التحقق النظري

توفر الورقة بشكل أساسي تحليلاً نظرياً وإطار عمل خوارزمي، بما في ذلك:

مؤشرات التقييم

  • الحد الأعلى النظري لخطأ التقريب
  • تحليل التعقيد الحسابي
  • التحكم في رقم الشرط

طرق المقارنة

  • موتر CUR الكلاسيكي (TCUR)
  • طريقة أخذ العينات بناءً على درجات الرافعة
  • طريقة أخذ العينات الموحدة

تفاصيل التنفيذ

  • استخدام تحويل فوريير السريع (FFT) لتنفيذ t-product
  • اعتماد GTSVD عشوائي لتقليل التعقيد الحسابي
  • توفير وصف الخوارزمية بأسلوب MATLAB

نتائج التجارب

النتائج الرئيسية

توفر الورقة بشكل أساسي النتائج النظرية:

  1. النظرية 1: حد أعلى لخطأ تقريب TCUR بأخذ عينات TDEIM
  2. النظرية 3: العلاقة بين GTCUR لأزواج الموترات و TCUR الكلاسيكي
  3. النظرية 4: تحليل الحالات الخاصة لـ GTCUR لثلاثيات الموترات

الاكتشافات النظرية

  1. عندما Y=I\mathbf{Y} = \mathbf{I}، يتدهور GTCUR إلى TCUR الكلاسيكي
  2. بالنسبة للموتر القابل للعكس Y\mathbf{Y}، يكافئ GTCUR TCUR لـ X∗Y−1\mathbf{X} \ast \mathbf{Y}^{-1}
  3. يتم التحكم في رقم الشرط بواسطة η~p\tilde{\eta}_p و η~q\tilde{\eta}_q

الأعمال ذات الصلة

الاتجاهات البحثية الرئيسية

  1. تحليل CUR للمصفوفات: الأعمال الكلاسيكية لـ Goreinov وآخرين
  2. تحليل الموترات: تحليل Tucker وتحليل CP وتحليل tensor-train
  3. الطرق القائمة على t-product: الإطار الذي أسسه Kilmer وآخرون
  4. SVD المعممة: GSVD و RSVD في حالة المصفوفات

الابتكار في هذه الورقة

مقارنة بالأعمال الموجودة، تقوم هذه الورقة لأول مرة بـ:

  • توسيع تحليل CUR إلى حالة عدة موترات
  • إنشاء إطار نظري كامل بناءً على t-product
  • توفير خوارزمية أخذ عينات TDEIM فعالة

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. توسيع ناجح لتقريب CUR من حالة موتر واحد إلى أزواج الموترات والثلاثيات الموترية
  2. توفير TDEIM استراتيجية أخذ عينات مثلى
  3. إطار نظري كامل يتضمن تحليل الخطأ والاتصالات في الحالات الخاصة
  4. خوارزمية فعالة، يمكن حسابها بالتوازي في المجال الفوريير

القيود

  1. نقص التجارب العددية: الورقة نظرية بشكل أساسي، بدون توفير التحقق العددي المحدد
  2. التعقيد الحسابي: حساب GTSVD لا يزال يمثل تحدياً للموترات الكبيرة الحجم
  3. سيناريوهات التطبيق: نقص التحليل التفصيلي لسيناريوهات التطبيق المحددة
  4. اختيار المعاملات: لم يتم مناقشة استراتيجية اختيار معامل الرتبة R

الاتجاهات المستقبلية

  1. التحقق من فعالية الطريقة في التطبيقات العملية
  2. تطوير خوارزميات عشوائية أكثر كفاءة
  3. دراسة استراتيجيات اختيار المعاملات التكيفية
  4. التوسع إلى حالة الموترات ذات الرتب الأعلى

التقييم المتعمق

المميزات

  1. مساهمة نظرية كبيرة: إنشاء إطار نظري كامل لتحليل CUR متعدد الموترات لأول مرة
  2. طريقة مبتكرة: استخدام ذكي للعوامل المشتركة لـ GTSVD لتحقيق معالجة مشتركة لعدة موترات
  3. خوارزمية فعالة: يضمن التنفيذ القائم على FFT كفاءة الحساب
  4. نظرية صارمة: توفير تحليل خطأ شامل وضمانات التقارب
  5. كتابة واضحة: بنية الورقة واضحة والاشتقاقات الرياضية صارمة

أوجه القصور

  1. نقص التحقق التجريبي: كملاحظة نظرية، تفتقر إلى التجارب العددية للتحقق من فعالية الطريقة العملية
  2. دافع التطبيق غير كافٍ: على الرغم من ذكر بعض التطبيقات، لم يتم مناقشة سيناريوهات التطبيق المحددة بعمق
  3. مشاكل قابلية التوسع: بالنسبة للموترات الكبيرة جداً، يبقى حساب GTSVD عنق الزجاجة
  4. حساسية المعاملات: لم يتم مناقشة حساسية الطريقة لاختيار المعاملات

التأثير

  1. القيمة النظرية: توفير أدوات نظرية جديدة لتحليل عدة موترات
  2. الإمكانات العملية: آفاق تطبيق في مجالات معالجة الصور وتحليل الإشارات
  3. قابلية إعادة الإنتاج: توفير وصف خوارزمي تفصيلي يسهل التنفيذ
  4. البحث اللاحق: وضع أساس متين للبحث الإضافي في المجالات ذات الصلة

السيناريوهات القابلة للتطبيق

  1. تحليل البيانات متعددة الأنماط: السيناريوهات التي تتطلب التعامل مع عدة بيانات موترية مرتبطة في نفس الوقت
  2. اختيار الميزات: استخراج ميزات تمييزية لمجموعة بيانات واحدة بالنسبة إلى مجموعات بيانات أخرى
  3. استعادة البيانات من الضوضاء: استخدام البنية المشتركة لعدة موترات لاستعادة البيانات
  4. تقليل الأبعاد: تقليل الأبعاد مع الحفاظ على بنية الموتر

المراجع

تستشهد الورقة بـ 24 مرجعاً مهماً، تتضمن بشكل أساسي:

  • الأعمال الكلاسيكية لـ Goreinov وآخرين حول تحليل CUR
  • الأبحاث الرائدة لـ Kilmer وآخرين حول t-product
  • أحدث أعمال Gidisu و Hochstenbach حول GMCUR للمصفوفات
  • الأدبيات ذات الصلة بطرق تحليل الموترات المختلفة

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