تکمیل ماتریس

در این بحث معمولاً هر گاه از ماتریس صحبت می‌شود ماتریس هرمیتی مورد نظر است(ماتریس متقارن). اگر ماتریس مجهول ما M نامیده شود که دارای  ${\displaystyle n^2}$

فرض کنید ${\displaystyle M\in R^{(n_1\times n_2)}}$

${\displaystyle [{\mathcal{p}}_{\mathrm{\Omega }}(x){]}_{ij}=\{\begin{array}{l}{x}_{ij}(i,j)\in \mathrm{\Omega }\\ 0O.W\end{array}}$

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

${\displaystyle M_{ij}=x_i{y}_j}$

بنابراین اگر هیچ نمونه‌ای از سطر اول در دسترس نباشد برای مثال هرگز نمی توان مقدار اولین جزء ${\displaystyle x_1}$

باید فضای سطری و ستونی ماتریس در تمامی مختصات گسترده شده باشد و در اصطلاح ماتریس باید ناهمدوس باشد بنابراین پارامتر ${\displaystyle {\mu }_0}$

${\displaystyle max\Vert U^T{e}_i{\Vert }_2⩽\sqrt{{\mu }_{0}r/n_1}}$

${\displaystyle max\Vert V^T{e}_i{\Vert }_2⩽\sqrt{{\mu }_{0}r/n_2}}$

${\displaystyle max|(UV{)}_{i,j}{|}_2⩽\sqrt{{\mu }_{1}r/n_1{n}_2}}$

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

الگوریتم بازیابی

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

$min\Vert X{\Vert }_{\ast }\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}{\mathcal{p}}_{\mathrm{\Omega }}(M)={\mathcal{p}}_{\mathrm{\Omega }}(X)$

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