مطاردة متطابقة

خوارزمية البحث عن التطابق ( MP ) هي خوارزمية تقريبية متفرقة تجد أفضل إسقاطات "مطابقة" للبيانات متعددة الأبعاد على نطاق قاموس مكتمل بشكل زائد (أي زائد عن الحاجة).${\displaystyle D}$الفكرة الأساسية هي تمثيل الإشارة تقريبًا${\displaystyle f}$من فضاء هيلبرت${\displaystyle H}$كمجموع مرجح لعدد محدود من الدوال${\displaystyle g_{\gamma _{n}}}$(تسمى الذرات) مأخوذة من${\displaystyle D}$تقريب مع${\displaystyle N}$الذرات لها الشكل

${\displaystyle f(t)\approx {\hat {f}}_{N}(t):=\sum _{n=1}^{N}a_{n}g_{\gamma _{n}}(t)}$

أين${\displaystyle g_{\gamma _{n}}}$هو${\displaystyle \gamma _{n}}$العمود رقم 1 من المصفوفة${\displaystyle D}$و${\displaystyle a_{n}}$يمثل عامل الترجيح القياسي (السعة) للذرة${\displaystyle g_{\gamma _{n}}}$عادةً، ليس كل ذرة في${\displaystyle D}$سيتم استخدام هذه القيمة في هذا المجموع. بدلاً من ذلك، تختار خوارزمية البحث المطابق الذرات واحدة تلو الأخرى لتقليل خطأ التقريب إلى أقصى حد (بشكل جشع) . ويتحقق ذلك من خلال إيجاد الذرة التي لها أعلى حاصل ضرب داخلي مع الإشارة (بافتراض أن الذرات مُعَيَّرة)، وطرح تقريب من الإشارة يستخدم تلك الذرة فقط، وتكرار العملية حتى يتم تحليل الإشارة بشكل مُرضٍ، أي أن معيار الباقي صغير، حيث يكون الباقي بعد الحساب${\displaystyle \gamma _{N}}$و${\displaystyle a_{N}}$يُرمز إليه بـ

${\displaystyle R_{N+1}=f-{\hat {f}}_{N}}$.

لو${\displaystyle R_{n}}$إذا تقاربت بسرعة إلى الصفر، فلن نحتاج إلا إلى عدد قليل من الذرات للحصول على تقريب جيد لـ${\displaystyle f}$تُعدّ هذه التمثيلات المتفرقة مرغوبة لترميز الإشارات وضغطها. وبشكل أدق، فإن مشكلة التفرق التي يهدف البحث المطابق إلى حلها تقريبًا هي

${\displaystyle \min _{x}\|f-Dx\|_{2}^{2}\ {\text{ بشرط }}\ \|x\|_{0}\leq N,}$

