k -SVD

في الرياضيات التطبيقية ، تُعدّ خوارزمية k -SVD خوارزمية لتعلم القواميس تُستخدم لإنشاء قاموس للتمثيلات المتفرقة ، وذلك من خلال أسلوب تحليل القيم المفردة . تُعتبر k -SVD تعميمًا لطريقة التجميع k -means ، وتعمل بالتناوب التكراري بين ترميز البيانات المدخلة بشكل متفرق بناءً على القاموس الحالي، وتحديث عناصر القاموس لتحسين ملاءمتها للبيانات. وهي ترتبط بنيويًا بخوارزمية التوقع والتعظيم (EM) . ^{[ 1 ] [ 2 ]} تُستخدم k -SVD على نطاق واسع في تطبيقات مثل معالجة الصور، ومعالجة الصوت ، وعلم الأحياء، وتحليل المستندات.

يُعدّ تحليل القيم المفردة k -SVD نوعًا من تعميم خوارزمية k -means، كما يلي. ويمكن اعتبار خوارزمية k -means أيضًا طريقةً للتمثيل المتفرق ، أي إيجاد أفضل دفتر رموز ممكن لتمثيل عينات البيانات.${\displaystyle \{y_{i}\}_{i=1}^{M}}$ عن طريق أقرب جار ، عن طريق الحل

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\forall i,x_{i}=e_{k}{\text{ for some }}k.}$

وهو ما يعادل تقريبًا

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i,\|x_{i}\|_{0}=1}$

وهو خوارزمية k-means التي تسمح بـ "الأوزان".

يرمز الحرف F إلى معيار فروبينيوس . مصطلح التمثيل المتفرق${\displaystyle x_{i}=e_{k}}$يفرض خوارزمية k -means استخدام ذرة واحدة (عمود واحد) فقط في القاموس${\displaystyle D}$ولتخفيف هذا القيد، يهدف خوارزمية k -SVD إلى تمثيل الإشارة كمزيج خطي من الذرات في${\displaystyle D}$.

تتبع خوارزمية k -SVD نفس مسار بناء خوارزمية k -means. ومع ذلك، وعلى عكس k -means، فإنه من أجل تحقيق توليفة خطية من الذرات في${\displaystyle D}$يتم تخفيف شرط التباعد في القيد بحيث يكون عدد المدخلات غير الصفرية في كل عمود${\displaystyle x_{i}}$يمكن أن يكون أكبر من 1، ولكنه أقل من عدد${\displaystyle T_{0}}$.

وبذلك، تصبح دالة الهدف

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i\;,\|x_{i}\|_{0}\leq T_{0}.}$

أو بصورة موضوعية أخرى

${\displaystyle \quad \min \limits _{D,X}\sum _{i}\|x_{i}\|_{0}\qquad {\text{subject to }}\quad \forall i\;,\|Y-DX\|_{F}^{2}\leq \epsilon .}$

في خوارزمية k -SVD،${\displaystyle D}$يتم أولاً تثبيت مصفوفة المعاملات الأفضل${\displaystyle X}$يتم العثور عليه. كما هو الحال في إيجاد الحل الأمثل حقًا${\displaystyle X}$إذا كان الأمر صعبًا، نستخدم طريقة البحث التقريبي. يمكن استخدام أي خوارزمية، مثل خوارزمية البحث المطابق المتعامد (OMP)، لحساب المعاملات، طالما أنها قادرة على توفير حل بعدد ثابت ومحدد مسبقًا من المدخلات غير الصفرية.${\displaystyle T_{0}}$.

بعد مهمة الترميز المتفرق، تأتي الخطوة التالية وهي البحث عن قاموس أفضل.${\displaystyle D}$ومع ذلك، فإن العثور على القاموس بأكمله في وقت واحد أمر مستحيل، لذا فإن العملية تتمثل في تحديث عمود واحد فقط من القاموس.${\displaystyle D}$في كل مرة، أثناء الإصلاح${\displaystyle X}$تحديث${\displaystyle k}$يتم تنفيذ العمود رقم -th عن طريق إعادة كتابة مصطلح الجزاء على النحو التالي:

$\displaystyle \|Y-DX\|_{F}^{2}=\left\|Y-\sum _{j=1}^{K}d_{j}x_{j}^{\text{T}}\right\|_{F}^{2}=\left\|\left(Y-\sum _{j\neq k}d_{j}x_{j}^{\text{T}}\right)-d_{k}x_{k}^{\text{T}}\right\|_{F}^{2}=\|E_{k}-d_{k}x_{k}^{\text{T}}\|_{F}^{2}}$

