طريقة كاتشمارتز

لدينا

${\displaystyle \forall z\in \mathbb {C} ^{n}:\quad \sum _{j=1}^{m}|\langle z,a_{j}\rangle |^{2}\geq {\frac {\|z\|^{2}}{\|A^{-1}\|^{2}}}}$

2

استخدام

${\displaystyle \|A\|^{2}=\sum _{j=1}^{m}\|a_{j}\|^{2}}$

يمكننا كتابة ( 2 ) على النحو التالي

${\displaystyle \forall z\in \mathbb {C} ^{n}:\quad \sum _{j=1}^{m}{\frac {\|a_{j}\|^{2}}{\|A\|^{2}}}\left|\left\langle z,{\frac {a_{j}}{\|a_{j}\|}}\right\rangle \right|^{2}\geq \kappa (A)^{-2}{\|z\|^{2}}}$

3

تتمثل الفكرة الرئيسية للبرهان في اعتبار الطرف الأيسر من المعادلة ( 3 ) بمثابة القيمة المتوقعة لمتغير عشوائي ما . وبالتحديد، تذكر أن فضاء حلول المعادلة (3) هو فضاء الحلول لـ${\displaystyle j-th}$معادلة${\displaystyle Ax=b}$هو المستوى الفائق

${\displaystyle \{y:\langle y,a_{j}\rangle =b_{j}\},}$

الذي هو طبيعي${\displaystyle {\tfrac {a_{j}}{\|a_{j}\|^{2}}}.}$عرّف متجهًا عشوائيًا Z تكون قيمه هي المتجهات العمودية على جميع معادلات${\displaystyle Ax=b}$، باحتمالات كما في خوارزميتنا:

${\displaystyle Z={\frac {a_{j}}{\|a_{j}\|}}}$باحتمال${\displaystyle {\frac {\|a_{j}\|^{2}}{\|A\|^{2}}}\qquad \qquad \qquad j=1,\ldots ,m}$

ثم يقول ( 3 ) أن

${\displaystyle \forall z\in \mathbb {C} ^{n}:\quad \mathbb {E} |\langle z,Z\rangle |^{2}\geq \kappa (A)^{-2}{\|z\|^{2}}}$

4

الإسقاط المتعامد${\displaystyle P}$على فضاء حلول معادلة عشوائية من${\displaystyle Ax=b}$يُعطى بواسطة${\displaystyle Pz=z-\langle z-x,Z\rangle Z.}$

الآن نحن جاهزون لتحليل خوارزميتنا. نريد أن نوضح أن الخطأ${\displaystyle {\|x_{k}-x\|^{2}}}$ينخفض ​​في كل خطوة في المتوسط ​​(بشرط الخطوات السابقة) بمقدار لا يقل عن عامل${\displaystyle (1-\kappa (A)^{-2}).}$التقريب التالي${\displaystyle x_{k}}$يتم حسابها من${\displaystyle x_{k-1}}$مثل${\displaystyle x_{k}=P_{k}x_{k-1},}$أين${\displaystyle P_{1},P_{2},\ldots }$هي تحقيقات مستقلة للإسقاط العشوائي${\displaystyle P.}$المتجه${\displaystyle x_{k-1}-x_{k}}$يوجد في جوهر${\displaystyle P_{k}.}$وهو متعامد مع فضاء حل المعادلة التي عليه${\displaystyle P_{k}}$المشاريع، التي تحتوي على المتجه${\displaystyle x_{k}-x}$(تذكر أن${\displaystyle x}$(وهو حل جميع المعادلات). ومن ثم، فإن تعامد هذين المتجهين ينتج عنه

${\displaystyle \|x_{k}-x\|^{2}=\|x_{k-1}-x\|^{2}-\|x_{k-1}-x_{k}\|^{2}.}$

لإكمال البرهان، علينا أن نحدد${\displaystyle \|x_{k-1}-x_{k}\|^{2}}$من الأسفل. بحسب تعريف${\displaystyle x_{k}}$لدينا

${\displaystyle \|x_{k-1}-x_{k}\|=\langle x_{k-1}-x,Z_{k}\rangle }$

أين${\displaystyle Z_{1},Z_{2},\ldots }$هي تحققات مستقلة للمتجه العشوائي${\displaystyle Z.}$

هكذا

${\displaystyle \|x_{k}-x\|^{2}\leq \left(1-\left|\left\langle {\frac {x_{k-1}-x}{\|x_{k-1}-x\|}},Z_{k}\right\rangle \right|^{2}\right){\|x_{k-1}-x\|^{2}}.}$

الآن نأخذ القيمة المتوقعة لكلا الطرفين بشرط اختيار المتجهات العشوائية${\displaystyle Z_{1},\ldots ,Z_{k-1}}$(وبالتالي نحدد اختيار الإسقاطات العشوائية)${\displaystyle P_{1},\ldots ,P_{k-1}}$وبالتالي المتجهات العشوائية${\displaystyle x_{1},\ldots ,x_{k-1}}$ونقوم بحساب المتوسط ​​على المتجه العشوائي${\displaystyle Z_{k}}$). ثم