أين${\displaystyle \|x\|_{0}}$هو${\displaystyle L_{0}}$المعيار الزائف (أي عدد العناصر غير الصفرية من${\displaystyle x}$في الترميز السابق، المدخلات غير الصفرية لـ${\displaystyle x}$نكون${\displaystyle x_{\gamma _{n}}=a_{n}}$إن حل مشكلة التباعد بدقة هو أمر صعب من نوع NP ، ولهذا السبب يتم استخدام طرق التقريب مثل MP.

للمقارنة، لنأخذ تمثيل تحويل فورييه للإشارة كمثال - يمكن وصفه باستخدام المصطلحات المذكورة أعلاه، حيث يُبنى القاموس من دوال أساسية جيبية (أصغر قاموس كامل ممكن). يتمثل العيب الرئيسي لتحليل فورييه في معالجة الإشارات في أنه يستخلص فقط السمات العامة للإشارات ولا يتكيف مع الإشارات المُحللة.${\displaystyle f}$باستخدام قاموس شديد التكرار، يمكننا البحث فيه عن الذرات (الدوال) التي تتطابق بشكل أفضل مع الإشارة.${\displaystyle f}$.

لو${\displaystyle D}$يحتوي على عدد كبير من المتجهات، يبحث عن التمثيل الأكثر تباعدًا لـ${\displaystyle f}$غير مقبول حسابيًا للتطبيقات العملية. في عام 1993، اقترح مالات وتشانغ ^{[ 1 ]} حلاً جشعًا أطلقوا عليه اسم "المطاردة المطابقة". لأي إشارة${\displaystyle f}$وأي قاموس${\displaystyle D}$، تقوم الخوارزمية بشكل متكرر بإنشاء قائمة مرتبة من مؤشرات الذرات ومعاملات الترجيح، والتي تشكل الحل الأمثل لمشكلة تمثيل الإشارة المتفرقة.

خوارزمية البحث عن المطابقة المدخلات: الإشارة:${\displaystyle f(t)}$قاموس${\displaystyle D}$مع أعمدة مُعَيَّرة${\displaystyle g_{i}}$. الناتج: قائمة المعاملات${\displaystyle (a_{n})_{n=1}^{N}}$ومؤشرات الذرات المقابلة${\displaystyle (\gamma _{n})_{n=1}^{N}}$. التهيئة: ${\displaystyle R_{1}\,\leftarrow \,f(t)}$؛ ${\displaystyle n\,\leftarrow \,1}$؛ يكرر: يجد${\displaystyle g_{\gamma _{n}}\in D}$مع أقصى قدر من المنتج الداخلي${\displaystyle |\langle R_{n},g_{\gamma _{n}}\rangle |}$؛ ${\displaystyle a_{n}\,\leftarrow \,\langle R_{n},g_{\gamma _{n}}\rangle }$؛ ${\displaystyle R_{n+1}\,\leftarrow \,R_{n}-a_{n}g_{\gamma _{n}}}$؛ ${\displaystyle n\,\leftarrow \,n+1}$؛ حتى الوصول إلى شرط التوقف (على سبيل المثال:${\displaystyle \|R_{n}\|<\mathrm {العتبة} }$) يعود

في معالجة الإشارات، يرتبط مفهوم البحث المطابق بالبحث عن الإسقاط الإحصائي ، حيث يتم العثور على الإسقاطات "المثيرة للاهتمام"؛ وتعتبر تلك التي تنحرف أكثر عن التوزيع الطبيعي أكثر إثارة للاهتمام.

• تتقارب الخوارزمية (أي${\displaystyle R_{n}\to 0}$) لأي${\displaystyle f}$هذا يقع ضمن المساحة التي يغطيها القاموس.
• الخطأ${\displaystyle \|R_{n}\|}$يتناقص بشكل رتيب.
• بما أن الباقي في كل خطوة يكون متعامدًا مع المرشح المحدد، فإن معادلة حفظ الطاقة تتحقق لكل${\displaystyle N}$:

${\displaystyle \|f\|^{2}=\|R_{N+1}\|^{2}+\sum _{n=1}^{N}{|a_{n}|^{2}}}$.

• في حالة أن المتجهات في${\displaystyle D}$إذا كانت متعامدة، وليست زائدة، فإن MP هو شكل من أشكال تحليل المكونات الرئيسية

طُبقت خوارزمية البحث المطابق على ترميز الإشارات والصور ^{[ 2 ]} والفيديو، ^{[ 3 ] [ 4 ]} وتمثيل الأشكال والتعرف عليها، ^{[ 5 ]} وترميز الأجسام ثلاثية الأبعاد، ^{[ 6 ]} وفي تطبيقات متعددة التخصصات مثل مراقبة سلامة الهياكل. ^{[ 7 ]} وقد ثبت أنها تتفوق على الترميز القائم على تحويل جيب التمام المنفصل (DCT) عند معدلات بت منخفضة، وذلك من حيث كفاءة الترميز وجودة الصورة. ^{[ 8 ]} تكمن المشكلة الرئيسية في خوارزمية البحث المطابق في التعقيد الحسابي للمُشفِّر. ففي النسخة الأساسية من الخوارزمية، يلزم البحث في قاموس كبير في كل تكرار. وتشمل التحسينات استخدام تمثيلات تقريبية للقاموس وطرقًا شبه مثالية لاختيار أفضل تطابق في كل تكرار (استخراج الذرات). ^{[ 9 ]} تُستخدم خوارزمية البحث المطابق في MP/SOFT، وهي طريقة لمحاكاة الديناميكيات الكمومية . ^{[ 10 ]}

يُستخدم MP أيضًا في تعلم القاموس . ^{[ 11 ] [ 12 ]} في هذه الخوارزمية، يتم تعلم الذرات من قاعدة بيانات (بشكل عام، مشاهد طبيعية مثل الصور المعتادة) ولا يتم اختيارها من قواميس عامة.

أحد التطبيقات الحديثة جدًا لـ MP هو استخدامه في ترميز الحساب الخطي ^{[ 13 ]} لتسريع حساب حاصل ضرب المصفوفة في المتجه.

يُعدّ امتداد خوارزمية المطابقة المتعامدة (OMP) أحد أشهر امتدادات هذه الخوارزمية ^{[ 14 ] [ 15 ]} . ويكمن الاختلاف الرئيسي بينها وبين خوارزمية المطابقة المتعامدة في أنه بعد كل خطوة، يتم تحديث جميع المعاملات المستخرجة حتى الآن، وذلك بحساب الإسقاط المتعامد للإشارة على الفضاء الفرعي الذي تشكله مجموعة الذرات المختارة. قد يؤدي هذا إلى نتائج أفضل من خوارزمية المطابقة المتعامدة القياسية، ولكنه يتطلب حسابات أكثر. وقد ثبت أن خوارزمية المطابقة المتعامدة تتمتع بضمانات للاستقرار والأداء في ظل شروط قياس متساوية محددة . ^{[ 16 ]} وتعمل خوارزمية المعاملات المتعددة التزايدية (IMP)، التي نُشرت قبل ثلاث سنوات من خوارزمية المطابقة المتعامدة، بنفس طريقة خوارزمية المطابقة المتعامدة. ^{[ 17 ]}

تتيح امتدادات مثل Multichannel MP ^{[ 18 ]} وMultichannel OMP ^{[ 19 ]} معالجة الإشارات متعددة المكونات. ومن الامتدادات الواضحة لخوارزمية المطابقة التتبعية (Matching Pursuit) معالجة الإشارات عبر مواضع ومقاييس متعددة، وذلك بتوسيع القاموس ليصبح أساسًا موجيًا. ويمكن تحقيق ذلك بكفاءة باستخدام عامل الالتفاف دون تغيير الخوارزمية الأساسية. ^{[ 20 ]}

يرتبط البحث المطابق بمجال الاستشعار المضغوط ، وقد طوّره باحثون في هذا المجال. ومن أبرز هذه التطويرات: البحث المطابق المتعامد (OMP) ^{[ 21 ]} ، والبحث المطابق المتدرج (StOMP) ^{[ 22 ]} ، والبحث المطابق باستخدام أخذ العينات المضغوطة (CoSaMP) ^{[ 23 ]} ، والبحث المطابق المعمم (gOMP) ^{[ 24 ]} ، والبحث المطابق متعدد المسارات (MMP) ^{[ 25 ] .}

• خوارزمية CLEAN
• معالجة الصور
• تحليل الطيف باستخدام طريقة المربعات الصغرى
• تحليل المكونات الرئيسية (PCA)
• تتبع الإسقاط
• معالجة الإشارات
• التقريب المتفرق
• الانحدار التدريجي