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

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