${\displaystyle \mathbb {E} _{Z_{1},\ldots ,Z_{k-1}}{\|x_{k}-x\|^{2}}=\left(1-\mathbb {E} _{Z_{1},\ldots ,Z_{k-1},Z_{k}}\left|\left\langle {\frac {x_{k-1}-x}{\|x_{k-1}-x\|}},Z_{k}\right\rangle \right|^{2}\right){\|x_{k-1}-x\|^{2}}.}$

( 4 ) والاستقلال،

${\displaystyle \mathbb {E} _{Z_{1},\ldots ,Z_{k-1}}{\|x_{k}-x\|^{2}}\leq (1-\kappa (A)^{-2}){\|x_{k-1}-x\|^{2}}.}$

وبأخذ توقعات كلا الجانبين بعين الاعتبار، نستنتج أن

${\displaystyle \mathbb {E} \|x_{k}-x\|^{2}\leq (1-\kappa (A)^{-2})\mathbb {E} {\|x_{k-1}-x\|^{2}}.\blacksquare }$

تجلّت أفضلية هذا الاختيار في إعادة بناء دالة محدودة النطاق من قيم عينات ذات تباعد غير منتظم. مع ذلك، أشير ^{[ 10 ]} إلى أن النجاح الذي حققه سترومر وفيرشينين يعتمد على الخيارات المحددة التي اتُخذت في ترجمة المسألة الأساسية، التي تتمثل طبيعتها الهندسية في إيجاد نقطة مشتركة لمجموعة من المستويات الفائقة ، إلى نظام من المعادلات الجبرية. وستظل هناك دائمًا تمثيلات جبرية مشروعة للمسألة الأساسية، والتي سيُظهر فيها أسلوب الاختيار في ^{[ 8 ]} أداءً أقل كفاءة. ^{[ 8 ] [ 10 ] [ 11 ]}

تُفسَّر عملية تكرار كازمارز ( 1 ) تفسيرًا هندسيًا بحتًا: إذ تُسقط الخوارزمية التكرار الحالي تباعًا على المستوى الفائق المُعرَّف بالمعادلة التالية. وبالتالي، فإن أي تغيير في مقياس المعادلات غير ذي صلة؛ ويمكن أيضًا ملاحظة من ( 1 ) أن أي تغيير (غير صفري) في مقياس المعادلات يُلغي نفسه. لذا، في خوارزمية كازمارز، يمكن استخدام${\displaystyle \|a_{i}\|}$أو أي أوزان أخرى قد تكون ذات صلة. تحديدًا، في مثال إعادة البناء المذكور أعلاه، تم اختيار المعادلات باحتمالية تتناسب مع متوسط ​​المسافة بين كل نقطة عينة وأقرب جارين لها - وهو مفهوم قدمه فيشتينجر وغروتشينيج . لمزيد من المعلومات حول هذا الموضوع، انظر ^{[ 12 ]} و ^{[ 13 ]} والمراجع الواردة فيهما.

تتضمن الأفكار الجديدة والمثيرة للاهتمام حول طريقة كازمارز العشوائية التي يمكن الحصول عليها من تحليل هذه الطريقة ما يلي:

