Matrix completion
میٹرکس کی تکمیل جزوی طور پر مشاہدہ شدہ میٹرکس کی گمشدہ اندراجات کو پر کرنے کا کام ہے، جو اعداد و شمار میں ڈیٹا امپوٹیشن انجام دینے کے برابر ہے۔ ڈیٹا سیٹس کی ایک وسیع رینج قدرتی طور پر میٹرکس کی شکل میں منظم ہوتی ہے۔ ایک مثال مووی ریٹنگ میٹرکس ہے، جیسا کہ نیٹ فلکس کے مسئلے میں ظاہر ہوتا ہے: ایک ریٹنگ میٹرکس کو دیکھتے ہوئے جس میں ہر اندراج گاہک کی طرف سے فلم کی درجہ بندی کی نمائندگی کرتا ہے، اگر گاہک نے فلم دیکھی ہے اور بصورت دیگر غائب ہے، تو ہم باقی اندراجات کی پیش گوئی کرنا چاہیں گے تاکہ صارفین کو آگے کیا دیکھنا ہے اس کے بارے میں اچھی سفارشات کی جا سکیں۔ ایک اور مثال ڈاکیومنٹ ٹرم میٹرکس ہے: دستاویزات کے مجموعے میں استعمال ہونے والے الفاظ کی تعدد کو میٹرکس کے طور پر پیش کیا جا سکتا ہے، جہاں ہر اندراج اس بات سے مطابقت رکھتا ہے کہ متعلقہ اصطلاح اشارہ شدہ دستاویز میں کتنی بار ظاہر ہوتی ہے۔ مکمل میٹرکس میں ڈگری آف فریڈم کی تعداد پر کسی پابندی کے بغیر اس مسئلے کا تعین نہیں کیا جاتا ہے کیونکہ پوشیدہ اندراجات کو صوابدیدی اقدار تفویض کی جا سکتی ہیں۔ اس طرح ہمیں ایک اچھی طرح سے پیش کردہ مسئلہ پیدا کرنے کے لیے میٹرکس پر کچھ مفروضے کی ضرورت ہوتی ہے، جیسے کہ یہ فرض کرنا کہ اس میں زیادہ سے زیادہ تعین کنندہ ہے، مثبت قطعی ہے، یا کم درجہ ہے۔ مثال کے طور پر، کوئی یہ فرض کر سکتا ہے کہ میٹرکس میں کم رینک کا ڈھانچہ ہے، اور پھر سب سے کم رینک کا میٹرکس تلاش کرنے کی کوشش کر سکتا ہے یا، اگر مکمل شدہ میٹرکس کا رینک معلوم ہے، تو رینک کا ایک میٹرکس جو معلوم اندراجات سے میل کھاتا ہے۔ مثال سے پتہ چلتا ہے کہ جزوی طور پر ظاہر کردہ رینک-1 میٹرکس (بائیں طرف) کو صفر غلطی (دائیں طرف) کے ساتھ مکمل کیا جا سکتا ہے کیونکہ گمشدہ اندراجات والی تمام قطاریں تیسری صف جیسی ہونی چاہئیں۔ نیٹ فلکس کے مسئلے کی صورت میں ریٹنگ میٹرکس کے کم درجے کی توقع کی جاتی ہے کیونکہ صارف کی ترجیحات کو اکثر چند عوامل سے بیان کیا جا سکتا ہے، جیسے کہ فلم کی صنف اور ریلیز کا وقت۔ دیگر ایپلی کیشنز میں کمپیوٹر وژن شامل ہے، جہاں تصاویر میں گمشدہ پکسلز کو دوبارہ تعمیر کرنے کی ضرورت ہوتی ہے، جزوی فاصلاتی معلومات سے نیٹ ورک میں سینسرز کی عالمی پوزیشننگ کا پتہ لگانا، اور ملٹی کلاس لرننگ۔ میٹرکس کی تکمیل کا مسئلہ عام طور پر این پی-سخت ہوتا ہے، لیکن اضافی مفروضوں کے تحت موثر الگورتھم ہوتے ہیں جو اعلی امکان کے ساتھ عین مطابق تعمیر نو حاصل کرتے ہیں۔ شماریاتی سیکھنے کے نقطہ نظر میں، میٹرکس تکمیل کا مسئلہ میٹرکس ریگولرائزیشن کا ایک اطلاق ہے جو ویکٹر ریگولرائزیشن کی عمومی شکل ہے۔ مثال کے طور پر، کم رینک والے میٹرکس کی تکمیل کے مسئلے میں کوئی بھی جوہری معیار کم رینک والے میٹرکس کی تکمیل کی شکل اختیار کرتے ہوئے باقاعدگی سے جرمانہ عائد کر سکتا ہے۔ میٹرکس کی تکمیل کے مسئلے کی مختلف شکلوں میں سے ایک یہ ہے کہ مشاہدہ شدہ اندراجات کے سیٹ میں تمام اندراجات کے لیے سب سے کم رینک والا میٹرکس تلاش کیا جائے جو میٹرکس سے میل کھاتا ہو، جسے ہم بازیافت کرنا چاہتے ہیں۔ اس مسئلے کی ریاضیاتی تشکیل مندرجہ ذیل ہے: کینڈس اور ریخت نے ثابت کیا کہ مشاہدہ شدہ اندراجات کے نمونے لینے کے مفروضوں اور کافی تعداد میں نمونے لینے والی اندراجات کے ساتھ اس مسئلے کا اعلی امکان کے ساتھ ایک منفرد حل ہے۔ ایک مساوی تشکیل، یہ دیکھتے ہوئے کہ بازیافت کیا جانے والا میٹرکس رینک کا جانا جاتا ہے، اس بات کو حل کرنا ہے کہ کہاں مفروضے مشاہدہ شدہ اندراجات کے نمونے لینے اور نمونے کے اندراجات کی تعداد کے بارے میں متعدد مفروضے اکثر تجزیہ کو آسان بنانے اور اس بات کو یقینی بنانے کے لیے بنائے جاتے ہیں کہ مسئلہ کم نہ ہو۔ مشاہدہ شدہ اندراجات کا یکساں نمونہ تجزیہ کو قابل عمل بنانے کے لیے، اکثر یہ فرض کیا جاتا ہے کہ مشاہدہ شدہ اندراجات اور فکسڈ کارڈینیلیٹی کے سیٹ کو کارڈینیلیٹی کے اندراجات کے تمام ذیلی سیٹوں کے مجموعہ سے بے ترتیب طور پر یکساں طور پر نمونہ لیا جاتا ہے۔ تجزیہ کو مزید آسان بنانے کے لیے، اس کے بجائے یہ فرض کیا جاتا ہے کہ اسے برنولی سیمپلنگ، یعنی۔ کہ ہر اندراج کا مشاہدہ امکان کے ساتھ کیا جاتا ہے۔ اگر سیٹ کیا گیا ہے کہ مطلوبہ متوقع کارڈینیلیٹی کہاں ہے، اور میٹرکس کے طول و عرض ہیں (عام طور پر نقصان کے بغیر)، اعلی امکان کے ساتھ اندر ہے، اس طرح برنولی نمونے لینا یکساں نمونے لینے کے لیے ایک اچھا تخمینہ ہے۔ ایک اور آسانیاں یہ فرض کرنا ہے کہ اندراجات کا نمونہ آزادانہ طور پر اور متبادل کے ساتھ لیا جاتا ہے۔ مشاہدہ شدہ اندراجات کی تعداد پر کم باؤنڈ فرض کریں کہ بائی میٹرکس (کے ساتھ) جو ہم بازیافت کرنے کی کوشش کر رہے ہیں اس کا درجہ ہے۔ منفرد طور پر دوبارہ تعمیر کرنے سے پہلے کتنی اندراجات کا مشاہدہ کیا جانا چاہیے اس پر ایک انفارمیشن تھیوریٹک لوور باؤنڈ ہے۔ میٹرکس کے لحاظ سے کم یا برابر رینک والا سیٹ طول و عرض کے ساتھ الجبرائی قسم ہے۔ اس نتیجے کا استعمال کرتے ہوئے، یہ دکھایا جا سکتا ہے کہ میٹرکس کی تکمیل کے لیے کم از کم اندراجات کا مشاہدہ کیا جانا چاہیے تاکہ ایک منفرد حل حاصل کیا جا سکے۔ دوسرا، ہر قطار اور کالم میں کم از کم ایک مشاہدہ شدہ اندراج ہونا چاہیے۔ کی واحد قدر سڑنا اس کے ذریعہ دیا جاتا ہے۔ اگر قطار کا مشاہدہ نہیں کیا جاتا ہے، تو، کے صحیح واحد ویکٹر کو دیکھنا آسان ہے، جسے کسی صوابدیدی قدر میں تبدیل کیا جا سکتا ہے اور پھر بھی مشاہدہ شدہ اندراجات کے سیٹ سے مماثل میٹرکس حاصل ہوتا ہے۔ اسی طرح، اگر کالم غیر مشاہدہ شدہ ہے، تو کا بائیں واحد ویکٹر من مانی ہو سکتا ہے۔ اگر ہم مشاہدہ شدہ اندراجات کے سیٹ کے برنولی نمونے لینے کو فرض کرتے ہیں، تو کوپن کلیکٹر اثر کا مطلب یہ ہے کہ کے ترتیب پر اندراجات کا مشاہدہ کیا جانا چاہیے تاکہ یہ یقینی بنایا جا سکے کہ ہر صف اور کالم سے اعلی امکان کے ساتھ مشاہدہ ہے۔ ضروری شرائط کو یکجا کرتے ہوئے اور یہ فرض کرتے ہوئے کہ (بہت سے عملی ایپلی کیشنز کے لیے ایک درست مفروضہ)، میٹرکس کی تکمیل کے مسئلے کو کم طے ہونے سے روکنے کے لیے درکار مشاہدہ شدہ اندراجات کی تعداد کی نچلی حد کی ترتیب پر ہے۔ مطابقت نہ ہونے کا تصور کمپریسڈ سینسنگ میں پیدا ہوا۔ اسے میٹرکس کی تکمیل کے تناظر میں متعارف کرایا گیا ہے تاکہ یہ یقینی بنایا جا سکے کہ کے واحد ویکٹر اس لحاظ سے بہت کم "کم" نہ ہوں کہ ہر واحد ویکٹر کے تمام نقاط قابل ذکر حد تک بڑے طول و عرض والے صرف چند نقاط کے بجائے تقابلی شدت کے ہوں۔ اس کے بعد معیاری بیس ویکٹر واحد ویکٹر کے طور پر ناپسندیدہ ہوتے ہیں، اور ویکٹر میں مطلوب ہوتا ہے۔ اگر واحد ویکٹر کافی حد تک "کم" ہوں تو کیا غلط ہو سکتا ہے اس کی ایک مثال کے طور پر، واحد قدر سڑنے کے ساتھ بائی میٹرکس پر غور کریں۔ اس کی تعمیر نو سے پہلے تقریبا تمام اندراجات کا نمونہ لینا ضروری ہے۔ کینڈس اور ریخت کالم کی جگہ کے ساتھ ایک میٹرکس کی ہم آہنگی کی وضاحت کرتے ہیں جس کی ایک جہتی ذیلی جگہ ہے، جہاں آرتھوگنل پروجیکشن ہے۔ عدم مطابقت اس کے بعد اس بات پر زور دیتی ہے کہ میٹرکس کے ذریعہ واحد قدر کے سڑنے کو دیکھتے ہوئے، کے اندراجات میں کچھ کے لیے طول و عرض زیادہ ہوتے ہیں۔ شور کے ساتھ کم درجہ میٹرکس کی تکمیل حقیقی دنیا کی درخواست میں، اکثر صرف چند اندراجات کا مشاہدہ کیا جاتا ہے جو کم از کم تھوڑی مقدار میں شور سے خراب ہوتے ہیں۔ مثال کے طور پر، نیٹ فلکس کے مسئلے میں، درجہ بندی غیر یقینی ہے۔ کینڈس اور پلان نے دکھایا کہ جوہری معیار کو کم سے کم کرکے صرف چند شور والے نمونوں سے بڑے کم درجے کے میٹرکس کی بہت سی گمشدہ اندراجات کو پر کرنا ممکن ہے۔ شور والا ماڈل یہ فرض کرتا ہے کہ ہم مشاہدہ کرتے ہیں کہ شور کی اصطلاح کہاں ہے۔ نوٹ کریں کہ شور یا تو غیر معمولی یا فیصلہ کن ہو سکتا ہے۔ متبادل طور پر ماڈل کا اظہار اس طرح کیا جا سکتا ہے کہ یہ فرض کرنے کے لیے کہ کچھ کے لیے اندراجات کے ساتھ میٹرکس کہاں ہے۔ نامکمل میٹرکس کو بازیافت کرنے کے لیے، ہم مندرجہ ذیل اصلاح کے مسئلے کو حل کرنے کی کوشش کرتے ہیں: اعداد و شمار سے مطابقت رکھنے والے تمام میٹرکس میں، کم از کم نیوکلیئر معیار کے ساتھ ایک تلاش کریں۔ کینڈس اور پلان نے دکھایا ہے کہ یہ تعمیر نو درست ہے۔ انہوں نے ثابت کیا ہے کہ جب کامل بے شور بازیابی ہوتی ہے، تو میٹرکس کی تکمیل رکاوٹ کے مقابلے میں مستحکم ہوتی ہے۔ غلطی شور کی سطح کے متناسب ہے۔ لہذا، جب شور کی سطح چھوٹی ہوتی ہے، تو غلطی چھوٹی ہوتی ہے۔ یہاں میٹرکس تکمیل کا مسئلہ محدود آئسومیٹری پراپرٹی (آر آئی پی) کی پابندی نہیں کرتا ہے۔ میٹرکس کے لیے، آر آئی پی یہ فرض کرے گا کہ سیمپلنگ آپریٹر تمام میٹرکس کی اطاعت کرتا ہے جن کا رینک کافی چھوٹا اور کافی چھوٹا ہے۔ یہ طریقے شاذ و نادر سگنل کی بازیابی کے مسائل پر بھی لاگو ہوتے ہیں جن میں آر آئی پی نہیں ہوتا ہے۔ اعلی درجہ میٹرکس کی تکمیل عام طور پر اعلی درجہ میٹرکس کی تکمیل این پی-ہارڈ ہوتی ہے۔ تاہم، بعض مفروضوں کے ساتھ، کچھ نامکمل اعلی رینک میٹرکس یا یہاں تک کہ مکمل رینک میٹرکس بھی مکمل کیا جا سکتا ہے۔ ایرکسن، بالزانو اور نواک نے میٹرکس کو مکمل کرنے کے مسئلے پر اس مفروضے کے ساتھ غور کیا ہے کہ میٹرکس کے کالم متعدد کم درجے کی ذیلی جگہوں کے اتحاد سے تعلق رکھتے ہیں۔ چونکہ کالم ذیلی جگہوں کے اتحاد سے تعلق رکھتے ہیں، اس مسئلے کو ذیلی جگہ کلسٹرنگ مسئلے کے گمشدہ ڈیٹا ورژن کے طور پر دیکھا جا سکتا ہے۔ ایک میٹرکس ہونے دیں جس کے (مکمل) کالم زیادہ سے زیادہ ذیلی جگہوں کے اتحاد میں ہوتے ہیں، ان میں سے ہر ایک، اور فرض کریں۔ ایرکسن، بالزانو اور نواک نے دکھایا کہ ہلکے مفروضوں کے تحت ہر کالم کو ایک نامکمل ورژن سے اعلی امکان کے ساتھ مکمل طور پر بازیافت کیا جاسکتا ہے جب تک کہ کم از کم اندراجات کو بے ترتیب طور پر یکساں طور پر مشاہدہ کیا جائے، جس کا انحصار معمول کی عدم مطابقت کے حالات، ذیلی جگہوں کی ہندسی ترتیب، اور ذیلی جگہوں پر کالموں کی تقسیم پر ہوتا ہے۔ الگورتھم میں کئی مراحل شامل ہیں: (1) مقامی محلے ؛ (2) مقامی ذیلی جگہیں ؛ (3) ذیلی جگہ کی اصلاح ؛ (4) مکمل میٹرکس کی تکمیل۔ یہ طریقہ انٹرنیٹ ڈسٹنس میٹرکس کی تکمیل اور ٹوپولوجی شناخت پر لاگو کیا جا سکتا ہے۔ کم درجہ میٹرکس تکمیل کے لیے الگورتھم مختلف میٹرکس تکمیل الگورتھم تجویز کیے گئے ہیں۔ ان میں کنویکس ریلیکسشن پر مبنی الگورتھم، گریڈینٹ پر مبنی الگورتھم، اور باری باری کم سے کم کرنے پر مبنی الگورتھم شامل ہیں۔ کنویکس میں نرمی درجہ بندی کو کم کرنے کا مسئلہ این پی-ہارڈ ہے۔ ایک نقطہ نظر، جو کینڈس اور ریخت کی طرف سے تجویز کیا گیا ہے، وہ یہ ہے کہ مسئلے کی کنویکس نرمی کی تشکیل کی جائے اور جوہری معیار کو کم سے کم کیا جائے (جو واحد اقدار کا مجموعہ دیتا ہے) اس کے بجائے (جو غیر صفر واحد اقدار کی تعداد کو شمار کرتا ہے)۔ یہ ویکٹر کے لیے L0-نارم کے بجائے L1-نارم کو کم کرنے کے مترادف ہے۔ کنویکس نرمی کو سیمیڈفائنٹ پروگرامنگ (ایس ڈی پی) کا استعمال کرتے ہوئے یہ دیکھ کر حل کیا جا سکتا ہے کہ اصلاح کا مسئلہ کنویکس نرمی کو حل کرنے کے لیے ایس ڈی پی کے استعمال کی پیچیدگی کے برابر ہے۔ ایس ڈی پی ٹی 3 جیسے جدید ترین حل کنندگان صرف 100 سے 100 تک کے سائز کے میٹرکس کو سنبھال سکتے ہیں۔ ایک متبادل فرسٹ آرڈر طریقہ جو تقریبا کنویکس نرمی کو حل کرتا ہے وہ کائی، کینڈس اور شین کے ذریعہ متعارف کرایا گیا سنگل ویلیو تھریش ہولڈنگ الگورتھم ہے۔ کینڈیس اور ریخت، بناچ خالی جگہوں پر بے ترتیب متغیرات کے مطالعہ کا استعمال کرتے ہوئے، ظاہر کرتے ہیں کہ اگر مشاہدہ شدہ اندراجات کی تعداد کی ترتیب پر ہے (عام طور پر نقصان کے بغیر فرض کریں)، تو رینک کم سے کم کرنے کے مسئلے کا ایک انوکھا حل ہوتا ہے جو اس کا حل بھی ہوتا ہے۔ کچھ مستقل کے امکانات کے ساتھ متغیر نرمی۔ اگر کا درجہ چھوٹا ہے ()، تو مشاہدات کے سیٹ کا سائز کم ہو کر کے ترتیب میں آ جاتا ہے۔ یہ نتائج زیادہ سے زیادہ قریب ہیں، کیونکہ میٹرکس کی تکمیل کے مسئلے کو کم سے کم نہ طے کرنے کے لیے اندراجات کی کم سے کم تعداد کا مشاہدہ کرنا ضروری ہے۔ اس نتیجے کو کینڈیس اور تاؤ نے بہتر بنایا ہے۔ وہ ان حدود کو حاصل کرتے ہیں جو مفروضوں کو مضبوط بنا کر صرف پولی لوگرتھمک عوامل کے ذریعے زیادہ سے زیادہ حدود سے مختلف ہوتی ہیں۔ انکوہیرینس پراپرٹی کے بجائے، وہ پیرامیٹر کے ساتھ مضبوط انکوہیرینس پراپرٹی کو فرض کرتے ہیں۔ اس خاصیت میں کہا گیا ہے کہ: کے لیے اور کے لیے کی اندراجات شدت میں بدیہی طور پر پابند ہیں، میٹرکس کی مضبوط عدم مطابقت اس بات پر زور دیتی ہے کہ معیاری بیس ویکٹرز کے آرتھوگنل پروجیکشنز میں طول و عرض کا زیادہ امکان ہوتا ہے اگر واحد ویکٹرز کو تصادفی طور پر تقسیم کیا گیا ہو۔ کینڈیس اور تاؤ کو معلوم ہوا کہ مشاہدہ شدہ اندراجات کی تعداد کب ہے اور اس کی ترتیب پر ہے، رینک کم سے کم کرنے کے مسئلے کا ایک انوکھا حل ہے جو کچھ مستقل کے امکان کے ساتھ اس کے کنویکس نرمی کا حل بھی ہوتا ہے۔ صوابدیدی کے لیے، اس دعوے کے لیے کافی مشاہدہ شدہ اندراجات کی تعداد درست ہے جو کہ ایک اور کنویکس نرمی کا نقطہ نظر ہے کہ درجہ بندی کی رکاوٹ کے تحت فروبینیوس مربع شدہ معیار کو کم سے کم کیا جائے۔ یہ حل کرنے کے مساوی ہے۔ ایک آرتھوگنل پروجیکشن میٹرکس (معنی) کو متعارف کرانے کے ذریعے رینک کا نمونہ بنانے اور اس مسئلے کی کنویکس نرمی کو لینے کے لیے، ہم مندرجہ ذیل سیمی فائنائٹ پروگرام حاصل کرتے ہیں۔ اگر Y اس نرمی میں ایک پروجیکشن میٹرکس ہے (یعنی، بائنری آئجن ویلیوز ہے)، تو نرمی سخت ہے۔ بصورت دیگر، یہ مجموعی مقصد پر ایک درست نچلی حد دیتا ہے۔ مزید برآں، اسے لالچ سے Y کی آئجن ویلیوز کو گول کرکے (قدرے) بڑے مقصد کے ساتھ ایک قابل عمل حل میں تبدیل کیا جا سکتا ہے۔ قابل ذکر بات یہ ہے کہ اس کنویکس نرمی کو کسی بھی ایس ڈی پیز کو حل کیے بغیر ایکس اور وائی پر باری باری کم سے کم کرکے حل کیا جا سکتا ہے، اور اس طرح یہ ایس ڈی پی ٹی 3 یا موسک جیسے جدید ترین ایس ڈی پی حل کرنے والوں کی عام عددی حدود سے آگے بڑھ جاتا ہے۔ یہ نقطہ نظر ایک زیادہ عام اصلاح کی تکنیک کا ایک خاص معاملہ ہے، جس کا اطلاق ٹریس میٹرکس کنویکس مقصد کے ساتھ کسی بھی نچلے درجے کے مسئلے پر درست نچلی حد حاصل کرنے کے لیے کیا جا سکتا ہے۔ گریڈیئنٹ ڈیسنٹ کیشوان، مونٹاناری اور اوہ میٹرکس کی تکمیل کی ایک قسم پر غور کرتے ہیں جہاں بائی میٹرکس کا درجہ، جسے بازیافت کیا جانا ہے، جانا جاتا ہے۔ وہ اندراجات کے برنولی نمونے لینے، مستقل پہلو تناسب، اندراجات کی باؤنڈڈ شدت (اوپری باؤنڈ ہونے دیں)، اور مستقل کنڈیشن نمبر (جہاں اور بالترتیب سب سے بڑی اور سب سے چھوٹی واحد اقدار ہیں) کو فرض کرتے ہیں۔ مزید برآں، وہ فرض کرتے ہیں کہ دو عدم مطابقت کے حالات مطمئن ہیں اور کہاں اور مستقل ہیں۔ ایک میٹرکس ہونے دیں جو مشاہدہ شدہ اندراجات کے سیٹ سے میل کھاتا ہے اور کہیں اور 0 ہے۔ اس کے بعد وہ مندرجہ ذیل الگورتھم کی تجویز کرتے ہیں: کالموں میں اندراجات کو 0 پر سیٹ کرنے کے مقابلے میں بڑے درجے والے کالموں سے تمام مشاہدات کو ہٹا کر ٹرم کریں۔ اسی طرح ان تمام مشاہدات کو صفوں سے ہٹا دیں جن کی ڈگری اس سے بڑی ہو۔ اس کے پہلے بنیادی اجزاء پر پروجیکٹ کریں۔ نتیجے والے میٹرکس کو کال کریں۔ لائن سرچ کے ساتھ گریڈینٹ ڈیسنٹ کے ذریعے کچھ ریگولرائزیشن فنکشن کہاں ہے حل کریں۔ کہاں پر شروع کریں۔ کچھ فنکشن کے طور پر سیٹ کریں جو گریڈینٹ نزول کے دوران متضاد رہنے پر مجبور کرتا ہے اگر اور متضاد ہیں۔ میٹرکس واپس کریں۔ الگورتھم کے مراحل 1 اور 2 سے ایک میٹرکس حاصل ہوتا ہے جو حقیقی میٹرکس کے بہت قریب ہوتا ہے (جیسا کہ روٹ مین اسکوائر ایرر (RMSE) کے ذریعے ماپا جاتا ہے) جس میں زیادہ امکان ہوتا ہے۔ خاص طور پر، امکان کے ساتھ، کچھ مستقل کے لیے۔ فروبینیوس معیار کی نشاندہی کرتا ہے۔ نوٹ کریں کہ اس نتیجے کو برقرار رکھنے کے لیے مفروضوں کے مکمل مجموعے کی ضرورت نہیں ہے۔ عدم مطابقت کی حالت، مثال کے طور پر، صرف صحیح تعمیر نو میں کام میں آتی ہے۔ آخر میں، اگرچہ ٹرمنگ متضاد لگ سکتی ہے کیونکہ اس میں معلومات کو باہر پھینکنا شامل ہے، یہ اس بات کو یقینی بناتا ہے کہ اس کے پہلے بنیادی اجزاء پر پیش کرنا مشاہدہ شدہ اندراجات کے مقابلے میں بنیادی میٹرکس کے بارے میں زیادہ معلومات فراہم کرتا ہے۔ مرحلہ 3 میں، امیدوار میٹرکس کی جگہ کو یہ دیکھ کر کم کیا جا سکتا ہے کہ اندرونی کم سے کم مسئلہ کا حل کہاں کے لیے ہے اور میٹرکس کے لحاظ سے آرتھونورمل ہے۔ پھر دو گراس مین مینیفولڈز کے کراس پروڈکٹ پر گریڈینٹ ڈیسنٹ کیا جا سکتا ہے۔ اگر اور مشاہدہ شدہ اندراج سیٹ کی ترتیب میں ہے، تو مرحلہ 3 کے ذریعہ واپس کیا گیا میٹرکس بالکل ہے۔ پھر الگورتھم آرڈر آپٹیمل ہے، کیونکہ ہم جانتے ہیں کہ میٹرکس کی تکمیل کے مسئلے کو کم کرنے کے لیے اندراجات کی تعداد کی ترتیب میں ہونی چاہیے۔ کم سے کم مربعوں کو متبادل کم سے کم کرنا کم درجے کے میٹرکس کو تلاش کرنے کے لیے ایک وسیع پیمانے پر قابل اطلاق اور تجرباتی طور پر کامیاب نقطہ نظر کی نمائندگی کرتا ہے جو دیئے گئے ڈیٹا میں بہترین فٹ ہوتے ہیں۔ مثال کے طور پر، کم رینک والے میٹرکس کی تکمیل کے مسئلے کے لیے، یہ طریقہ انتہائی درست اور موثر سمجھا جاتا ہے، اور نیٹ فلکس کے مسئلے میں جیتنے والے اندراج کا ایک اہم جزو بنتا ہے۔ متبادل کم سے کم کرنے کے نقطہ نظر میں، کم درجے کا ٹارگٹ میٹرکس دو لکیری شکل میں لکھا جاتا ہے: الگورتھم پھر بہترین اور بہترین کو تلاش کرنے کے درمیان بدلتا ہے۔ اگرچہ مجموعی مسئلہ غیر کنویکس ہے، لیکن ہر ذیلی مسئلہ عام طور پر کنویکس ہوتا ہے اور اسے مؤثر طریقے سے حل کیا جا سکتا ہے۔ جین، نیتراپلی اور سنگھوی نے میٹرکس تکمیل اور میٹرکس سینسنگ دونوں کے لیے باری باری کم سے کم کرنے کی کارکردگی کے لیے پہلی ضمانتوں میں سے ایک دی ہے۔ متبادل کم سے کم الگورتھم کو مندرجہ ذیل غیر متغیر مسئلے کو حل کرنے کے ایک اندازے کے طور پر دیکھا جا سکتا ہے: جین، نیتراپلی اور سنگھوی کی طرف سے تجویز کردہ آلٹ من کمپلٹ الگورتھم یہاں درج ہے: ان پٹ: مشاہدہ شدہ سیٹ، تقسیم کو ذیلی سیٹوں میں قدر کرتا ہے جس میں ہر عنصر کا تعلق مساوی امکان کے ساتھ ہوتا ہے (متبادل کے ساتھ نمونہ لینا) یعنی کلپنگ کے اوپر بائیں واحد ویکٹر: اس کے تمام عناصر کو صفر سے زیادہ شدت کے ساتھ سیٹ کریں اور واپسی کے لیے فار ڈو اینڈ کے کالموں کو آرتھونورملائز کریں انہوں نے دکھایا کہ ایک غیر متغیر میٹرکس کی بے ترتیب اندراجات کا مشاہدہ کرکے، آلٹ من کمپلٹ الگورتھم مراحل میں بازیافت کر سکتا ہے۔ نمونے کی پیچیدگی () کے لحاظ سے، نظریاتی طور پر، متبادل کم سے کم کرنے کے لیے کنویکس ریلیکسشن سے بڑے کی ضرورت پڑ سکتی ہے۔ تاہم تجرباتی طور پر ایسا نہیں لگتا جس کا مطلب ہے کہ نمونے کی پیچیدگی کی حدود کو مزید سخت کیا جا سکتا ہے۔ وقت کی پیچیدگی کے لحاظ سے، انہوں نے دکھایا کہ آلٹ من کمپلٹ کو وقت درکار ہے۔ یہ بات قابل غور ہے کہ اگرچہ کنویکس نرمی پر مبنی طریقوں کا سخت تجزیہ ہوتا ہے، لیکن کم سے کم کرنے پر مبنی الگورتھم عملی طور پر زیادہ کامیاب ہوتے ہیں۔ ایپلی کیشنز میٹرکس کی تکمیل کی متعدد ایپلی کیشنز کا خلاصہ کینڈس اور پلان کے ذریعے مندرجہ ذیل کیا گیا ہے: باہمی تعاون سے فلٹرینگ باہمی تعاون سے فلٹرینگ بہت سے صارفین سے ذائقہ کی معلومات اکٹھا کرکے صارف کے مفادات کے بارے میں خودکار پیش گوئیاں کرنے کا کام ہے۔ ایپل، ایمیزون، بارنس اینڈ نوبل، اور نیٹ فلکس جیسی کمپنیاں جزوی علم سے اپنے صارف کی ترجیحات کی پیش گوئی کرنے کی کوشش کر رہی ہیں۔ اس قسم کے میٹرکس کی تکمیل کے مسئلے میں، نامعلوم مکمل میٹرکس کو اکثر کم درجہ سمجھا جاتا ہے کیونکہ صرف چند عوامل عام طور پر کسی فرد کے ذوق یا ترجیح میں حصہ ڈالتے ہیں۔ نظام کی شناخت کنٹرول میں، کوئی بھی ایک مجرد وقت کے لکیری وقت کے متغیر اسٹیٹ اسپیس ماڈل کو ان پٹ اور آؤٹ پٹ کی ترتیب میں فٹ کرنا چاہے گا۔ ویکٹر وقت پر نظام کی حالت ہے اور نظام ماڈل کی ترتیب ہے۔ ان پٹ/آؤٹ پٹ جوڑی سے، کوئی میٹرکس اور ابتدائی حالت کو بازیافت کرنا چاہے گا۔ اس مسئلے کو کم درجے کے میٹرکس کی تکمیل کے مسئلے کے طور پر بھی دیکھا جا سکتا ہے۔ انٹرنیٹ آف تھنگز (آئی او ٹی) لوکلائزیشن لوکلائزیشن (یا گلوبل پوزیشننگ) کا مسئلہ قدرتی طور پر آئی او ٹی سینسر نیٹ ورکس میں ابھرتا ہے۔ مسئلہ یہ ہے کہ جوڑی کے لحاظ سے فاصلے کے مقامی یا جزوی سیٹ سے یوکلڈین اسپیس میں سینسر کے نقشے کو بازیافت کیا جائے۔ اس طرح یہ درجہ دو کے ساتھ میٹرکس کی تکمیل کا مسئلہ ہے اگر سینسر 2-D جہاز میں واقع ہیں اور تین اگر وہ 3-D جگہ میں ہیں۔ سوشل نیٹ ورکس ریکوری زیادہ تر حقیقی دنیا کے سوشل نیٹ ورکس میں کم درجے کے فاصلے کے میٹرکس ہوتے ہیں۔ جب ہم مکمل نیٹ ورک کی پیمائش کرنے کے قابل نہیں ہوتے ہیں، جو کہ پرائیویٹ نوڈس، محدود اسٹوریج یا کمپیوٹ ریسورسز جیسی وجوہات کی وجہ سے ہو سکتا ہے، تو ہمارے پاس فاصلاتی اندراجات کا صرف ایک حصہ معلوم ہوتا ہے۔ مجرمانہ نیٹ ورک اس طرح کے نیٹ ورک کی ایک اچھی مثال ہیں۔ ان غیر مشاہدہ شدہ فاصلے کو بازیافت کرنے کے لیے کم درجے کی میٹرکس تکمیل کا استعمال کیا جا سکتا ہے۔ میٹرکس ریگولرائزیشن نیٹ فلکس پرائز کولیبریٹو فلٹرنگ سسٹم آئیڈینٹیفیکیشن کنویکس آپٹیمائزیشن امپوٹیشن حوالہ جات میٹرکس تھیوری بھی دیکھیں۔