تکمیل ماتریس

بندانگشتی
**تکمیل ماتریس** به عمل کامل کردن همهٔ درایه‌های یک ماتریس با استفاده از داشتن تعداد محدودی از درایه‌های آن می‌باشد.
یکی از کاربردهای این مسئله در تخمین نظرات کاربران سایت اجاره فیلم نت فلیکس می‌باشد.

فرض کنید تعداد m
 مشتری تعدادی فیلم را از مجموعه n عضوی کلوپ اجاره فیلم مشاهده کرده‌اند و نمره‌ای داده‌اند. هدف تخمین نمرهٔ فیلم‌های مشاهده نشده می‌باشد. به‌طور کلی در بسیاری از مسائل عملی می خواهیم یک ماتریس را با نمونه برداری از داده‌های آن بازیابی کنیم. همچنین به عنوان مثالی دیگر پیش‌بینی جواب‌های افراد در یک نظرسنجی را در نظر بگیرید، فرض می کنیم افراد سطرهای یک ماتریس را تشکیل داده و سوالات ستونها را تشکیل می دهند. با جمع‌آوری اطلاعات این ماتریس تکمیل می‌شود اما فرض کنید بسیاری از این سوالات بدون پاسخ باشد. آیا ممکن است بتوانیم حدس بزنیم جاهای خالی را با چه پاسخ‌های می‌توان پر کرد؟ چطور باید حدس زد؟ در واقع ما علاقمند به بازیابی ماتریس  M
 با سطر و ستون هستیم اما فقط m
 نمونه را مشاهده کردیم که به نسبت عدد بسیار کوچکی است. آیا می‌توان بازیابی را با این تعداد نمونه مشاهده شده انجام داد؟ عموماً موافقند که این بازیابی غیرممکن است مگر با داشتن یکسری اطلاعات اضافه تا بتوان ماتریس را بازیابی نمود. در بسیاری از مثال‌ها ماتریسی که علاقمند به بازیابی آن هستیم رتبه پایین یا تقریباً رتبه پایین است.

## فضای شدنی
در این بحث معمولاً هر گاه از ماتریس صحبت می‌شود ماتریس هرمیتی مورد نظر است(ماتریس متقارن). اگر ماتریس مجهول ما **M** نامیده شود که دارای  n^2
 بعد در فضای خطی باشد. اگر \Omega_r
 نماینده تمام مختصات‌هایی از **M**  باشد که در مورد آن‌ها می دانیم و همچنین مختصات‌هایی که هیچ اطلاعاتی در مورد تصویر **M** روی آن‌ها نداریم را با  \Omega^\perp
 نمایش می دهیم. بنابراین تمامی ماتریس‌هایی که با اطلاعات موجود سازگارند صفحه‌ای می سازند که آن را به نام فضای شدنی می شناسیم.

فرض کنید M\in R^{(n_1\times n_2) }  ماتریسی است که می خواهیم آن را بازیابی کنیم. تنها اطلاعاتی که از این ماتریس داریم تعدادی از داده‌های آن است که به صورت نمونه برداری شده نیز بوده و به صورت  (i,j)\in \Omega, M_{ij} که \Omega یک زیر مجموعه از ماتریس اصلی نیز هست. عملگر نمونه بردار به صورت \mathcal{p}:R^{n_1\times n_2}\rightarrow R^{n_1\times n_2} است که می‌توان به صورت زیر نوشت:

[\mathcal{p}_{\Omega}(x)]_{ij}=\begin{cases} x_{ij}\quad \quad (i,j)\in \Omega \\ 0 \quad \quad \quad O.W \end{cases}

واضح است اگر مجموعه نمونه بردار از نمونه‌های یک ستون یا یک سطر ماتریس **M** اجتناب کند نمی توان امیدوار به بازسازی ماتریس **M** بود حتی اگر رتبه ماتریس 1 باشد.  M را با رتبه 1 در نظر بگیرید و به صورت ضرب دو بردار که *xy که x و y بردارهای n بعدی هستند بنابراین  (i,j) امین درایه برابر است با:

M_{ij}=x_iy_j

بنابراین اگر هیچ نمونه‌ای از سطر اول در دسترس نباشد برای مثال هرگز نمی توان مقدار اولین جزء x_1 را حدس زد. در واقع هیچ اطلاعاتی از x_1 مشاهده نشده است. بنابراین برای بازسازی ماتریس نامعلوم حداقل باید در هر ستون و در هر ردیف یک نمونه مشاهده کرده باشیم. اگر نمونه برداری به صورتی باشد که تمامی نمونه‌های مشاهده شده برای یک سطر باشند، سپس حتی قادر به بازیابی ماتریس با رتبه 1 نخواهیم بود. 

باید فضای سطری و ستونی ماتریس در تمامی مختصات گسترده شده باشد و در اصطلاح ماتریس باید ناهمدوس باشد بنابراین پارامتر \mu_0 برای محدود کردن همدوسی ماتریس تعریف می‌شود که کم بودن مقدار آن باعث جلوگیری از تمرکز داده‌ها در یک  سطر یا ستون خاص می گردد، این الزام بخاطر نمونه برداری یکنواخت باید برقرار باشد. ماتریس **M** همچنین باید پارامتر \mu_1 را تحت عنوان ناهمدوسی مشترک ارضا کند:

\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)


## جستارهای وابسته
* بهینه‌سازی محدب
* پالایش گروهی

## منابع

رده:نظریه ماتریس‌ها