تکمیل ماتریس

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

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

فضای شدنی[3]

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

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

${\displaystyle [{\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) امین درایه برابر است با:

${\displaystyle M_{ij}=x_{i}y_{j}}$

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

باید فضای سطری و ستونی ماتریس در تمامی مختصات گسترده شده باشد و در اصطلاح ماتریس باید ناهمدوس باشد بنابراین پارامتر ${\displaystyle \mu _{0}}$ برای محدود کردن همدوسی ماتریس تعریف می‌شود که کم بودن مقدار آن باعث جلوگیری از تمرکز داده‌ها در یک  سطر یا ستون خاص می گردد، این الزام بخاطر نمونه برداری یکنواخت باید برقرار باشد. ماتریس M همچنین باید پارامتر ${\displaystyle \mu _{1}}$ را تحت عنوان ناهمدوسی مشترک ارضا کند:

${\displaystyle \max \|U^{T}e_{i}\|_{2}\leqslant {\sqrt {\mu _{0}r/n_{1}}}}$

${\displaystyle \max \|V^{T}e_{i}\|_{2}\leqslant {\sqrt {\mu _{0}r/n_{2}}}}$

${\displaystyle \max |(UV)_{i,j}|_{2}\leqslant {\sqrt {\mu _{1}r/n_{1}n_{2}}}}$

تعریف ارائه شده همدوسی در بالا همراه با فرض نمونه برداری یکنواخت و مستقل صادق است.

الگوریتم بازیابی[1]

اگر بردار تکین‌های ماتریس M در مختصات‌های مختلف پخش شوند امیدوار خواهیم بود ماتریس رتبه پایینی وجود داشته باشد که شامل داده‌های مشاهده شده هم باشد، برای بازیابی پاسخ از مسئله بهینه‌سازی زیر استفاده می‌شود.

${\textstyle \min \|X\|_{*}\quad \quad \mathrm {subject\quad to} \quad \quad {\mathcal {p}}_{\Omega }(M)={\mathcal {p}}_{\Omega }(X)}$

جستارهای وابسته

• بهینه‌سازی محدب
• پالایش گروهی

منابع

1. E. J. Candès and B. Recht, "Exact matrix completion via convex optimization", Found. of Comput. Math. , 2008
2. «Matrix Completion With Noise - IEEE Xplore Document» (به انگلیسی). دریافت‌شده در ۲۰۱۷-۰۱-۲۸.
3. «Recovering Low-Rank Matrices From Few Coefficients in Any Basis - IEEE Xplore Document» (به انگلیسی). دریافت‌شده در ۲۰۱۷-۰۱-۲۸.