أين${\displaystyle x_{k}^{\text{T}}}$يشير إلى الصف رقم k من X.

عن طريق تحليل عملية الضرب${\displaystyle DX}$إلى مجموع${\displaystyle K}$بالنسبة للمصفوفات من الرتبة 1، يمكننا افتراض الأخرى${\displaystyle K-1}$تُفترض الشروط ثابتة، و${\displaystyle k}$لا يزال الرقم -th غير معروف. بعد هذه الخطوة، يمكننا حل مشكلة التصغير عن طريق تقريب${\displaystyle E_{k}}$مصطلح مع ${\displaystyle rank-1}$المصفوفة باستخدام تحليل القيم المفردة ، ثم تحديثها${\displaystyle d_{k}}$ومع ذلك، فإن الحل الجديد للمتجه${\displaystyle x_{k}^{\text{T}}}$ليس من المؤكد أن يكون متفرقاً.

لحل هذه المشكلة، حدد${\displaystyle \omega _{k}}$مثل

${\displaystyle \omega _{k}=\{i\mid 1\leq i\leq N,x_{k}^{\text{T}}(i)\neq 0\},}$

وهذا يشير إلى أمثلة${\displaystyle \{y_{i}\}_{i=1}^{N}}$التي تستخدم الذرة${\displaystyle d_{k}}$(وأيضًا مدخلات${\displaystyle x_{i}}$(أي غير صفري). ثم، حدد${\displaystyle \Omega _{k}}$كمصفوفة بحجم${\displaystyle N\times |\omega _{k}|}$، مع وجود البعض على${\displaystyle (i,\omega _{k}(i)){\text{th}}}$المدخلات، والأصفار في غير ذلك. عند الضرب${\displaystyle {\tilde {x}}_{k}^{\text{T}}=x_{k}^{\text{T}}\Omega _{k}}$وهذا يؤدي إلى تقليص متجه الصف${\displaystyle x_{k}^{\text{T}}}$عن طريق استبعاد المدخلات الصفرية. وبالمثل، فإن عملية الضرب${\displaystyle {\tilde {Y}}_{k}=Y\Omega _{k}}$هي مجموعة فرعية من الأمثلة التي تستخدم حاليًا${\displaystyle d_{k}}$الذرة. ويمكن ملاحظة التأثير نفسه على${\displaystyle {\tilde {E}}_{k}=E_{k}\Omega _{k}}$.

وبالتالي تصبح مسألة التصغير كما ذكرنا سابقاً

${\displaystyle \|E_{k}\Omega _{k}-d_{k}x_{k}^{\text{T}}\Omega _{k}\|_{F}^{2}=\|{\tilde {E}}_{k}-d_{k}{\tilde {x}}_{k}^{\text{T}}\|_{F}^{2}}$

ويمكن القيام بذلك مباشرةً باستخدام تحليل القيم المفردة (SVD). يقوم تحليل القيم المفردة بتحليل${\displaystyle {\tilde {E}}_{k}}$داخل${\displaystyle U\Delta V^{\text{T}}}$الحل لـ${\displaystyle d_{k}}$يمثل العمود الأول من المتجه U، متجه المعاملات${\displaystyle {\tilde {x}}_{k}^{\text{T}}}$كأول عمود من${\displaystyle V\times \Delta (1,1)}$بعد تحديث القاموس بأكمله، تتحول العملية بعد ذلك إلى حل X بشكل متكرر، ثم حل D بشكل متكرر.

يُعدّ اختيار "قاموس" مناسب لمجموعة بيانات مسألة غير محدبة، ويعمل تحليل القيم المفردة k -SVD من خلال تحديث تكراري لا يضمن إيجاد الحل الأمثل الشامل. ^{[ 2 ]} ومع ذلك، فإن هذا الأمر شائع في الخوارزميات الأخرى المُستخدمة لهذا الغرض، ويُحقق تحليل القيم المفردة k -SVD نتائج جيدة إلى حدٍّ ما في التطبيق العملي. ^{[ 2 ]}

• التقريب المتفرق
• تحليل القيم المفردة
• معيار المصفوفة
• التجميع باستخدام خوارزمية k -means
• تقريب الرتبة المنخفضة