• إن المعدل العام لخوارزمية Gower-Richtarik يستعيد بدقة معدل طريقة Kaczmarz العشوائية في الحالة الخاصة التي تم اختزالها إليها.
• إن اختيار الاحتمالات التي صِيغت وحُلِّلت من أجلها خوارزمية كازمارز العشوائية في الأصل (الاحتمالات المتناسبة مع مربعات معايير الصفوف) ليس الأمثل. الاحتمالات المثلى هي حل برنامج شبه محدد معين. يمكن أن يكون التعقيد النظري لخوارزمية كازمارز العشوائية بالاحتمالات المثلى أفضل بكثير من تعقيدها بالاحتمالات القياسية. ومع ذلك، فإن مقدار هذا التحسن يعتمد على المصفوفة.${\displaystyle A}$هناك مشاكل تكون فيها الاحتمالات القياسية هي الأمثل.
• عند تطبيقها على نظام ذي مصفوفة${\displaystyle A}$وهي دالة موجبة محددة، فإن طريقة كازمارز العشوائية مكافئة لطريقة التدرج العشوائي (SGD) (مع حجم خطوة خاص جدًا) لتقليل الدالة التربيعية المحدبة بقوة${\displaystyle f(x)={\tfrac {1}{2}}x^{T}Ax-b^{T}x.}$لاحظ ذلك منذ${\displaystyle f}$إذا كانت محدبة، فإن القيم الصغرى لـ${\displaystyle f}$يجب أن يفي${\displaystyle \nabla f(x)=0}$وهو ما يعادل${\displaystyle Ax=b.}$"حجم الخطوة الخاص" هو حجم الخطوة الذي يؤدي إلى نقطة تُقلل، على الخط أحادي البعد الذي يمتد عليه التدرج العشوائي، المسافة الإقليدية من المُصغِّر المجهول (!) لـ${\displaystyle f}$أي من${\displaystyle x^{*}=A^{-1}b.}$يتم الحصول على هذه الرؤية من خلال منظور مزدوج للعملية التكرارية (الموصوفة أدناه باسم "وجهة نظر التحسين: التقييد والتقريب").

تتميز طريقة غاور-ريشتاريك بستة صيغ تبدو مختلفة ولكنها متكافئة، مما يلقي مزيدًا من الضوء على كيفية تفسيرها (وبالتالي، كيفية تفسير متغيراتها العديدة، بما في ذلك طريقة كازمارز العشوائية):

• 1. وجهة نظر الرسم التخطيطي: الرسم التخطيطي والمشروع
• 2. وجهة نظر التحسين: التقييد والتقريب
• 3. وجهة نظر هندسية: تقاطع عشوائي
• 4. المنظور الجبري 1: حل المعادلات الخطية العشوائية
• 5. وجهة نظر جبرية 2: التحديث العشوائي
• 6. وجهة نظر تحليلية: نقطة ثابتة عشوائية

سنشرح الآن بعض هذه الآراء. تعتمد هذه الطريقة على معيارين:

• مصفوفة موجبة محددة${\displaystyle B}$مما يؤدي إلى ناتج ضرب داخلي إقليدي مرجح${\displaystyle \langle x,y\rangle _{B}:=x^{T}By}$والمعيار المستحث

${\displaystyle \|x\|_{B}=\left(\langle x,x\rangle _{B}\right)^{\frac {1}{2}},}$

• ومصفوفة عشوائية${\displaystyle S}$بعدد من الصفوف يساوي${\displaystyle A}$(وربما عدد عشوائي من الأعمدة).

بالنظر إلى التكرار السابق${\displaystyle x^{k},}$النقطة الجديدة${\displaystyle x^{k+1}}$يتم حسابها عن طريق رسم مصفوفة عشوائية${\displaystyle S}$(بطريقة مستقلة ومتطابقة التوزيع من توزيع ثابت معين)، وتحديد

${\displaystyle x^{k+1}={\underset {x}{\operatorname {arg\ min} }}\|x-x^{k}\|_{B}{\text{ subject to }}S^{T}Ax=S^{T}b.}$

إنه،${\displaystyle x^{k+1}}$يتم الحصول عليها كإسقاط لـ${\displaystyle x^{k}}$على النظام المرسوم عشوائياً${\displaystyle S^{T}Ax=S^{T}b}$الفكرة وراء هذه الطريقة هي اختيار${\displaystyle S}$بحيث يكون الإسقاط على النظام المرسوم أبسط بكثير من حل النظام الأصلي${\displaystyle Ax=b}$يتم الحصول على طريقة كازمارز العشوائية عن طريق الاختيار${\displaystyle B}$أن تكون مصفوفة الوحدة ، و${\displaystyle S}$أن يكون${\displaystyle i^{th}}$متجه إحداثيات الوحدة باحتمالية${\displaystyle p_{i}=\|a_{i}\|_{2}^{2}/\|A\|_{F}^{2}.}$خيارات مختلفة من${\displaystyle B}$و${\displaystyle S}$يؤدي ذلك إلى ظهور أشكال مختلفة من هذه الطريقة.

