تکمیل ماتریس

تکمیل ماتریس به عمل کامل کردن همهٔ درایه های یک ماتریس با استفاده از داشتن تعداد محدودی از درایه های آن می باشد. [ ۱] یکی از کاربردهای این مسئله در تخمین نظرات کاربران سایت اجاره فیلم نت فلیکس می باشد.
فرض کنید تعداد m مشتری تعدادی فیلم را از مجموعه n عضوی کلوپ اجاره فیلم مشاهده کرده اند و نمره ای داده اند. هدف تخمین نمرهٔ فیلم های مشاهده نشده می باشد. به طور کلی در بسیاری از مسائل عملی می خواهیم یک ماتریس را با نمونه برداری از داده های آن بازیابی کنیم. همچنین به عنوان مثالی دیگر پیش بینی جواب های افراد در یک نظرسنجی را در نظر بگیرید، فرض می کنیم افراد سطرهای یک ماتریس را تشکیل داده و سوالات ستونها را تشکیل می دهند. با جمع آوری اطلاعات این ماتریس تکمیل می شود اما فرض کنید بسیاری از این سوالات بدون پاسخ باشد. آیا ممکن است بتوانیم حدس بزنیم جاهای خالی را با چه پاسخ های می توان پر کرد؟ چطور باید حدس زد؟ در واقع ما علاقمند به بازیابی ماتریس   M با سطر و  ستون هستیم اما فقط m نمونه را مشاهده کردیم که به نسبت عدد بسیار کوچکی است. آیا می توان بازیابی را با این تعداد نمونه مشاهده شده انجام داد؟ عموماً موافقند که این بازیابی غیرممکن است مگر با داشتن یکسری اطلاعات اضافه تا بتوان ماتریس را بازیابی نمود. [ ۲] در بسیاری از مثال ها ماتریسی که علاقمند به بازیابی آن هستیم رتبه پایین یا تقریباً رتبه پایین است.
در این بحث معمولاً هر گاه از ماتریس صحبت می شود ماتریس هرمیتی مورد نظر است ( ماتریس متقارن ) . اگر ماتریس مجهول ما M نامیده شود که دارای   n 2 بعد در فضای خطی باشد. اگر Ω r   نماینده تمام مختصات هایی از M باشد که در مورد آن ها می دانیم و همچنین مختصات هایی که هیچ اطلاعاتی در مورد تصویر M روی آن ها نداریم را با   Ω ⊥   نمایش می دهیم. بنابراین تمامی ماتریس هایی که با اطلاعات موجود سازگارند صفحه ای می سازند که آن را به نام فضای شدنی می شناسیم.
فرض کنید M ∈ R ( n 1 × n 2 )   ماتریسی است که می خواهیم آن را بازیابی کنیم. تنها اطلاعاتی که از این ماتریس داریم تعدادی از داده های آن است که به صورت نمونه برداری شده نیز بوده و به صورت   ( i , j ) ∈ Ω ,   M i j که Ω   یک زیر مجموعه از ماتریس اصلی نیز هست. عملگر نمونه بردار به صورت p : R n 1 × n 2 → R n 1 × n 2 است که می توان به صورت زیر نوشت: