إكمال المصفوفة

الموسوعة الحرة
إكمال مصفوفة 5×5 مكشوفة جزئيًا برتبة 1. اليسار: المصفوفة غير المكتملة الملاحظة؛ اليمين: نتيجة إكمال المصفوفة.

إكمال المصفوفة هو مهمة ملء القيم المفقودة في مصفوفة مُرصَدة جزئيًا، وهو ما يُعادل إجراء عملية إسناد البيانات في الإحصاء. تُنظَّم مجموعة واسعة من مجموعات البيانات بشكل طبيعي في شكل مصفوفة. أحد الأمثلة على ذلك مصفوفة تقييمات الأفلام، كما هو الحال في مسألة نتفليكس : بفرض وجود مصفوفة تقييمات تحتوي على كل قيمة مفقودة.(أنا،ج){\displaystyle (i,j)}يمثل تصنيف الفيلمج{\displaystyle j}بواسطة العميلأنا{\displaystyle i}، إذا كان العميلأنا{\displaystyle i}شاهد الفيلمج{\displaystyle j}وإذا كانت البيانات الأخرى مفقودة، نرغب في التنبؤ بالبيانات المتبقية لتقديم توصيات جيدة للعملاء بشأن ما يشاهدونه لاحقًا. مثال آخر هو مصفوفة المصطلحات في المستندات : يمكن تمثيل ترددات الكلمات المستخدمة في مجموعة من المستندات كمصفوفة، حيث يتوافق كل عنصر مع عدد مرات ظهور المصطلح المرتبط به في المستند المحدد.

بدون أي قيود على عدد درجات الحرية في المصفوفة المكتملة، تُعتبر هذه المسألة غير محددة بشكل كامل، إذ يمكن إسناد قيم عشوائية إلى العناصر المخفية. لذا، نحتاج إلى بعض الافتراضات حول المصفوفة لإنشاء مسألة محددة جيدًا ، مثل افتراض أن لها محددًا أقصى، أو أنها موجبة التحديد، أو أنها منخفضة الرتبة. [ 1 ] [ 2 ]

على سبيل المثال، يمكن افتراض أن المصفوفة ذات بنية منخفضة الرتبة، ثم البحث عن مصفوفة ذات أدنى رتبة ، أو إذا كانت رتبة المصفوفة المكتملة معروفة، مصفوفة ذات رتبةر{\displaystyle r}يتطابق ذلك مع المدخلات المعروفة. يوضح الرسم التوضيحي أنه يمكن إكمال مصفوفة من الرتبة 1 مكشوفة جزئيًا (على اليسار) بدون أي خطأ (على اليمين)، حيث يجب أن تكون جميع الصفوف التي تحتوي على مدخلات مفقودة مماثلة للصف الثالث. في حالة مشكلة Netflix، من المتوقع أن تكون مصفوفة التقييمات منخفضة الرتبة، نظرًا لأن تفضيلات المستخدمين غالبًا ما يمكن وصفها ببضعة عوامل، مثل نوع الفيلم ووقت إصداره. تشمل التطبيقات الأخرى رؤية الحاسوب ، حيث يلزم إعادة بناء وحدات البكسل المفقودة في الصور، والكشف عن الموقع العالمي لأجهزة الاستشعار في الشبكة من معلومات المسافة الجزئية، والتعلم متعدد الفئات . تُعد مشكلة إكمال المصفوفة بشكل عام من المسائل الصعبة حسابيًا (NP-hard )، ولكن في ظل افتراضات إضافية، توجد خوارزميات فعالة تحقق إعادة بناء دقيقة باحتمالية عالية .

من منظور التعلم الإحصائي، تُعدّ مسألة إكمال المصفوفة تطبيقًا لتنظيم المصفوفة ، وهو تعميم لتنظيم المتجهات . على سبيل المثال، في مسألة إكمال المصفوفة منخفضة الرتبة، يمكن تطبيق عقوبة التنظيم التي تأخذ شكل معيار نووي.R(X)=λ‖X‖*{\displaystyle R(X)=\lambda \|X\|_{*}}

إكمال المصفوفة منخفضة الرتبة

أحد أشكال مسألة إكمال المصفوفة هو إيجاد المصفوفة ذات الرتبة الأدنىX{\displaystyle X}والتي تتطابق مع المصفوفةم{\displaystyle M}والتي نرغب في استعادتها، لجميع المدخلات في المجموعةهـ{\displaystyle E}من المدخلات المرصودة. الصياغة الرياضية لهذه المسألة هي كما يلي:

مينXرتبة(X)رهناً بـXأناج=مأناج∀أنا،ج∈هـ{\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&{\text{rank}}(X)\\&{\text{subject to}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}}

أثبت كانديس وريخت [ 3 ] أنه مع افتراضات حول أخذ عينات من المدخلات المرصودة وعدد كافٍ من المدخلات التي تم أخذ عينات منها، فإن هذه المشكلة لها حل فريد باحتمالية عالية.

صيغة مكافئة، بالنظر إلى المصفوفةم{\displaystyle M}من المعروف أن المبلغ المراد استرداده ذو رتبةر{\displaystyle r}، هو حل لـX{\displaystyle X}أينXأناج=مأناج∀أنا،ج∈هـ{\displaystyle X_{ij}=M_{ij}\;\;\forall i,j\in E}

الافتراضات

يتم وضع عدد من الافتراضات حول أخذ عينات من المدخلات المرصودة وعدد المدخلات التي تم أخذ عينات منها بشكل متكرر لتبسيط التحليل ولضمان عدم عدم تحديد المشكلة بشكل غير كافٍ .

أخذ عينات منتظمة من المدخلات المرصودة