هناك صياغة مختلفة ظاهريًا ولكنها مكافئة تمامًا للطريقة (تم الحصول عليها عبر ازدواجية لاغرانج) وهي

${\displaystyle x^{k+1}={\underset {x}{\operatorname {arg\ min} }}\left\|x-x^{*}\right\|_{B}{\text{ subject to }}x=x^{k}+B^{-1}A^{T}Sy,}$

أين${\displaystyle y}$يُسمح أيضًا بالتغيير، وحيث${\displaystyle x^{*}}$أي حل للنظام${\displaystyle Ax=b.}$لذلك،${\displaystyle x^{k+1}}$يتم الحصول على ذلك عن طريق تقييد التحديث أولاً بالفضاء الخطي الفرعي الممتد بواسطة أعمدة المصفوفة العشوائية${\displaystyle B^{-1}A^{T}S}$أي، إلى

${\displaystyle \left\{h:h=B^{-1}A^{T}Sy,\quad y{\text{ can vary }}\right\},}$

ثم اختيار النقطة${\displaystyle x}$من هذا الفضاء الفرعي الذي يقارب بشكل أفضل${\displaystyle x^{*}}$قد تبدو هذه الصيغة مفاجئة، إذ يبدو من المستحيل تنفيذ خطوة التقريب نظرًا لحقيقة أن${\displaystyle x^{*}}$غير معروف (فهذا ما نحاول حسابه!). ومع ذلك، لا يزال من الممكن القيام بذلك، ببساطة لأن${\displaystyle x^{k+1}}$الحساب بهذه الطريقة هو نفسه${\displaystyle x^{k+1}}$تم حسابها من خلال الرسم التخطيطي وصياغة المشروع، ومنذ ذلك الحين${\displaystyle x^{*}}$لا يظهر هناك.

يمكن أيضًا كتابة التحديث بشكل صريح على النحو التالي

${\displaystyle x^{k+1}=x^{k}-B^{-1}A^{T}S\left(S^{T}AB^{-1}A^{T}S\right)^{\dagger }S^{T}\left(Ax^{k}-b\right),}$

حيث${\displaystyle M^{\dagger }}$نرمز إلى المعكوس الزائف لمور-بنروز للمصفوفة${\displaystyle M}$وبالتالي، يمكن كتابة الطريقة بالشكل التالي${\displaystyle x^{k+1}=x^{k}+h^{k}}$، أين${\displaystyle h^{k}}$هو متجه تحديث عشوائي .

تأجير${\displaystyle M=S^{T}AB^{-1}A^{T}S,}$يمكن إثبات أن النظام${\displaystyle My=S^{T}(Ax^{k}-b)}$دائماً ما يكون لديه حل${\displaystyle y^{k}}$وأن المتجه هو لكل هذه الحلول${\displaystyle x^{k+1}-B^{-1}A^{T}Sy^{k}}$هو نفسه. لذا، لا يهم أي من هذه الحلول يتم اختياره، ويمكن كتابة الطريقة أيضًا على النحو التالي${\displaystyle x^{k+1}=x^{k}-B^{-1}A^{T}Sy^{k}}$يؤدي المعكوس الزائف إلى حل واحد محدد فقط. ويتمثل دور المعكوس الزائف في جانبين:

• يسمح ذلك بكتابة الطريقة بصيغة "التحديث العشوائي" الصريحة كما هو موضح أعلاه،
• يجعل ذلك التحليل بسيطاً من خلال الصيغة النهائية، السادسة.

إذا طرحنا${\displaystyle x^{*}}$من كلا جانبي صيغة التحديث العشوائي، نرمز

${\displaystyle Z:=A^{T}S\left(S^{T}AB^{-1}A^{T}S\right)^{\dagger }S^{T}A,}$

واستغل حقيقة أن${\displaystyle Ax^{*}=b,}$نصل إلى الصيغة الأخيرة:

