تکمیل ماتریس
تکمیل ماتریس به عمل کامل کردن همهٔ درایه‌های یک ماتریس با استفاده از داشتن تعداد محدودی از درایه‌های آن می‌باشد. یکی از کاربردهای این مسئله در تخمین نظرات کاربران سایت اجاره فیلم نت فلیکس می‌باشد.
فرض کنید تعداد formula_1 مشتری تعدادی فیلم را از مجموعه n عضوی کلوپ اجاره فیلم مشاهده کرده‌اند و نمره‌ای داده‌اند. هدف تخمین نمرهٔ فیلم‌های مشاهده نشده می‌باشد. به‌طور کلی در بسیاری از مسائل عملی می خواهیم یک ماتریس را با نمونه برداری از داده‌های آن بازیابی کنیم. همچنین به عنوان مثالی دیگر پیش‌بینی جواب‌های افراد در یک نظرسنجی را در نظر بگیرید، فرض می کنیم افراد سطرهای یک ماتریس را تشکیل داده و سوالات ستونها را تشکیل می دهند. با جمع‌آوری اطلاعات این ماتریس تکمیل می‌شود اما فرض کنید بسیاری از این سوالات بدون پاسخ باشد. آیا ممکن است بتوانیم حدس بزنیم جاهای خالی را با چه پاسخ‌های می‌توان پر کرد؟ چطور باید حدس زد؟ در واقع ما علاقمند به بازیابی ماتریس  formula_2 با سطر و ستون هستیم اما فقط formula_1 نمونه را مشاهده کردیم که به نسبت عدد بسیار کوچکی است. آیا می‌توان بازیابی را با این تعداد نمونه مشاهده شده انجام داد؟ عموماً موافقند که این بازیابی غیرممکن است مگر با داشتن یکسری اطلاعات اضافه تا بتوان ماتریس را بازیابی نمود. در بسیاری از مثال‌ها ماتریسی که علاقمند به بازیابی آن هستیم رتبه پایین یا تقریباً رتبه پایین است.
در این بحث معمولاً هر گاه از ماتریس صحبت می‌شود ماتریس هرمیتی مورد نظر است(ماتریس متقارن). اگر ماتریس مجهول ما M نامیده شود که دارای  formula_4 بعد در فضای خطی باشد. اگر formula_5 نماینده تمام مختصات‌هایی از M باشد که در مورد آن‌ها می دانیم و همچنین مختصات‌هایی که هیچ اطلاعاتی در مورد تصویر M روی آن‌ها نداریم را با  formula_6 نمایش می دهیم. بنابراین تمامی ماتریس‌هایی که با اطلاعات موجود سازگارند صفحه‌ای می سازند که آن را به نام فضای شدنی می شناسیم.
فرض کنید formula_7  ماتریسی است که می خواهیم آن را بازیابی کنیم. تنها اطلاعاتی که از این ماتریس داریم تعدادی از داده‌های آن است که به صورت نمونه برداری شده نیز بوده و به صورت  formula_8, formula_9 که formula_10 یک زیر مجموعه از ماتریس اصلی نیز هست. عملگر نمونه بردار به صورت formula_11 است که می‌توان به صورت زیر نوشت:
formula_12
واضح است اگر مجموعه نمونه بردار از نمونه‌های یک ستون یا یک سطر ماتریس M اجتناب کند نمی توان امیدوار به بازسازی ماتریس M بود حتی اگر رتبه ماتریس 1 باشد.  M را با رتبه 1 در نظر بگیرید و به صورت ضرب دو بردار که *xy که x و y بردارهای n بعدی هستند بنابراین  (i,j) امین درایه برابر است با:
formula_13
بنابراین اگر هیچ نمونه‌ای از سطر اول در دسترس نباشد برای مثال هرگز نمی توان مقدار اولین جزء formula_14 را حدس زد. در واقع هیچ اطلاعاتی از formula_14 مشاهده نشده است. بنابراین برای بازسازی ماتریس نامعلوم حداقل باید در هر ستون و در هر ردیف یک نمونه مشاهده کرده باشیم. اگر نمونه برداری به صورتی باشد که تمامی نمونه‌های مشاهده شده برای یک سطر باشند، سپس حتی قادر به بازیابی ماتریس با رتبه 1 نخواهیم بود.
باید فضای سطری و ستونی ماتریس در تمامی مختصات گسترده شده باشد و در اصطلاح ماتریس باید ناهمدوس باشد بنابراین پارامتر formula_16 برای محدود کردن همدوسی ماتریس تعریف می‌شود که کم بودن مقدار آن باعث جلوگیری از تمرکز داده‌ها در یک  سطر یا ستون خاص می گردد، این الزام بخاطر نمونه برداری یکنواخت باید برقرار باشد. ماتریس M همچنین باید پارامتر formula_17 را تحت عنوان ناهمدوسی مشترک ارضا کند:
formula_18
formula_19
formula_20
تعریف ارائه شده همدوسی در بالا همراه با فرض نمونه برداری یکنواخت و مستقل صادق است.
اگر بردار تکین‌های ماتریس M در مختصات‌های مختلف پخش شوند امیدوار خواهیم بود ماتریس رتبه پایینی وجود داشته باشد که شامل داده‌های مشاهده شده هم باشد، برای بازیابی پاسخ از مسئله بهینه‌سازی زیر استفاده می‌شود.
formula_21