ولجعل التحليل قابلاً للتطبيق، يُفترض غالباً أن المجموعةهـ{\displaystyle E}يتم أخذ عينة عشوائية منتظمة من جميع المجموعات الفرعية من المدخلات ذات العدد الثابت من المدخلات المرصودة.|هـ|{\displaystyle |E|}ولتبسيط التحليل أكثر، يُفترض بدلاً من ذلك أنهـ{\displaystyle E}يتم إنشاؤها عن طريق أخذ عينات برنولي ، أي أن كل إدخال يتم ملاحظته باحتماليةص{\displaystyle p}. لوص{\displaystyle p}تم ضبطه علىشمالمن{\displaystyle {\frac {N}{mn}}}أينشمال{\displaystyle N}هي العدد المتوقع المرغوب فيه لـهـ{\displaystyle E}، وم،ن{\displaystyle m,\;n}أبعاد المصفوفة (لنفترضم<ن{\displaystyle m<n}(دون فقدان للعمومية )|هـ|{\displaystyle |E|}يقع ضمنيا(نسجل⁡ن){\displaystyle O(n\log n)}لشمال{\displaystyle N}باحتمالية عالية، لذا فإن أخذ عينات برنولي يُعد تقريبًا جيدًا لأخذ العينات المنتظمة. [ 3 ] ومن التبسيطات الأخرى افتراض أن المدخلات تُؤخذ عينات منها بشكل مستقل ومع الإحلال. [ 4 ]

الحد الأدنى لعدد الإدخالات المرصودة

لنفترض أنم{\displaystyle m}بواسطةن{\displaystyle n}مصفوفةم{\displaystyle M}(معم<ن{\displaystyle m<n}) نحاول استعادة رتبتهر{\displaystyle r}يوجد حد أدنى نظري للمعلومات لعدد المدخلات التي يجب ملاحظتها قبلم{\displaystyle M}يمكن إعادة بنائها بشكل فريد. مجموعة م{\displaystyle m}بواسطةن{\displaystyle n}المصفوفات ذات الرتبة الأقل من أو تساوي ر{\displaystyle r}هو نوع جبري فيجم×ن{\displaystyle {\mathbb {C} }^{m\times n}}بأبعاد (ن+م)ر-ر2{\displaystyle (n+m)r-r^{2}}باستخدام هذه النتيجة، يمكن للمرء أن يثبت أن على الأقل 4نر-4ر2{\displaystyle 4nr-4r^{2}} يجب مراعاة المدخلات لإكمال المصفوفة في جن×ن{\displaystyle {\mathbb {C} }^{n\times n}} أن يكون لديك حل فريد عندما ر≤ن/2{\displaystyle r\leq n/2} [ 5 ]​

ثانيًا، يجب أن يكون هناك إدخال واحد على الأقل مُلاحظ لكل صف وعمود منم{\displaystyle M}تحليل القيم المفردة لـم{\displaystyle M}يُعطى بواسطةيوΣV†{\displaystyle U\Sigma V^{\dagger }}إذا كان العمودأنا{\displaystyle i}إذا لم تتم ملاحظته، فمن السهل رؤيةأناذ{\displaystyle i^{\text{th}}}متجه مفرد أيمن لـم{\displaystyle M}،vأنا{\displaystyle v_{i}}يمكن تغييرها إلى قيمة عشوائية وستظل تُنتج مطابقة مصفوفةم{\displaystyle M}على مجموعة المدخلات المرصودة. وبالمثل، إذا كان الصفج{\displaystyle j}غير مرصود،جذ{\displaystyle j^{\text{th}}}متجه مفرد أيسر لـم{\displaystyle M}،uأنا{\displaystyle u_{i}}يمكن أن تكون عشوائية. إذا افترضنا أخذ عينات برنولي من مجموعة الإدخالات المرصودة، فإن تأثير جامع القسائم يعني أن الإدخالات من رتبةيا(نسجل⁡ن){\displaystyle O(n\log n)}يجب مراقبة كل صف وعمود لضمان وجود ملاحظة من كل صف وعمود باحتمالية عالية. [ 6 ]

بدمج الشروط اللازمة وبافتراض أنر≪م،ن{\displaystyle r\ll m,n}(وهو افتراض صحيح للعديد من التطبيقات العملية)، فإن الحد الأدنى لعدد المدخلات المرصودة المطلوبة لمنع مشكلة إكمال المصفوفة من أن تكون غير محددة هو من رتبةنرسجل⁡ن{\displaystyle nr\log n}.

عدم الترابط

ظهر مفهوم عدم التماسك في الاستشعار المضغوط . وقد تم تقديمه في سياق إكمال المصفوفة لضمان المتجهات المفردة لـم{\displaystyle M}ليست "متباعدة" للغاية بمعنى أن جميع إحداثيات كل متجه منفرد لها مقادير متقاربة بدلاً من أن تكون بعض الإحداثيات ذات مقادير أكبر بكثير. [ 7 ] [ 8 ] وبالتالي، فإن متجهات الأساس القياسية غير مرغوب فيها كمتجهات منفردة، والمتجه1ن[11⋮1]{\displaystyle {\frac {1}{\sqrt {n}}}{\begin{bmatrix}1\\1\\\vdots \\1\end{bmatrix}}}فيRن{\displaystyle \mathbb {R} ^{n}}يُعدّ ذلك مرغوبًا. كمثال على ما قد يحدث من أخطاء إذا كانت المتجهات المفردة "متباعدة" بشكل كافٍ، انظر إلىم{\displaystyle m}بواسطةن{\displaystyle n}مصفوفة[10⋯0⋮⋮0000]{\displaystyle {\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}}باستخدام تحليل القيم المفردةأنام[10⋯0⋮⋮0000]أنان{\displaystyle I_{m}{\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}I_{n}}جميع إدخالات تقريبًام{\displaystyle M}يجب أخذ عينة منها قبل إعادة بنائها.

يُعرّف كانديس وريخت [ 3 ] تماسك المصفوفةيو{\displaystyle U}مع مسافة العمودر-{\displaystyle r-}الفضاء الفرعي ذو الأبعادRن{\displaystyle \mathbb {R} ^{n}}مثلμ(يو)=نرالأعلىأنا<ن‖Pيوهـأنا‖2{\displaystyle \mu (U)={\frac {n}{r}}\max _{i<n}\|P_{U}e_{i}\|^{2}}، أينPيو{\displaystyle P_{U}}هو الإسقاط المتعامد علىيو{\displaystyle U}ثم يؤكد عدم التماسك أنه بالنظر إلى تحليل القيم المفردةيوΣV†{\displaystyle U\Sigma V^{\dagger }}التابعم{\displaystyle m}بواسطةن{\displaystyle n}مصفوفةم{\displaystyle M}،

  1. μ(يو)،μ(V)≤μ0{\displaystyle \mu (U),\;\mu (V)\leq \mu _{0}}
  2. مدخلات∑كuكvك†{\displaystyle \sum _{k}u_{k}v_{k}^{\dagger }}لها مقادير محدودة من الأعلى بـμ1رمن{\displaystyle \mu _{1}{\sqrt {\frac {r}{mn}}}}

بالنسبة للبعضμ0،μ1{\displaystyle \mu _{0},\;\mu _{1}}.

إكمال المصفوفة منخفضة الرتبة مع الضوضاء

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

Yأناج=مأناج+Zأناج،(أنا،ج)∈Ω،{\displaystyle Y_{ij}=M_{ij}+Z_{ij},(i,j)\in \Omega ,}

أينZأناج:(أنا،ج)∈Ω{\displaystyle {Z_{ij}:(i,j)\in \Omega }}يمثل هذا الحدّ حدّاً للضوضاء. لاحظ أن الضوضاء قد تكون عشوائية أو حتمية. بدلاً من ذلك، يمكن التعبير عن النموذج على النحو التالي:

PΩ(Y)=PΩ(م)+PΩ(Z)،{\displaystyle P_{\Omega }(Y)=P_{\Omega }(M)+P_{\Omega }(Z),}

أينZ{\displaystyle Z}هون×ن{\displaystyle n\times n}مصفوفة ذات مدخلاتZأناج{\displaystyle Z_{ij}}ل(أنا،ج)∈Ω{\displaystyle (i,j)\in \Omega }بافتراض أن‖PΩ(Z)‖F≤دلتا{\displaystyle \|P_{\Omega }(Z)\|_{F}\leq \delta }بالنسبة للبعضدلتا>0{\displaystyle \delta >0}لاستعادة المصفوفة غير المكتملة، نحاول حل مسألة التحسين التالية :

مينX‖X‖*رهناً بـ‖PΩ(X-Y)‖F≤دلتا{\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&\|X\|_{*}\\&{\text{subject to}}&\|P_{\Omega }(X-Y)\|_{F}\leq \delta \\\end{aligned}}}

