تکمیل ماتریس

بندانگشتی
تکمیل ماتریس به عمل کامل کردن همه درایه‌های یک ماتریس با استفاده از داشتن تعداد محدودی از درایه‌های آن می‌باشد.
یکی از کاربردهای این مسئله در تخمین نظرات کاربران سایت اجاره فیلم می‌باشد.
فرض کنید تعداد m
مشتری تعدادی فیلم را از مجموعه n عضوی کلوپ اجاره فیلم مشاهده کرده‌اند و نمره‌ای داده‌اند. هدف تخمین نمره فیلم‌های مشاهده نشده می‌باشد. به‌طور کلی در بسیاری از مسائل عملی می‌خواهیم یک ماتریس را با نمونه برداری از داده‌های آن بازیابی کنیم. همچنین به عنوان مثالی دیگر پیش‌بینی جواب‌های افراد در یک نظرسنجی را در نظر بگیرید، فرض می‌کنیم افراد سطرهای یک ماتریس را تشکیل داده و سوالات ستونها را تشکیل می‌دهند. با جمع‌آوری اطلاعات این ماتریس تکمیل می‌شود اما فرض کنید بسیاری از این سوالات بدون پاسخ باشد. آیا ممکن است بتوانیم حدس بزنیم جاهای خالی را با چه پاسخ‌های می‌توان پر کرد؟ چطور باید حدس زد؟ در واقع ما علاقمند به بازیابی ماتریس M
با سطر و ستون هستیم اما فقط m
نمونه را مشاهده کردیم که به نسبت عدد بسیار کوچکی است. آیا می‌توان بازیابی را با این تعداد نمونه مشاهده شده انجام داد؟ عموما موافقند که این بازیابی غیرممکن است مگر با داشتن یکسری اطلاعات اضافه تا بتوان ماتریس را بازیابی نمود. در بسیاری از مثال‌ها ماتریسی که علاقمند به بازیابی آن هستیم رتبه پایین یا تقریبا رتبه پایین است.
فضای شدنی
در این بحث معمولا هر گاه از ماتریس صحبت می‌شود ماتریس هرمیتی مورد نظر است(ماتریس متقارن). اگر ماتریس مجهول ما M نامیده شود که دارای n^2
بعد در فضای خطی باشد. اگر \Omega_r
نماینده تمام مختصات‌هایی از M باشد که در مورد آن‌ها می‌دانیم و همچنین مختصات‌هایی که هیچ اطلاعاتی در مورد تصویر M روی آن‌ها نداریم را با \Omega^\perp
نمایش می‌دهیم. بنابراین تمامی ماتریس‌هایی که با اطلاعات موجود سازگارند صفحه‌ای می‌سازند که آن را به نام فضای شدنی می‌شناسیم.
فرض کنید ماتریسی است که می‌خواهیم آن را بازیابی کنیم. تنها اطلاعاتی که از این ماتریس داریم تعدادی از داده‌های آن است که به صورت نمونه برداری شده نیز بوده و به صورت , که یک زیر مجموعه از ماتریس اصلی نیز هست. عملگر نمونه بردار به صورت است که می‌توان به صورت زیر نوشت:
واضح است اگر مجموعه نمونه بردار از نمونه‌های یک ستون یا یک سطر ماتریس M اجتناب کند نمی‌توان امیدوار به بازسازی ماتریس M بود حتی اگر رتبه ماتریس 1 باشد. M را با رتبه 1 در نظر بگیرید و به صورت ضرب دو بردار که *xy که x و y بردارهای n بعدی هستند بنابراین (i,j) امین درایه برابر است با:
بنابراین اگر هیچ نمونه‌ای از سطر اول در دسترس نباشد برای مثال هرگز نمی‌توان مقدار اولین جزء را حدس زد. در واقع هیچ اطلاعاتی از مشاهده نشده است. بنابراین برای بازسازی ماتریس نامعلوم حداقل باید در هر ستون و در هر ردیف یک نمونه مشاهده کرده باشیم. اگر نمونه برداری به صورتی باشد که تمامی نمونه‌های مشاهده شده برای یک سطر باشند، سپس حتی قادر به بازیابی ماتریس با رتبه 1 نخواهیم بود.
باید فضای سطری و ستونی ماتریس در تمامی مختصات گسترده شده باشد و در اصطلاح ماتریس باید ناهمدوس باشد بنابراین پارامتر برای محدود کردن همدوسی ماتریس تعریف می‌شود که کم بودن مقدار آن باعث جلوگیری از تمرکز داده‌ها در یک سطر یا ستون خاص می‌گردد، این الزام بخاطر نمونه برداری یکنواخت باید برقرار باشد. ماتریس M همچنین باید پارامتر را تحت عنوان ناهمدوسی مشترک ارضا کند:
\max \|U^Te_i\|_2\leqslant\sqrt{\mu_0r/n_1
\max \|V^Te_i\|_2\leqslant\sqrt{\mu_0r/n_2
\max |(UV)_{i,j|_2\leqslant\sqrt{\mu_1r/n_1n_2
تعریف ارائه شده همدوسی در بالا همراه با فرض نمونه برداری یکنواخت و مستقل صادق است.
الگوریتم بازیابی
اگر بردار تکین‌های ماتریس M در مختصات‌های مختلف پخش شوند امیدوار خواهیم بود ماتریس رتبه پایینی وجود داشته باشد که شامل داده‌های مشاهده شده هم باشد، برای بازیابی پاسخ از مسئله بهینه‌سازی زیر استفاده می‌شود.
\min \|X\|_*\quad \quad \mathrm{subject\quad to \quad \quad \mathcal{p_\Omega(M)=\mathcal{p_\Omega(X)
بهینه‌سازی محدب
پالایش گروهی