${\displaystyle x^{k+1}-x^{*}=\left(I-B^{-1}Z\right)\left(x^{k}-x^{*}\right),}$

أين${\displaystyle I}$هي مصفوفة الوحدة. مصفوفة التكرار،${\displaystyle I-B^{-1}Z,}$عشوائي، ومن هنا جاء اسم هذه الصيغة.

بأخذ التوقعات المشروطة في الصيغة السادسة (المشروطة بـ${\displaystyle x^{k}}$)، نحصل على

${\displaystyle \mathbb {E} \left.\left[x^{k+1}-x^{*}\right|x^{k}\right]=\left(I-B^{-1}\mathbb {E} [Z]\right)\left[x^{k}-x^{*}\right].}$

بأخذ التوقع مرة أخرى، وباستخدام خاصية البرج للتوقعات، نحصل على

${\displaystyle \mathbb {E} \left[x^{k+1}-x^{*}\right]=(I-B^{-1}\mathbb {E} [Z])\mathbb {E} \left[x^{k}-x^{*}\right].}$

يُظهر غاور وريشتاريك ^{[ 14 ] أن}

${\displaystyle \rho$ :=\left\|IB^{-{\frac {1}{2}}}\mathbb {E} [Z]B^{-{\frac {1}{2}}}\right\|_{B}=\lambda _{\max }\left(IB^{-1}\mathbb {E} [Z]\right),}

حيث يتم تعريف معيار المصفوفة بواسطة

${\displaystyle \|M\|_{B}:=\max _{x\neq 0}{\frac {\|Mx\|_{B}}{\|x\|_{B}}}.}$

علاوة على ذلك، ودون أي افتراضات بشأن${\displaystyle S}$يمتلك المرء${\displaystyle 0\leq \rho \leq 1.}$من خلال أخذ المعايير وفكّ التكرار، نحصل على

${\displaystyle \left\|\mathbb {E} \left[x^{k}-x^{*}\right]\right\|_{B}\leq \rho ^{k}\|x^{0}-x^{*}\|_{B}.}$

ملاحظة : الشرط الكافي لتقارب البواقي المتوقعة إلى الصفر هو${\displaystyle \rho <1.}$يمكن تحقيق ذلك إذا${\displaystyle A}$يتمتع برتبة عمود كاملة وفي ظل ظروف معتدلة للغاية${\displaystyle S.}$يمكن إثبات تقارب الطريقة أيضاً دون افتراض رتبة العمود الكاملة بطريقة مختلفة. ^{[ 15 ]}

من الممكن أيضاً إظهار نتيجة أقوى:

تتقارب المعايير التربيعية المتوقعة (بدلاً من معايير التوقعات) بنفس المعدل:

${\displaystyle \mathbb {E} \left\|\left[x^{k}-x^{*}\right]\right\|_{B}^{2}\leq \rho ^{k}\left\|x^{0}-x^{*}\right\|_{B}^{2}.}$

ملاحظة : هذا النوع الثاني من التقارب أقوى بسبب المتطابقة التالية ^{[ 14 ]} التي تنطبق على أي متجه عشوائي${\displaystyle x}$وأي متجه ثابت${\displaystyle x^{*}}$:

${\displaystyle \left\|\mathbb {E} \left[x-x^{*}\right]\right\|^{2}=\mathbb {E} \left[\left\|x-x^{*}\right\|^{2}\right]-\mathbb {E} \left[\|x-\mathbb {E} [x]\|^{2}\right].}$

لقد رأينا أن طريقة كازمارز العشوائية تظهر كحالة خاصة من طريقة جوور-ريشتاريك لـ${\displaystyle B=I}$و${\displaystyle S}$كونه${\displaystyle i^{th}}$متجه إحداثيات الوحدة باحتمالية${\displaystyle p_{i}=\|a_{i}\|_{2}^{2}/\|A\|_{F}^{2},}$أين${\displaystyle a_{i}}$هو${\displaystyle i^{th}}$صف من${\displaystyle A.}$يمكن التحقق من ذلك عن طريق الحساب المباشر.

${\displaystyle \rho =\|I-B^{-1}\mathbb {E} [Z]\|_{B}=1-{\frac {\lambda _{\min }(A^{T}A)}{\|A\|_{F}^{2}}}.}$