من بين جميع المصفوفات المتوافقة مع البيانات، ابحث عن المصفوفة ذات المعيار النووي الأدنى. وقد أثبت كانديس وبلان [ 9 ] دقة هذه العملية. كما أثبتا أنه عند حدوث استعادة مثالية خالية من الضوضاء، يكون إكمال المصفوفة مستقرًا في مواجهة الاضطرابات. ويتناسب الخطأ طرديًا مع مستوى الضوضاء.دلتا{\displaystyle \delta }لذلك، عندما يكون مستوى الضوضاء منخفضًا، يكون الخطأ منخفضًا أيضًا. هنا، لا تخضع مسألة إكمال المصفوفة لخاصية التساوي المقيد (RIP). بالنسبة للمصفوفات، تفترض خاصية التساوي المقيد أن عامل أخذ العينات يخضع لـ

(1-دلتا)‖X‖F2≤1ص‖PΩ(X)‖F2≤(1+دلتا)‖X‖F2{\displaystyle (1-\delta )\|X\|_{F}^{2}\leq {\frac {1}{p}}\|P_{\Omega }(X)\|_{F}^{2}\leq (1+\delta )\|X\|_{F}^{2}}

لجميع المصفوفاتX{\displaystyle X}برتبة صغيرة بما فيه الكفاية ودلتا<1{\displaystyle \delta <1}صغيرة بما يكفي. كما أن هذه الطرق قابلة للتطبيق على مشاكل استعادة الإشارة المتفرقة التي لا ينطبق عليها مبدأ RIP.

إكمال المصفوفة عالية الرتبة

تُعتبر مسألة إكمال المصفوفات عالية الرتبة عموماً مسألة صعبة من نوع NP . ومع ذلك، في ظل افتراضات معينة، يمكن إكمال بعض المصفوفات عالية الرتبة غير المكتملة أو حتى المصفوفات كاملة الرتبة.

درس إريكسون وبالزانو ونواك [ 10 ] مشكلة إكمال مصفوفة بافتراض أن أعمدة المصفوفة تنتمي إلى اتحاد فضاءات فرعية متعددة منخفضة الرتبة. وبما أن الأعمدة تنتمي إلى اتحاد فضاءات فرعية، يمكن اعتبار المشكلة نسخةً من مشكلة تجميع الفضاءات الفرعية مع وجود بيانات مفقودة.X{\displaystyle X}كنن×شمال{\displaystyle n\times N}مصفوفة تقع أعمدتها (الكاملة) في اتحاد لا يزيد عنك{\displaystyle k}الفضاءات الفرعية، كل منهارتبة≤ر<ن{\displaystyle \operatorname {rank} \leq r<n}وافترضشمال≫كن{\displaystyle N\gg kn}أظهر إريكسون وبالزانو ونواك [ 10 ] أنه في ظل افتراضات معتدلة، فإن كل عمود منX{\displaystyle X}يمكن استعادتها بشكل كامل باحتمالية عالية من نسخة غير مكتملة طالما أن على الأقلجرشمالسجل2⁡(ن){\displaystyle CrN\log ^{2}(n)}مدخلات منX{\displaystyle X}تُلاحظ بشكل عشوائي منتظم، معج>1{\displaystyle C>1}ثابت يعتمد على شروط عدم التماسك المعتادة، والترتيب الهندسي للفضاءات الفرعية، وتوزيع الأعمدة على الفضاءات الفرعية.

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

خوارزميات لإكمال المصفوفات منخفضة الرتبة

تم اقتراح العديد من خوارزميات إكمال المصفوفات. [ 8 ] وتشمل هذه الخوارزمية القائمة على الاسترخاء المحدب، [ 3 ] والخوارزمية القائمة على التدرج، [ 11 ] والخوارزمية القائمة على التصغير المتناوب، [ 12 ] وخوارزمية جاوس-نيوتن، [ 13 ] والخوارزمية القائمة على مراعاة التقطيع. [ 14 ]

استرخاء محدب

تُعدّ مسألة تقليل الرتبة مسألة صعبة من نوع NP . يتمثل أحد الأساليب المقترحة من قبل كانديس وريخت في صياغة استرخاء محدب للمسألة وتقليل المعيار النووي.‖م‖*{\displaystyle \|M\|_{*}}(مما يعطي مجموع القيم المفردة لـم{\displaystyle M}) بدلاً منرتبة(م){\displaystyle {\text{rank}}(M)}(الذي يحسب عدد القيم المفردة غير الصفرية لـم{\displaystyle M}[ 3 ] هذا يُشابه تقليل معيار L1 بدلاً من معيار L0 للمتجهات. يمكن حل الاسترخاء المحدب باستخدام البرمجة شبه المحددة (SDP) بملاحظة أن مسألة التحسين تُكافئ ما يلي :

ميندبليو1،دبليو2يتعقب⁡(دبليو1)+يتعقب⁡(دبليو2)رهناً بـXأناج=مأناج∀أنا،ج∈هـ[دبليو1XXتيدبليو2]⪰0{\displaystyle {\begin{aligned}&\min \limits _{W_{1},W_{2}}&&\operatorname {trace} (W_{1})+\operatorname {trace} (W_{2})\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\begin{bmatrix}W_{1}&X\\X^{T}&W_{2}\end{bmatrix}}\succeq 0\end{aligned}}}

تكمن صعوبة استخدام البرمجة شبه المحددة لحل الاسترخاء المحدب فييا(الأعلى(م،ن)4){\displaystyle O({\text{max}}(m,n)^{4})}لا تستطيع أحدث برامج الحل، مثل SDPT3، التعامل إلا مع المصفوفات التي يصل حجمها إلى 100 × 100. [ 15 ] وهناك طريقة بديلة من الدرجة الأولى لحل الاسترخاء المحدب تقريبًا، وهي خوارزمية عتبة القيمة المفردة التي قدمها كل من كاي وكانديس وشين. [ 15 ]

يُبين كانديس وريخت، باستخدام دراسة المتغيرات العشوائية على فضاءات باناخ ، أنه إذا كان عدد المدخلات المرصودة من رتبةالأعلى{μ12،μ0μ1،μ0ن0.25}نرسجل⁡ن{\displaystyle \max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\log n}(بافتراض عدم فقدان العمومية)م<ن{\displaystyle m<n})، تمتلك مسألة تقليل الرتبة حلاً وحيداً، وهو أيضاً حل لتقريبها المحدب باحتمالية1-جن3{\displaystyle 1-{\frac {c}{n^{3}}}}لبعض الثوابتج{\displaystyle c}إذا كانت رتبةم{\displaystyle M}صغير (ر≤ن0.2μ0{\displaystyle r\leq {\frac {n^{0.2}}{\mu _{0}}}})، يتقلص حجم مجموعة الملاحظات إلى رتبةμ0ن1.2رسجل⁡ن{\displaystyle \mu _{0}n^{1.2}r\log n}تُعد هذه النتائج قريبة من الأمثل، حيث أن الحد الأدنى لعدد المدخلات التي يجب ملاحظتها حتى لا تكون مسألة إكمال المصفوفة غير محددة بشكل كافٍ هو من رتبةنرسجل⁡ن{\displaystyle nr\log n}.

وقد حسّن كانديس وتاو هذه النتيجة. [ 6 ] إذ توصلا إلى حدود لا تختلف عن الحدود المثلى إلا بعوامل لوغاريتمية متعددة، وذلك بتعزيز الافتراضات. فبدلاً من خاصية عدم التماسك، افترضا خاصية عدم التماسك القوي بمعاملμ3{\displaystyle \mu _{3}}تنص هذه الخاصية على ما يلي:

  1. |⟨هـأ،Pيوهـأ′⟩-رم1أ=أ′|≤μ3رم{\displaystyle |\langle e_{a},P_{U}e_{a'}\rangle -{\frac {r}{m}}1_{a=a'}|\leq \mu _{3}{\frac {\sqrt {r}}{m}}}لأ،أ′≤م{\displaystyle a,a'\leq m}و|⟨هـب،Pيوهـب′⟩-رن1ب=ب′|≤μ3رن{\displaystyle |\langle e_{b},P_{U}e_{b'}\rangle -{\frac {r}{n}}1_{b=b'}|\leq \mu _{3}{\frac {\sqrt {r}}{n}}}لب،ب′≤ن{\displaystyle b,b'\leq n}
  2. مدخلات∑أناuأناvأنا†{\displaystyle \sum _{i}u_{i}v_{i}^{\dagger }}تكون محدودة في مقدارها بـμ3رمن{\displaystyle \mu _{3}{\sqrt {\frac {r}{mn}}}}

بشكل بديهي، عدم تماسك قوي للمصفوفةيو{\displaystyle U}يؤكد أن الإسقاطات المتعامدة لمتجهات الأساس القياسية إلىيو{\displaystyle U}لها مقادير ذات احتمالية عالية إذا تم توزيع المتجهات المفردة عشوائياً. [ 7 ]

يجد كانديس وتاو أنه عندمار{\displaystyle r}يكونيا(1){\displaystyle O(1)}ويبلغ عدد الإدخالات المرصودة حواليμ34ن(سجل⁡ن)2{\displaystyle \mu _{3}^{4}n(\log n)^{2}}، تمتلك مسألة تقليل الرتبة حلاً وحيداً، وهو أيضاً حل لتقريبها المحدب باحتمالية1-جن3{\displaystyle 1-{\frac {c}{n^{3}}}}لبعض الثوابتج{\displaystyle c}. لأير{\displaystyle r}عدد الإدخالات المرصودة الكافية لتأكيد هذا الادعاء هو من رتبةμ32نر(سجل⁡ن)6{\displaystyle \mu _{3}^{2}nr(\log n)^{6}}

يتمثل أحد أساليب الاسترخاء المحدب الأخرى [ 16 ] في تقليل معيار فروبينيوس التربيعي في ظل قيد الرتبة. وهذا يعادل حل

مينX‖X‖F2رهناً بـXأناج=مأناج∀أنا،ج∈هـرتبة⁡(X)≤ك.{\displaystyle {\begin{aligned}&\min \limits _{X}&&\Vert X\Vert _{F}^{2}\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&\operatorname {Rank} (X)\leq k.\end{aligned}}}

من خلال إدخال مصفوفة إسقاط متعامدةY{\displaystyle Y}(معنىY2=Y،Y=Y′{\displaystyle Y^{2}=Y,Y=Y'}) لنمذجة رتبةX{\displaystyle X}عبرX=YX،يتعقب(Y)≤ك{\displaystyle X=YX,{\text{trace}}(Y)\leq k}وبأخذ الاسترخاء المحدب لهذه المسألة، نحصل على البرنامج شبه المحدد التالي

مينX،Y،θيتعقب(θ)رهناً بـXأناج=مأناج∀أنا،ج∈هـيتعقب⁡(Y)≤ك،0⪯Y⪯أنا(YXX⊤θ)⪰0.{\displaystyle {\begin{aligned}&\min \limits _{X,Y,\theta }&&{\text{trace}}(\theta )\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&\operatorname {trace} (Y)\leq k,0\preceq Y\preceq I\\&&&{\begin{pmatrix}Y&X\\X^{\top }&\theta \end{pmatrix}}\succeq 0.\end{aligned}}}

إذا كانت Y مصفوفة إسقاط (أي ذات قيم ذاتية ثنائية) في هذا التقريب، فإن التقريب يكون دقيقًا. وإلا، فإنه يُعطي حدًا أدنى صالحًا للدالة الهدفية الكلية. علاوة على ذلك، يمكن تحويله إلى حل ممكن بدالة هدفية أكبر (قليلاً) عن طريق تقريب القيم الذاتية لـ Y بطريقة جشعة. [ 16 ] والجدير بالذكر أن هذا التقريب المحدب يمكن حله عن طريق التناوب بين تقليل قيم X و Y دون حل أي مسائل برمجة شبه محددة، وبالتالي يتجاوز الحدود العددية النموذجية لحلول البرمجة شبه المحددة الحديثة مثل SDPT3 أو Mosek.

يُعد هذا النهج حالة خاصة من تقنية إعادة صياغة أكثر عمومية، والتي يمكن تطبيقها للحصول على حد أدنى صالح لأي مسألة منخفضة الرتبة ذات هدف محدب لمصفوفة الأثر. [ 17 ]

الانحدار التدريجي

قام كل من كيشافان ومونتاناري وأوه [ 11 ] بدراسة نوع مختلف من إكمال المصفوفة حيث يتم تحديد رتبةم{\displaystyle m}بواسطةن{\displaystyle n}مصفوفةم{\displaystyle M}من المعروف أن المادة التي سيتم استعادتها هير{\displaystyle r}يفترضون أخذ عينات برنولي من المدخلات، ونسبة عرض إلى ارتفاع ثابتةمن{\displaystyle {\frac {m}{n}}}، حجم محدود لعناصرم{\displaystyle M}(ليكن الحد الأعلى هومالأعلى{\displaystyle M_{\text{max}}})، ورقم الحالة الثابتσ1σر{\displaystyle {\frac {\sigma _{1}}{\sigma _{r}}}}(أينσ1{\displaystyle \sigma _{1}}وσر{\displaystyle \sigma _{r}}أكبر وأصغر القيم المفردة لـم{\displaystyle M}على التوالي). علاوة على ذلك، يفترضون أن شرطي عدم الاتساق مُحققان معμ0{\displaystyle \mu _{0}}وμ1σ1σر{\displaystyle \mu _{1}{\frac {\sigma _{1}}{\sigma _{r}}}}أينμ0{\displaystyle \mu _{0}}وμ1{\displaystyle \mu _{1}}هي ثوابت. ليكنمهـ{\displaystyle M^{E}}أن تكون مصفوفة مطابقةم{\displaystyle M}في موقع التصويرهـ{\displaystyle E}من المدخلات المرصودة، وتكون قيمتها صفرًا في غير ذلك. ثم يقترحون الخوارزمية التالية:

  1. تقليممهـ{\displaystyle M^{E}}عن طريق إزالة جميع المشاهدات من الأعمدة ذات الدرجة الأكبر من2|هـ|ن{\displaystyle {\frac {2|E|}{n}}}عن طريق ضبط القيم في الأعمدة على 0. وبالمثل، قم بإزالة جميع الملاحظات من الصفوف التي تكون درجتها أكبر من2|هـ|ن{\displaystyle {\frac {2|E|}{n}}}.
  2. مشروعمهـ{\displaystyle M^{E}}إلى أولر{\displaystyle r}المكونات الرئيسية . سمِّ المصفوفة الناتجةTr(مهـ){\displaystyle {\text{Tr}}(M^{E})}.
  3. يحلمينX،YمينS∈Rر×ر12∑أنا،ج∈هـ(مأناج-(XSY†)أناج)2+ρجي(X،Y){\displaystyle \min _{X,Y}\min _{S\in \mathbb {R} ^{r\times r}}{\frac {1}{2}}\sum _{i,j\in E}(M_{ij}-(XSY^{\dagger })_{ij})^{2}+\rho G(X,Y)}أينجي(X،Y){\displaystyle G(X,Y)}هي دالة تنظيمية ما باستخدام خوارزمية التدرج الهبوطي مع البحث الخطي . قم بتهيئةX،Y{\displaystyle X,\;Y}فيX0،Y0{\displaystyle X_{0},\;Y_{0}}أينTr(مهـ)=X0S0Y0†{\displaystyle {\text{Tr}}(M_{E})=X_{0}S_{0}Y_{0}^{\dagger }}. تعيينجي(X،Y){\displaystyle G(X,Y)}كوظيفة ما تفرضX،Y{\displaystyle X,\;Y}أن يظل غير متماسك طوال عملية الهبوط التدرجي إذاX0{\displaystyle X_{0}}وY0{\displaystyle Y_{0}}غير مترابطة.
  4. أعد المصفوفةXSY†{\displaystyle XSY^{\dagger }}.

تُنتج الخطوتان 1 و2 من الخوارزمية مصفوفةTr(مهـ){\displaystyle {\text{Tr}}(M^{E})}قريب جدًا من المصفوفة الحقيقيةم{\displaystyle M}(كما تم قياسه بواسطة جذر متوسط ​​مربع الخطأ (RMSE) ) باحتمالية عالية. على وجه الخصوص، باحتمالية1-1ن3{\displaystyle 1-{\frac {1}{n^{3}}}}،1منمالأعلى2‖م-Tr(مهـ)‖F2≤جرم|هـ|من{\displaystyle {\frac {1}{mnM_{\text{max}}^{2}}}\|M-{\text{Tr}}(M^{E})\|_{F}^{2}\leq C{\frac {r}{m|E|}}{\sqrt {\frac {m}{n}}}}لبعض الثوابتج{\displaystyle C}. ‖⋅‖F{\displaystyle \|\cdot \|_{F}}يرمز إلى معيار فروبينيوس . تجدر الإشارة إلى أن مجموعة الافتراضات الكاملة ليست ضرورية لصحة هذه النتيجة. فشرط عدم الاتساق، على سبيل المثال، لا يُفعّل إلا في إعادة البناء الدقيق. وأخيرًا، على الرغم من أن عملية التقليم قد تبدو غير بديهية لأنها تنطوي على حذف معلومات، إلا أنها تضمن الإسقاط.مهـ{\displaystyle M^{E}}إلى أولر{\displaystyle r}توفر المكونات الرئيسية مزيدًا من المعلومات حول المصفوفة الأساسيةم{\displaystyle M}أكثر من مجرد معلومات حول المدخلات المرصودة.

في الخطوة الثالثة، فضاء المصفوفات المرشحةX،Y{\displaystyle X,\;Y}يمكن تقليل ذلك من خلال ملاحظة أن مشكلة التصغير الداخلي لها نفس الحل لـ(X،Y){\displaystyle (X,Y)}أما بالنسبة لـ(Xسؤال،YR){\displaystyle (XQ,YR)}أينسؤال{\displaystyle Q}وR{\displaystyle R}متعامد​ر{\displaystyle r}بواسطةر{\displaystyle r}المصفوفات. ثم يمكن إجراء انحدار التدرج على الضرب الاتجاهي لمتشعبين من نوع غراسمان . إذار≪م،ن{\displaystyle r\ll m,\;n}وتكون مجموعة المدخلات المرصودة بالترتيب التالي:نرسجل⁡ن{\displaystyle nr\log n}، المصفوفة التي تم إرجاعها بواسطة الخطوة 3 هي بالضبطم{\displaystyle M}إذن، تكون الخوارزمية مثالية من حيث الترتيب، لأننا نعلم أنه لكي لا تكون مسألة إكمال المصفوفة غير محددة بشكل كافٍ ، يجب أن يكون عدد المدخلات من رتبةنرسجل⁡ن{\displaystyle nr\log n}.

تقليل المربعات الصغرى المتناوبة

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

X=يوVتي{\displaystyle X=UV^{T}}؛

ثم تتناوب الخوارزمية بين إيجاد الأفضليو{\displaystyle U}والأفضلV{\displaystyle V}على الرغم من أن المشكلة الكلية غير محدبة، إلا أن كل مشكلة فرعية منها عادةً ما تكون محدبة ويمكن حلها بكفاءة. وقد قدم جاين ونيتراپالي وسانغافي [ 12 ] أحد الضمانات الأولى لأداء التصغير المتناوب لكل من إكمال المصفوفة واستشعارها.

يمكن اعتبار خوارزمية التصغير المتناوب طريقة تقريبية لحل المشكلة غير المحدبة التالية:

مينيو،V∈Rن×ك‖PΩ(يوVتي)-PΩ(م)‖F2{\displaystyle {\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}

تم إدراج خوارزمية AltMinComplete المقترحة من قبل جاين، نيترابالي وسانغافي هنا: [ 12 ]

  1. المدخلات : مجموعة الملاحظاتΩ{\displaystyle \Omega }، قيمPΩ(م){\displaystyle P_{\Omega }(M)}
  2. تقسيمΩ{\displaystyle \Omega }داخل2تي+1{\displaystyle 2T+1}المجموعات الفرعيةΩ0،⋯،Ω2تي{\displaystyle \Omega _{0},\cdots ,\Omega _{2T}}مع كل عنصر من عناصرΩ{\displaystyle \Omega }ينتمي إلى أحدΩت{\displaystyle \Omega _{t}}باحتمالية متساوية (أخذ العينات مع الإحلال)
  3. يو^0=SVد(1صPΩ0(م)،ك){\displaystyle {\hat {U}}^{0}=SVD({\frac {1}{p}}P_{\Omega _{0}}(M),k)}أي، أعلى-ك{\displaystyle k}المتجهات المفردة اليسرى لـ1صPΩ0(م){\displaystyle {\frac {1}{p}}P_{\Omega _{0}}(M)}
  4. القص : اضبط جميع عناصريو^0{\displaystyle {\hat {U}}^{0}}التي لها مقدار أكبر من2μكن{\displaystyle {\frac {2\mu {\sqrt {k}}}{\sqrt {n}}}}لتصفير أعمدة وتطبيعهايو^0{\displaystyle {\hat {U}}^{0}}
  5. لت=0،⋯،تي-1{\displaystyle t=0,\cdots ,T-1}يفعل
  6. V^ت+1←أرجينينV∈Rن×ك‖PΩت+1(يو^Vتي-م)‖F2{\displaystyle \quad {\hat {V}}^{t+1}\leftarrow {\text{argmin}}_{V\in \mathbb {R} ^{n\times k}}\|P_{\Omega _{t+1}}({\hat {U}}V^{T}-M)\|_{F}^{2}}
  7. يو^ت+1←أرجينينيو∈Rم×ك‖PΩتي+ت+1(يو(V^ت+1)تي-م)‖F2{\displaystyle \quad {\hat {U}}^{t+1}\leftarrow {\text{argmin}}_{U\in \mathbb {R} ^{m\times k}}\|P_{\Omega _{T+t+1}}(U({\hat {V}}^{t+1})^{T}-M)\|_{F}^{2}}
  8. نهاية لـ
  9. يعودX=يو^تي(V^تي)تي{\displaystyle X={\hat {U}}^{T}({\hat {V}}^{T})^{T}}

لقد أظهروا ذلك من خلال الملاحظة|Ω|=يا((σ1*σك*)6ك7سجل⁡نسجل⁡(ك‖م‖F/ϵ)){\displaystyle |\Omega |=O(({\frac {\sigma _{1}^{*}}{\sigma _{k}^{*}}})^{6}k^{7}\log n\log(k\|M\|_{F}/\epsilon ))}عناصر عشوائية لمصفوفة غير متماسكةم{\displaystyle M}يمكن استرداد خوارزمية AltMinCompleteم{\displaystyle M}فييا(سجل⁡(1/ϵ)){\displaystyle O(\log(1/\epsilon ))}خطوات. من حيث تعقيد العينة (|Ω|{\displaystyle |\Omega |}نظريًا، قد يتطلب تقليل التناوب حجمًا أكبرΩ{\displaystyle \Omega }أكثر من الاسترخاء المحدب. ومع ذلك، يبدو من الناحية التجريبية أن هذا ليس هو الحال، مما يعني أنه يمكن تشديد حدود تعقيد العينة بشكل أكبر. من حيث التعقيد الزمني، أظهروا أن AltMinComplete يحتاج إلى وقت

يا(|Ω|ك2سجل⁡(1/ϵ)){\displaystyle O(|\Omega |k^{2}\log(1/\epsilon ))}.

تجدر الإشارة إلى أنه على الرغم من أن الطرق القائمة على الاسترخاء المحدب لها تحليل دقيق، إلا أن الخوارزميات القائمة على التقليل المتناوب أكثر نجاحًا في الممارسة العملية.

جاوس-نيوتن

يُعدّ استعادة مصفوفة جاوس-نيوتن (GNMR) إضافةً بسيطةً إلى الخوارزميات القائمة على التحليل. [ 13 ] على غرار التصغير المتناوب، تعالج GNMR هدف إكمال المصفوفة ذات الرتبة المنخفضة بعد تحليلها.

مينيو،V∈Rن×ك‖PΩ(يوVتي)-PΩ(م)‖F2{\displaystyle {\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}

استلهامًا من منهج جاوس-نيوتن الكلاسيكي ، يقوم GNMR بتخطيط دالة الهدف. وينتج عن ذلك المسألة الفرعية التالية للمربعات الصغرى الخطية :

مينΔيو،ΔV∈Rن×ك‖PΩ(يو0V0تي+يو0ΔVتي+ΔيوV0تي)-PΩ(م)‖F2{\displaystyle {\begin{aligned}&{\underset {\Delta U,\Delta V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(U_{0}V_{0}^{T}+U_{0}\Delta V^{T}+\Delta UV_{0}^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}

بدءاً من التهيئة(يو0،V0){\displaystyle (U_{0},V_{0})}تقوم خوارزمية GNMR بحل مشكلة المربعات الصغرى الخطية الفرعية بشكل تكراري وتحديثهايوت+1←يوت+Δيو،{\displaystyle U_{t+1}\leftarrow U_{t}+\Delta U,}Vت+1←Vت+ΔV{\displaystyle V_{t+1}\leftarrow V_{t}+\Delta V}حتى التقارب. ولأن المسألة الفرعية للمربعات الصغرى تعاني من نقص في الرتبة، فإن خوارزمية GNMR تختار الحل ذي المعيار الأدنى، وبالتالي تحافظ على التوازن بينيو{\displaystyle U}وV{\displaystyle V}دون استخدام تنظيم صريح. وقد ثبت أن هذه الخوارزمية تتمتع بضمانات نظرية قوية. بالإضافة إلى ذلك، وعلى الرغم من بساطتها، تشير النتائج التجريبية إلى أن خوارزمية GNMR تتفوق على العديد من الخوارزميات الشائعة، لا سيما عندما تكون الملاحظات متفرقة أو تكون المصفوفة سيئة التكييف.

إكمال المصفوفة مع مراعاة البيانات المنفصلة

في تطبيقات مثل أنظمة التوصية، حيث تكون عناصر المصفوفة منفصلة (مثل التقييمات الصحيحة من 1 إلى 5)، فإن دمج هذه الخاصية المنفصلة في مشكلة إكمال المصفوفة يمكن أن يحسن الأداء. تُدخل أساليب إكمال المصفوفة التي تراعي الخاصية المنفصلة مُنظِّمًا يُشجع عناصر المصفوفة المُكتملة على التوافق مع أبجدية منفصلة محدودة.

استخدمت إحدى الطرق المبكرة في هذا المجال...ℓ1{\displaystyle \ell _{1}}المعيار -norm كتقريب محدب لـℓ0{\displaystyle \ell _{0}}يُستخدم معيار -norm لفرض التقطيع، مما يُمكّن من التحسين الفعال باستخدام طرق التدرج التقريبي. وبناءً على ذلك، استبدل فورلينغ وآخرون (2023) [ 14 ]ℓ1{\displaystyle \ell _{1}}المعيار - مع تقريب مستمر وقابل للتفاضل لـℓ0{\displaystyle \ell _{0}}-norm، مما يجعل المشكلة أكثر قابلية للحل ويحسن الأداء.

يمكن صياغة مشكلة إكمال المصفوفة مع مراعاة العناصر المنفصلة على النحو التالي:

arg⁡مينX∈Rم×نو(X)+λز(X)+ζر(X|0)،{\displaystyle {\underset {{\boldsymbol {X}}\in \mathbb {R} ^{m\times n}}{\arg \min }}\,f({\boldsymbol {X}})+\lambda g({\boldsymbol {X}})+\zeta r({\boldsymbol {X}}\mid 0),}

أين:

  • (X)=12‖PΩ(X-يا)‖F2{\displaystyle ({\boldsymbol {X}})={\frac {1}{2}}\left\|P_{\Omega }({\boldsymbol {X}}-{\boldsymbol {O}})\right\|_{F}^{2}}يضمن ذلك دقة البيانات المُسجلة، معPΩ{\displaystyle P_{\Omega }}باعتبارها الإسقاط على المجموعة المرصودةΩ{\displaystyle \Omega }ويا{\displaystyle {\boldsymbol {O}}}باعتبارها المصفوفة المرصودة.
  • ز(X)=‖X‖*{\displaystyle g({\boldsymbol {X}})=\|{\boldsymbol {X}}\|_{*}}إن القاعدة النووية هي فرض بنية ذات رتبة منخفضة.
  • ر(X|0)=∑ك=1|أ|‖متجهΩ¯⁡(X)-أك1‖0{\displaystyle r({\boldsymbol {X}}\mid 0)=\sum _{k=1}^{|{\mathcal {A}}|}\left\|\operatorname {vec} _{\overline {\Omega }}({\boldsymbol {X}})-a_{k}\mathbf {1} \right\|_{0}}هو منظم الفضاء المنفصل، معأ{\displaystyle {\mathcal {A}}}كونها الأبجدية المنفصلة (على سبيل المثال، {1، 2، 3، 4، 5}) وΩ¯{\displaystyle {\overline {\Omega }}}مجموعة المدخلات غير المرصودة.

لحل هذه المشكلة غير المحدبة،ℓ0{\displaystyle \ell _{0}}يتم تقريب المعيار -norm بواسطة دالة متصلة . يتم تحويل هذا التقريب إلى دالة محدبة باستخدام البرمجة الكسرية ، مما يحول المسألة إلى سلسلة من المسائل الفرعية المحدبة.

تقوم الخوارزمية بتحديث تقدير المصفوفة بشكل متكرر من خلال تطبيق عمليات تقريبية على منظم الفضاء المنفصل وعتبة القيمة المفردة لفرض قيد الرتبة المنخفضة. تبدأ العملية بالحل منℓ1{\displaystyle \ell _{1}}يمكن للطريقة القائمة على معيار L1 تسريع التقارب. تُظهر نتائج المحاكاة، التي تم اختبارها على مجموعات بيانات مثل MovieLens-100k، أن هذه الطريقة تتفوق على كلتا الطريقتين الأخريين.ℓ1{\displaystyle \ell _{1}}[ 14 ]​

التطبيقات

يلخص كانديس وبلان [ 9 ] العديد من تطبيقات إكمال المصفوفة على النحو التالي:

الترشيح التعاوني

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

تحديد النظام

في حالة التحكم، يرغب المرء في ملاءمة نموذج فضاء الحالة الخطي المتقطع الزمني غير المتغير مع الزمن

x(ت+1)=أx(ت)+بu(ت)y(ت)=جx(ت)+دu(ت){\displaystyle {\begin{aligned}x(t+1)&=Ax(t)+Bu(t)\\y(t)&=Cx(t)+Du(t)\end{aligned}}}

إلى سلسلة من المدخلاتu(ت)∈Rم{\displaystyle u(t)\in \mathbb {R} ^{m}}والمخرجاتy(ت)∈Rص،ت=0،...،شمال{\displaystyle y(t)\in \mathbb {R} ^{p},t=0,\ldots ,N}المتجهx(ت)∈Rن{\displaystyle x(t)\in \mathbb {R} ^{n}}هي حالة النظام في وقتت{\displaystyle t}ون{\displaystyle n}يمثل هذا ترتيب نموذج النظام. ومن زوج المدخلات/المخرجات، يرغب المرء في استعادة المصفوفات.أ،ب،ج،د{\displaystyle A,B,C,D}والحالة الأوليةx(0){\displaystyle x(0)}يمكن أيضًا اعتبار هذه المشكلة مشكلة إكمال مصفوفة منخفضة الرتبة.

تحديد موقع إنترنت الأشياء (IoT)

تبرز مشكلة تحديد الموقع (أو تحديد الموقع العالمي) بشكل طبيعي في شبكات استشعار إنترنت الأشياء. وتتمثل هذه المشكلة في استعادة خريطة المستشعر في الفضاء الإقليدي من مجموعة محلية أو جزئية من المسافات الزوجية. وبالتالي، فهي مشكلة إكمال مصفوفة من الرتبة الثانية إذا كانت المستشعرات موجودة في مستوى ثنائي الأبعاد، ومن الرتبة الثالثة إذا كانت موجودة في فضاء ثلاثي الأبعاد. [ 18 ]

تعافي الشبكات الاجتماعية

تتميز معظم الشبكات الاجتماعية الواقعية بمصفوفات مسافة منخفضة الرتبة. عندما يتعذر علينا قياس الشبكة بالكامل، لأسباب مثل العقد الخاصة، أو محدودية موارد التخزين أو الحوسبة، لا نملك سوى جزء ضئيل من قيم المسافة المعروفة. تُعد الشبكات الإجرامية مثالًا جيدًا على هذه الشبكات. يمكن استخدام تقنية إكمال المصفوفة منخفضة الرتبة لاستعادة هذه المسافات غير المرصودة. [ 19 ]

انظر أيضاً

مراجع

  1. ↑ جونسون، تشارلز ر. (1990). "مسائل إكمال المصفوفات: دراسة استقصائية". نظرية المصفوفات وتطبيقاتها . وقائع ندوات في الرياضيات التطبيقية. المجلد 40. الصفحات 171-198 . doi : 10.1090/psapm/040/1059486 . ISBN   9780821801543.
  2. ↑ لوران، مونيك (2008). "مسائل إكمال المصفوفة". موسوعة التحسين . المجلد 3. الصفحات 221-229 . doi : 10.1007/978-0-387-74759-0_355 . ISBN   978-0-387-74758-3.
  3. 1 2 3 4 5 كانديس، إي جيه؛ ريخت، ب. (2009). "إكمال المصفوفة الدقيق عبر التحسين المحدب" . أسس الرياضيات الحسابية . 9 (6): 717-772 . arXiv : 0805.4471 . doi : 10.1007/s10208-009-9045-5 .
  4. ↑ ريخت، ب. (2009). "نهج أبسط لإكمال المصفوفات" (ملف PDF) . مجلة أبحاث تعلم الآلة . 12 : 3413-3430 . arXiv : 0910.0651 . Bibcode : 2009arXiv0910.0651R .
  5. ↑ شو، تشي تشيانغ (2018). "الحد الأدنى لعدد القياسات لاستعادة المصفوفات منخفضة الرتبة". التحليل التوافقي التطبيقي والحسابي . 44 (2): 497-508 . arXiv : 1505.07204 . doi : 10.1016/j.acha.2017.01.005 . S2CID 11990443 . 
  6. 1 2 كانديس، إي جيه؛ تاو، تي. (2010). "قوة الاسترخاء المحدب: إكمال المصفوفة شبه الأمثل". معاملات IEEE في نظرية المعلومات . 56 (5): 2053-2080 . arXiv : 0903.1476 . Bibcode : 2010ITIT...56.2053C . doi : 10.1109/TIT.2010.2044061 . S2CID 1255437 . 
  7. 1 2 تاو، ت. (10 مارس 2009). "قوة الاسترخاء المحدب: إكمال المصفوفة شبه الأمثل" . ما الجديد .
  8. 1 2 نغوين، إل تي؛ كيم، جيه؛ شيم، بي . (10 يوليو 2019). "إكمال المصفوفات منخفضة الرتبة: دراسة معاصرة" . IEEE Access . 7 (1): 94215–94237 . arXiv : 1907.11705 . Bibcode : 2019arXiv190711705N . doi : 10.1109/ACCESS.2019.2928130 . S2CID 198930899 . 
  9. 1 2 3 كانديس، إي جيه؛ بلان، واي. (2010). "إكمال المصفوفة مع الضوضاء". وقائع معهد مهندسي الكهرباء والإلكترونيات . 98 (6): 925-936 . arXiv : 0903.3131 . doi : 10.1109/JPROC.2009.2035722 . S2CID 109721 . 
  10. 1 2 إريكسون، ب.؛ بالزانو، ل.؛ نواك، ر. (2011). "إكمال المصفوفة عالية الرتبة وتجميع الفضاء الجزئي مع البيانات المفقودة". arXiv : 1112.5629 [ cs.IT ].
  11. 1 2 كيشافان، ر.هـ؛ مونتاناري، أ.؛ أوه، س. (2010). "إكمال المصفوفة من عدد قليل من المدخلات". معاملات IEEE في نظرية المعلومات . 56 (6): 2980-2998 . arXiv : 0901.3150 . Bibcode : 2010ITIT...56.2980K . doi : 10.1109/TIT.2010.2046205 . S2CID 53504 . 
  12. 1 2 3 جاين، ب.؛ نيترابالي، ب.؛ سانغافي، س. (2013). "إكمال المصفوفات منخفضة الرتبة باستخدام التصغير المتناوب". وقائع الندوة السنوية الخامسة والأربعين لجمعية ACM حول نظرية الحوسبة . ACM. ص 665-674 . arXiv : 1212.0467 . doi : 10.1145/2488608.2488693 . ISBN  978-1-4503-2029-0. S2CID 447011 . 
  13. زيلبر ، بيني ؛ نادلر، بواز (2022). "GNMR: خوارزمية قابلة للإثبات من سطر واحد لاستعادة المصفوفات منخفضة الرتبة" . مجلة SIAM لرياضيات علوم البيانات . 4 (2): 909-934 . doi : 10.1137/21M1433812 . PMC 11784930. PMID 39896132 .  
  14. 1 2 3 فورلينغ، نيكلاس؛ أندو، كينغو؛ أبريو، جوزيبي ثاديو فريتاس دي؛ غونزاليس جي، ديفيد؛ غونسا، أوزفالدو (2023). "إكمال المصفوفة المتقطعة الواعية عبر تقريب معيار ℓ₀ المحدب". معاملات IEEE في معالجة الإشارات . XX (X): XXX– XXX. doi : 10.1109/TSP.2023.XXXXXXX (غير نشط في 1 يوليو 2025).{{cite journal}}: صيانة CS1: رقم التعريف الرقمي غير نشط اعتبارًا من يوليو 2025 ( رابط )
  15. 1 2 كاي، جيه.-إف.؛ كانديس، إي. جيه.؛ شين، زد. (2010). "خوارزمية عتبة القيمة المفردة لإكمال المصفوفة". مجلة SIAM للتحسين . 20 (4): 1956-1982 . arXiv : 0810.3286 . doi : 10.1137/080738970 . S2CID 1254778 . 
  16. 1 2 بيرتسيماس، ديميتريس؛ كوري-رايت، رايان؛ بوفيليه، جان (2021). "تحسين المخروط المختلط الإسقاط: نموذج جديد لنمذجة قيود الرتبة". بحوث العمليات . 70 (6): 3321-3344 . arXiv : 2009.10395 . doi : 10.1287/opre.2021.2182 . S2CID 221836263 . 
  17. ↑ بيرتسيماس، ديميتريس؛ كوري-رايت، رايان؛ بوفيليه، جان (2023). "منظور جديد حول تحسين الرتبة المنخفضة". التحسين عبر الإنترنت . 202 ( 1-2 ): 47-92 . arXiv : 2105.05947 . doi : 10.1007/s10107-023-01933-9 .
  18. ↑ نغوين، إل تي؛ كيم، جيه؛ كيم، إس؛ شيم، بي (2019). "تحديد موقع شبكات إنترنت الأشياء عبر إكمال المصفوفة منخفضة الرتبة". معاملات IEEE في الاتصالات . 67 (8): 5833-5847 . Bibcode : 2019ITCom..67.5833N . doi : 10.1109/TCOMM.2019.2915226 . S2CID 164605437 . 
  19. ↑ ماهيندري، ج.؛ جاياسومانا، أ.ب.؛ غاجاماناج، ك.؛ بافينروث، ر. (2019). "حول أخذ العينات واستعادة طوبولوجيا الشبكات الاجتماعية الموجهة - نهج قائم على إكمال المصفوفة منخفضة الرتبة". المؤتمر الرابع والأربعون لشبكات الحاسوب المحلية (LCN) لعام 2019. معهد مهندسي الكهرباء والإلكترونيات. الصفحات 324-331 . doi : 10.1109/LCN44214.2019.8990707 . ISBN  978-1-7281-1028-8. S2CID 211206354 .