Matrix completion
मैट्रिक्स पूरा करना आंशिक रूप से देखे गए मैट्रिक्स की लापता प्रविष्टियों को भरने का कार्य है, जो सांख्यिकी में डेटा आरोपण करने के बराबर है। डेटासेट की एक विस्तृत श्रृंखला स्वाभाविक रूप से मैट्रिक्स के रूप में व्यवस्थित होती है। एक उदाहरण मूवी-रेटिंग मैट्रिक्स है, जैसा कि नेटफ्लिक्स समस्या में दिखाई देता हैः एक रेटिंग मैट्रिक्स को देखते हुए जिसमें प्रत्येक प्रविष्टि ग्राहक द्वारा फिल्म की रेटिंग का प्रतिनिधित्व करती है, यदि ग्राहक ने फिल्म देखी है और अन्यथा गायब है, तो हम ग्राहकों को आगे क्या देखना है, इस बारे में अच्छी सिफारिशें करने के लिए शेष प्रविष्टियों की भविष्यवाणी करना चाहेंगे। एक अन्य उदाहरण दस्तावेज़-अवधि मैट्रिक्स हैः दस्तावेज़ों के संग्रह में उपयोग किए जाने वाले शब्दों की आवृत्तियों को एक मैट्रिक्स के रूप में दर्शाया जा सकता है, जहां प्रत्येक प्रविष्टि इंगित दस्तावेज़ में संबंधित शब्द के प्रकट होने की संख्या से मेल खाती है। पूर्ण मैट्रिक्स में स्वतंत्रता की डिग्री की संख्या पर किसी भी प्रतिबंध के बिना यह समस्या कम निर्धारित की जाती है क्योंकि छिपी हुई प्रविष्टियों को मनमाने मूल्य दिए जा सकते हैं। इस प्रकार हमें एक अच्छी तरह से प्रस्तुत समस्या बनाने के लिए मैट्रिक्स पर कुछ धारणा की आवश्यकता होती है, जैसे कि यह मान लेना कि इसमें अधिकतम निर्धारक है, सकारात्मक निश्चित है, या निम्न श्रेणी है। उदाहरण के लिए, कोई यह मान सकता है कि मैट्रिक्स में निम्न-श्रेणी संरचना है, और फिर सबसे कम श्रेणी मैट्रिक्स खोजने की कोशिश कर सकता है या, यदि पूर्ण मैट्रिक्स की श्रेणी ज्ञात है, तो श्रेणी का एक मैट्रिक्स जो ज्ञात प्रविष्टियों से मेल खाता है। चित्रण से पता चलता है कि आंशिक रूप से प्रकट रैंक-1 मैट्रिक्स (बाईं ओर) को शून्य-त्रुटि (दाईं ओर) के साथ पूरा किया जा सकता है क्योंकि गायब प्रविष्टियों वाली सभी पंक्तियाँ तीसरी पंक्ति के समान होनी चाहिए। नेटफ्लिक्स समस्या के मामले में रेटिंग मैट्रिक्स कम श्रेणी का होने की उम्मीद है क्योंकि उपयोगकर्ता की प्राथमिकताओं को अक्सर कुछ कारकों द्वारा वर्णित किया जा सकता है, जैसे कि फिल्म शैली और रिलीज का समय। अन्य अनुप्रयोगों में कंप्यूटर दृष्टि शामिल है, जहां छवियों में गायब पिक्सेल को फिर से बनाने की आवश्यकता होती है, आंशिक दूरी की जानकारी से नेटवर्क में सेंसर की वैश्विक स्थिति का पता लगाना और बहुस्तरीय शिक्षा शामिल है। मैट्रिक्स पूरा करने की समस्या सामान्य रूप से एन. पी.-कठिन है, लेकिन अतिरिक्त धारणाओं के तहत कुशल एल्गोरिदम हैं जो उच्च संभावना के साथ सटीक पुनर्निर्माण प्राप्त करते हैं। सांख्यिकीय अधिगम के दृष्टिकोण से, मैट्रिक्स पूर्णता समस्या मैट्रिक्स नियमितीकरण का एक अनुप्रयोग है जो वेक्टर नियमितीकरण का एक सामान्यीकरण है। उदाहरण के लिए, निम्न श्रेणी के मैट्रिक्स पूरा करने की समस्या में कोई भी परमाणु मानक निम्न श्रेणी के मैट्रिक्स पूरा करने के रूप में नियमितीकरण दंड लागू कर सकता है मैट्रिक्स पूरा करने की समस्या के रूपों में से एक सबसे कम श्रेणी के मैट्रिक्स का पता लगाना है जो मैट्रिक्स से मेल खाता है, जिसे हम पुनर्प्राप्त करना चाहते हैं, प्रेक्षित प्रविष्टियों के सेट में सभी प्रविष्टियों के लिए। इस समस्या का गणितीय सूत्रीकरण इस प्रकार हैः कैंडेस और रेक्ट ने साबित किया कि देखी गई प्रविष्टियों के नमूने पर धारणाओं और पर्याप्त रूप से कई नमूने वाली प्रविष्टियों के साथ इस समस्या का उच्च संभावना के साथ एक अद्वितीय समाधान है। एक समतुल्य सूत्रीकरण, यह देखते हुए कि पुनर्प्राप्त किए जाने वाले मैट्रिक्स को श्रेणी के रूप में जाना जाता है, यह हल करने के लिए है कि विश्लेषण को सरल बनाने और यह सुनिश्चित करने के लिए कि समस्या कम निर्धारित नहीं है, देखी गई प्रविष्टियों के नमूने और नमूना प्रविष्टियों की संख्या पर कई धारणाएं अक्सर की जाती हैं। प्रेक्षित प्रविष्टियों का समान नमूनाकरण विश्लेषण को व्यवस्थित करने योग्य बनाने के लिए, अक्सर यह माना जाता है कि प्रेक्षित प्रविष्टियों के समूह और निश्चित कार्डिनलिटी को कार्डिनलिटी की प्रविष्टियों के सभी उपसमुच्चय के संग्रह से यादृच्छिक रूप से समान रूप से नमूना लिया जाता है। विश्लेषण को और सरल बनाने के लिए, यह माना जाता है कि इसका निर्माण बर्नौली सैंपलिंग द्वारा किया गया है, अर्थात। कि प्रत्येक प्रविष्टि संभाव्यता के साथ देखी जाती है। यदि निर्धारित किया जाता है कि वांछित अपेक्षित कार्डिनलिटी कहाँ है, और मैट्रिक्स के आयाम (सामान्यता के नुकसान के बिना) हैं, तो उच्च संभावना के साथ है, इस प्रकार बर्नौली नमूनाकरण एक समान नमूने के लिए एक अच्छा अनुमान है। एक अन्य सरलीकरण यह मान लेना है कि प्रविष्टियों का नमूना स्वतंत्र रूप से और प्रतिस्थापन के साथ लिया जाता है। मान लीजिए कि देखी गई प्रविष्टियों की संख्या पर निचली सीमा मैट्रिक्स (के साथ) द्वारा हम पुनर्प्राप्त करने की कोशिश कर रहे हैं। विशिष्ट रूप से पुनर्निर्माण किए जाने से पहले कितनी प्रविष्टियों को देखा जाना चाहिए, इस पर एक सूचना सैद्धांतिक निचली सीमा है। मैट्रिक्स द्वारा कम या बराबर श्रेणी वाला सेट आयाम के साथ एक बीजगणितीय विविधता है। इस परिणाम का उपयोग करते हुए, कोई यह दिखा सकता है कि कम से कम प्रविष्टियों को मैट्रिक्स पूरा करने के लिए देखा जाना चाहिए ताकि एक अद्वितीय समाधान मिल सके। दूसरा, प्रति पंक्ति और स्तंभ में कम से कम एक प्रेक्षित प्रविष्टि होनी चाहिए। के एकल मूल्य अपघटन द्वारा दिया जाता है। यदि पंक्ति का अवलोकन नहीं किया जाता है, तो, के सही एकवचन सदिश को देखना आसान है, जिसे कुछ मनमाने मूल्य में बदला जा सकता है और फिर भी देखी गई प्रविष्टियों के सेट पर एक मैट्रिक्स मिलान प्राप्त होता है। इसी तरह, यदि कॉलम का अवलोकन नहीं किया गया है, तो इसका बायां एकवचन सदिश मनमाना हो सकता है। यदि हम प्रेक्षित प्रविष्टियों के समूह के बर्नौली नमूने को मानते हैं, तो कूपन संग्राहक प्रभाव का तात्पर्य है कि प्रत्येक पंक्ति और स्तंभ से उच्च संभावना के साथ एक अवलोकन सुनिश्चित करने के लिए के क्रम पर प्रविष्टियों को देखा जाना चाहिए। आवश्यक शर्तों को जोड़कर और यह मानते हुए कि (कई व्यावहारिक अनुप्रयोगों के लिए एक वैध धारणा), मैट्रिक्स पूरा करने की समस्या को कम निर्धारित होने से रोकने के लिए आवश्यक देखी गई प्रविष्टियों की संख्या पर निचली सीमा के क्रम पर है। असंयम असंयम की अवधारणा संपीड़ित संवेदन में उत्पन्न हुई। इसे मैट्रिक्स पूर्णता के संदर्भ में पेश किया गया है ताकि यह सुनिश्चित किया जा सके कि के एकवचन वैक्टर इस अर्थ में बहुत "विरल" नहीं हैं कि प्रत्येक एकवचन वेक्टर के सभी निर्देशांक काफी बड़े परिमाण वाले कुछ निर्देशांकों के बजाय तुलनीय परिमाण के हैं। मानक आधार वैक्टर तब एकवचन वैक्टर के रूप में अवांछनीय होते हैं, और वेक्टर वांछनीय होता है। एक उदाहरण के रूप में क्या गलत हो सकता है यदि एकवचन वैक्टर पर्याप्त रूप से "विरल" हैं, तो एकवचन मूल्य अपघटन के साथ उप मैट्रिक्स पर विचार करें। पुनर्निर्माण से पहले लगभग सभी प्रविष्टियों का नमूना लिया जाना चाहिए। कैंडेस और रेक्ट कॉलम स्पेस के साथ एक मैट्रिक्स की सुसंगतता को परिभाषित करते हैं, एक आयामी उपक्षेत्र के रूप में, जहाँ ऑर्थोगोनल प्रक्षेपण है। एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर एकर शोर के साथ निम्न श्रेणी मैट्रिक्स पूर्णता वास्तविक दुनिया के अनुप्रयोग में, अक्सर कम से कम थोड़ी मात्रा में शोर से दूषित केवल कुछ प्रविष्टियों का अवलोकन किया जाता है। उदाहरण के लिए, नेटफ्लिक्स समस्या में, रेटिंग अनिश्चित हैं। कैंडेस और प्लान ने दिखाया कि परमाणु मानक न्यूनतमकरण द्वारा केवल कुछ शोर वाले नमूनों से बड़े निम्न-श्रेणी के मैट्रिक्स की कई लापता प्रविष्टियों को भरना संभव है। शोर मॉडल मानता है कि हम देखते हैं कि शोर शब्द कहाँ है। ध्यान दें कि शोर या तो यादृच्छिक या निर्धारक हो सकता है। वैकल्पिक रूप से मॉडल को व्यक्त किया जा सकता है कि कुछ लोगों के लिए प्रविष्टियों के साथ एक मैट्रिक्स कहाँ है। अपूर्ण मैट्रिक्स को पुनर्प्राप्त करने के लिए, हम निम्नलिखित अनुकूलन समस्या को हल करने का प्रयास करते हैंः डेटा के अनुरूप सभी मैट्रिक्स में से, न्यूनतम परमाणु मानक के साथ एक का पता लगाएं। कैंडेस और प्लान ने दिखाया है कि यह पुनर्निर्माण सटीक है। उन्होंने साबित कर दिया है कि जब पूर्ण ध्वनिहीन पुनर्प्राप्ति होती है, तो मैट्रिक्स पूर्णता विज़ विज़ पर्टर्बेशन स्थिर होती है। त्रुटि शोर स्तर के समानुपाती होती है। इसलिए, जब शोर का स्तर छोटा होता है, तो त्रुटि छोटी होती है। यहाँ मैट्रिक्स पूर्णता समस्या प्रतिबंधित सममिति गुण (आर. आई. पी.) का पालन नहीं करती है। मैट्रिक्स के लिए, आर. आई. पी. यह मान लेगा कि सैंपलिंग ऑपरेटर पर्याप्त रूप से छोटे और पर्याप्त रूप से छोटे रैंक वाले सभी मैट्रिक्स का पालन करता है। ये विधियाँ विरल संकेत पुनर्प्राप्ति समस्याओं पर भी लागू होती हैं जिनमें आर. आई. पी. नहीं होती है। उच्च श्रेणी मैट्रिक्स पूर्णता सामान्य रूप से उच्च श्रेणी मैट्रिक्स पूर्णता एन. पी.-हार्ड है। हालांकि, कुछ धारणाओं के साथ, कुछ अधूरे उच्च श्रेणी मैट्रिक्स या यहां तक कि पूर्ण श्रेणी मैट्रिक्स को पूरा किया जा सकता है। एरिक्सन, बाल्ज़ानो और नोवाक ने एक मैट्रिक्स को पूरा करने की समस्या पर इस धारणा के साथ विचार किया है कि मैट्रिक्स के स्तंभ कई निम्न-श्रेणी के उप-स्थानों के संघ से संबंधित हैं। चूँकि कॉलम सबस्पेस के एक संघ से संबंधित हैं, इसलिए समस्या को सबस्पेस क्लस्टरिंग समस्या के लापता-डेटा संस्करण के रूप में देखा जा सकता है। मान लीजिए कि एक मैट्रिक्स जिसका (पूर्ण) कॉलम अधिकांश उपस्थानों के संघ में स्थित है, प्रत्येक, और मान लीजिए। एरिक्सन, बाल्ज़ानो और नोवाक ने दिखाया कि हल्की धारणाओं के तहत प्रत्येक स्तंभ को एक अपूर्ण संस्करण से उच्च संभावना के साथ पूरी तरह से पुनर्प्राप्त किया जा सकता है, जब तक कि कम से कम प्रविष्टियों को यादृच्छिक रूप से समान रूप से देखा जाता है, जो सामान्य असंगति स्थितियों, उपस्थानों की ज्यामितीय व्यवस्था और उपस्थानों पर स्तंभों के वितरण पर निर्भर करता है। एल्गोरिदम में कई चरण शामिल हैंः (1) स्थानीय पड़ोस; (2) स्थानीय उप-स्थान; (3) उप-स्थान परिष्करण; (4) पूर्ण मैट्रिक्स पूर्णता। इस विधि को इंटरनेट दूरी मैट्रिक्स पूर्णता और टोपोलॉजी पहचान पर लागू किया जा सकता है। लो-रैंक मैट्रिक्स कम्प्लीशन के लिए एल्गोरिदम विभिन्न मैट्रिक्स कम्प्लीशन एल्गोरिदम प्रस्तावित किए गए हैं। इनमें उत्तल विश्राम-आधारित एल्गोरिदम, प्रवणता-आधारित एल्गोरिदम और वैकल्पिक न्यूनतम-आधारित एल्गोरिदम शामिल हैं। कन्वेक्स रिलैक्सेशन रैंक मिनिमाइजेशन की समस्या एन. पी.-हार्ड है। कैंडेस और रेक्ट द्वारा प्रस्तावित एक दृष्टिकोण, समस्या की उत्तल छूट बनाना और परमाणु मानक (जो के एकवचन मूल्यों का योग देता है) को कम करना है (जो के गैर शून्य एकवचन मूल्यों की संख्या की गणना करता है)। यह वैक्टर के लिए L0-मानक के बजाय L1-मानक को कम करने के लिए समान है। उत्तल विश्राम को सेमीडिफाइनाइट प्रोग्रामिंग (एस. डी. पी.) का उपयोग करके यह देखते हुए हल किया जा सकता है कि अनुकूलन समस्या उत्तल विश्राम को हल करने के लिए एस. डी. पी. का उपयोग करने की जटिलता है। एस. डी. पी. टी. 3 जैसे अत्याधुनिक समाधानकर्ता केवल 100 गुणा 100 तक के आकार के मैट्रिक्स को संभाल सकते हैं एक वैकल्पिक प्रथम क्रम विधि जो उत्तल छूट को लगभग हल करती है, काई, कैंडेस और शेन द्वारा शुरू किया गया एकल मूल्य सीमा-धारक एल्गोरिदम है। कैंडेस और रेक्ट ने बनाच रिक्त स्थान पर यादृच्छिक चर के अध्ययन का उपयोग करते हुए दिखाया कि यदि देखी गई प्रविष्टियों की संख्या के क्रम पर है (सामान्यता के नुकसान के बिना मान लें), तो श्रेणी न्यूनतमकरण समस्या का एक अनूठा समाधान है जो कुछ स्थिरांक की संभावना के साथ इसके उत्तल विश्राम का समाधान भी होता है। यदि की श्रेणी छोटी () है, तो टिप्पणियों के समूह का आकार के क्रम में कम हो जाता है। ये परिणाम इष्टतम के करीब हैं, क्योंकि मैट्रिक्स पूरा करने की समस्या को कम निर्धारित नहीं करने के लिए प्रविष्टियों की न्यूनतम संख्या का अवलोकन किया जाना चाहिए। कैंडेस और ताओ ने इस परिणाम में सुधार किया है। वे धारणाओं को मजबूत करके केवल बहुपदगणितीय कारकों द्वारा इष्टतम सीमाओं से भिन्न सीमाओं को प्राप्त करते हैं। इनकॉहिरेंस प्रॉपर्टी के बजाय, वे पैरामीटर के साथ मजबूत इनकॉहिरेंस प्रॉपर्टी मानते हैं। यह गुण बताता है किः के लिए और के लिए की प्रविष्टियाँ परिमाण में सहज ज्ञान से बंधी होती हैं, एक मैट्रिक्स की मजबूत असंगतता यह दावा करती है कि मानक आधार वैक्टरों के ऑर्थोगोनल अनुमानों में ऐसे परिमाण होते हैं जिनकी उच्च संभावना होती है यदि एकवचन वैक्टर यादृच्छिक रूप से वितरित किए गए थे। कैंडेस और ताओ ने पाया कि कब है और देखी गई प्रविष्टियों की संख्या के क्रम पर है, रैंक न्यूनतमकरण समस्या का एक अनूठा समाधान है जो कुछ स्थिरांक की संभावना के साथ इसके उत्तल विश्राम का समाधान भी होता है। मनमाने ढंग से, इस दावे के लिए पर्याप्त देखी गई प्रविष्टियों की संख्या सही है एक अन्य उत्तल विश्राम दृष्टिकोण एक श्रेणी बाधा के तहत फ्रोबेनियस वर्ग मानक को कम करना है। यह हल करने के बराबर है एक ऑर्थोगोनल प्रोजेक्शन मैट्रिक्स (अर्थ) को पेश करके और इस समस्या के उत्तल छूट को मॉडल करने के लिए, हम निम्नलिखित अर्ध-परिमित कार्यक्रम प्राप्त करते हैं यदि Y इस छूट में एक प्रोजेक्शन मैट्रिक्स है (यानी, द्विआधारी आइगेनवैल्यू है), तो छूट तंग है। अन्यथा, यह समग्र उद्देश्य पर एक वैध निचली सीमा देता है। इसके अलावा, इसे लालच में Y के आइगेनवैल्यूज को गोल करके (थोड़ा) बड़े उद्देश्य के साथ एक व्यवहार्य समाधान में परिवर्तित किया जा सकता है। उल्लेखनीय रूप से, इस उत्तल छूट को किसी भी एस. डी. पी. को हल किए बिना एक्स और वाई पर बारी-बारी से न्यूनतम करके हल किया जा सकता है, और इस प्रकार यह एस. डी. पी. टी. 3 या मोसेक जैसे अत्याधुनिक एस. डी. पी. समाधानकों की विशिष्ट संख्यात्मक सीमाओं से परे है। यह दृष्टिकोण एक अधिक सामान्य सुधार तकनीक का एक विशेष मामला है, जिसे ट्रेस-मैट्रिक्स-कन्वेक्स उद्देश्य के साथ किसी भी निम्न-श्रेणी की समस्या पर एक वैध निचली सीमा प्राप्त करने के लिए लागू किया जा सकता है। ग्रेडिएंट डिसेंट केशवन, मोंटानारी और ओह मैट्रिक्स पूर्णता के एक प्रकार पर विचार करते हैं जहां मैट्रिक्स द्वारा रैंक, जिसे पुनर्प्राप्त किया जाना है, के रूप में जाना जाता है। वे प्रविष्टियों का बर्नौली नमूनाकरण, स्थिर पहलू अनुपात, प्रविष्टियों का सीमित परिमाण (ऊपरी सीमा होने दें), और स्थिर स्थिति संख्या (जहां और क्रमशः सबसे बड़े और सबसे छोटे एकवचन मान हैं) मानते हैं। इसके अलावा, वे मानते हैं कि दो असंगति स्थितियां संतुष्ट हैं और कहाँ और स्थिर हैं। मान लीजिए कि एक मैट्रिक्स है जो देखी गई प्रविष्टियों के सेट से मेल खाता है और कहीं और 0 है। फिर वे निम्नलिखित एल्गोरिथ्म का प्रस्ताव करते हैंः कॉलम में प्रविष्टियों को 0 पर सेट करने की तुलना में बड़ी डिग्री वाले कॉलम से सभी टिप्पणियों को हटाकर ट्रिम करें। इसी तरह उससे बड़ी डिग्री वाली पंक्तियों से सभी टिप्पणियों को हटा दें। अपने पहले प्रमुख घटकों पर परियोजना। परिणामी मैट्रिक्स को कॉल करें। लाइन सर्च के साथ ग्रेडिएंट डिसेंट द्वारा कुछ नियमितकरण फ़ंक्शन को हल करें। कहाँ से आरंभ करें। कुछ फ़ंक्शन के रूप में सेट करें जो ग्रेडिएंट डिसेंट के दौरान असंगत रहने के लिए मजबूर करता है यदि और असंगत हैं। मैट्रिक्स को वापस करें। एल्गोरिथम के चरण 1 और 2 उच्च संभावना के साथ सही मैट्रिक्स (जैसा कि रूट मीन स्क्वायर एरर (आर. एम. एस. ई.) द्वारा मापा जाता है) के बहुत करीब एक मैट्रिक्स प्रदान करते हैं। विशेष रूप से, संभाव्यता के साथ, कुछ स्थिरांक के लिए। फ्रोबेनियस मानक को दर्शाता है। ध्यान दें कि इस परिणाम को बनाए रखने के लिए मान्यताओं के पूर्ण समूह की आवश्यकता नहीं है। उदाहरण के लिए, असंगति की स्थिति केवल सटीक पुनर्निर्माण में खेल में आती है। अंत में, हालांकि छंटाई प्रति सहज प्रतीत हो सकती है क्योंकि इसमें जानकारी को बाहर फेंकना शामिल है, यह सुनिश्चित करता है कि इसके पहले प्रमुख घटकों पर प्रक्षेपित करने से देखी गई प्रविष्टियों की तुलना में अंतर्निहित मैट्रिक्स के बारे में अधिक जानकारी मिलती है। चरण 3 में, उम्मीदवार मैट्रिक्स के स्थान को यह देखकर कम किया जा सकता है कि आंतरिक न्यूनतम समस्या का समाधान कहाँ के लिए है और मैट्रिक्स द्वारा ऑर्थोनॉर्मल हैं। फिर दो ग्रासमैन मैनिफोल्ड्स के क्रॉस उत्पाद पर ग्रेडिएंट डिसेंट किया जा सकता है। यदि और प्रेक्षित प्रविष्टि सेट के क्रम में है, तो चरण 3 द्वारा वापस किया गया मैट्रिक्स बिल्कुल है। फिर एल्गोरिथ्म क्रम इष्टतम है, क्योंकि हम जानते हैं कि मैट्रिक्स पूरा करने की समस्या को कम निर्धारित नहीं करने के लिए प्रविष्टियों की संख्या के क्रम में होनी चाहिए। अल्टरनेटिंग लीस्ट स्क्वेयर्स मिनिमाइजेशन अल्टरनेटिंग मिनिमाइजेशन निम्न श्रेणी के मैट्रिक्स को खोजने के लिए एक व्यापक रूप से लागू और अनुभवजन्य रूप से सफल दृष्टिकोण का प्रतिनिधित्व करता है जो दिए गए डेटा के लिए सबसे उपयुक्त है। उदाहरण के लिए, निम्न श्रेणी के मैट्रिक्स को पूरा करने की समस्या के लिए, इस विधि को सबसे सटीक और कुशल माना जाता है, और यह नेटफ्लिक्स समस्या में विजेता प्रविष्टि का एक प्रमुख घटक है। वैकल्पिक न्यूनतमकरण दृष्टिकोण में, निम्न-श्रेणी लक्ष्य मैट्रिक्स को द्वि-रेखीय रूप में लिखा जाता हैः एल्गोरिथ्म फिर सर्वश्रेष्ठ और सर्वश्रेष्ठ को खोजने के बीच बारी-बारी से आता है। जबकि समग्र समस्या गैर-उत्तल है, प्रत्येक उप-समस्या आमतौर पर उत्तल होती है और इसे कुशलता से हल किया जा सकता है। जैन, नेत्रपल्ली और संघवी ने मैट्रिक्स पूर्णता और मैट्रिक्स संवेदन दोनों के लिए वैकल्पिक न्यूनतमकरण के प्रदर्शन के लिए पहली गारंटी दी है। वैकल्पिक न्यूनतमकरण एल्गोरिदम को निम्नलिखित गैर-उत्तल समस्या को हल करने के लिए एक अनुमानित तरीके के रूप में देखा जा सकता हैः जैन, नेत्रपल्ली और संघवी द्वारा प्रस्तावित ऑल्टमिनकंप्लीट एल्गोरिदम को यहां सूचीबद्ध किया गया हैः इनपुटः प्रेक्षित समुच्चय, विभाजन को उपसमुच्चय में मान देता है जिसमें प्रत्येक तत्व का संबंध समान संभावना (प्रतिस्थापन के साथ नमूना) के साथ होता है, यानी, क्लिपिंग के शीर्ष-बाएं एकल वैक्टरः उन सभी तत्वों को सेट करें जिनका परिमाण शून्य से अधिक है और रिटर्न के लिए टू एंड के स्तंभों को ऑर्थोनॉर्मलाइज़ करें उन्होंने दिखाया कि एक असंगत मैट्रिक्स की यादृच्छिक प्रविष्टियों को देखकर, ऑल्टमिनकंप्लीट एल्गोरिदम चरणों में ठीक हो सकता है। नमूना जटिलता () के संदर्भ में, सैद्धांतिक रूप से, वैकल्पिक न्यूनतमकरण के लिए कन्वेक्स रिलैक्सेशन से बड़े की आवश्यकता हो सकती है। हालाँकि अनुभवजन्य रूप से ऐसा नहीं लगता है जिसका अर्थ है कि नमूना जटिलता की सीमा को और कड़ा किया जा सकता है। समय की जटिलता के संदर्भ में, उन्होंने दिखाया कि ऑल्टमिनकंप्लीट को समय की आवश्यकता है। यह ध्यान देने योग्य है कि, हालांकि उत्तल विश्राम आधारित विधियों में कठोर विश्लेषण होता है, वैकल्पिक न्यूनतमकरण आधारित एल्गोरिदम व्यवहार में अधिक सफल होते हैं। अनुप्रयोग मैट्रिक्स पूरा करने के कई अनुप्रयोगों को कैंडेस और प्लान द्वारा संक्षेप में प्रस्तुत किया गया हैः सहयोगात्मक फ़िल्टरिंग सहयोगात्मक फ़िल्टरिंग कई उपयोगकर्ताओं से स्वाद की जानकारी एकत्र करके उपयोगकर्ता के हितों के बारे में स्वचालित भविष्यवाणियां करने का कार्य है। ऐप्पल, अमेज़ॅन, बार्न्स एंड नोबल और नेटफ्लिक्स जैसी कंपनियां आंशिक ज्ञान से अपनी उपयोगकर्ता प्राथमिकताओं का अनुमान लगाने की कोशिश कर रही हैं। इस तरह की मैट्रिक्स पूर्णता समस्या में, अज्ञात पूर्ण मैट्रिक्स को अक्सर निम्न श्रेणी माना जाता है क्योंकि केवल कुछ कारक आमतौर पर किसी व्यक्ति के स्वाद या वरीयता में योगदान करते हैं। प्रणाली पहचान नियंत्रण में, कोई भी एक असतत-समय रैखिक समय-अपरिवर्तनीय अवस्था-स्थान मॉडल को इनपुट और आउटपुट के अनुक्रम में फिट करना चाहेगा। वेक्टर समय पर प्रणाली की स्थिति है और प्रणाली मॉडल का क्रम है। इनपुट/आउटपुट जोड़ी से, कोई मैट्रिक्स और प्रारंभिक स्थिति को पुनर्प्राप्त करना चाहेगा। इस समस्या को निम्न श्रेणी की मैट्रिक्स पूर्णता समस्या के रूप में भी देखा जा सकता है। इंटरनेट ऑफ थिंग्स (आई. ओ. टी.) स्थानीयकरण आई. ओ. टी. संवेदक नेटवर्क में स्थानीयकरण (या वैश्विक स्थिति) समस्या स्वाभाविक रूप से उभरती है। समस्या यह है कि यूक्लिडियन स्थान में संवेदक मानचित्र को जोड़ीदार दूरी के स्थानीय या आंशिक सेट से पुनर्प्राप्त किया जाए। इस प्रकार यह श्रेणी दो के साथ एक मैट्रिक्स पूर्णता समस्या है यदि संवेदक 2-डी तल में स्थित हैं और तीन यदि वे 3-डी स्थान में हैं। अधिकांश वास्तविक दुनिया के सामाजिक नेटवर्कों में कम श्रेणी की दूरी के मैट्रिक्स हैं। जब हम पूर्ण नेटवर्क को मापने में सक्षम नहीं होते हैं, जो निजी नोड्स, सीमित भंडारण या गणना संसाधनों जैसे कारणों से हो सकता है, तो हमारे पास केवल ज्ञात दूरी प्रविष्टियों का एक अंश होता है। आपराधिक नेटवर्क ऐसे नेटवर्क का एक अच्छा उदाहरण है। निम्न-श्रेणी मैट्रिक्स पूर्णता का उपयोग इन अनदेखी दूरी को पुनर्प्राप्त करने के लिए किया जा सकता है। मैट्रिक्स नियमितीकरण नेटफ्लिक्स पुरस्कार सहयोगात्मक फ़िल्टरिंग प्रणाली पहचान कन्वेक्स अनुकूलन आरोप संदर्भ मैट्रिक्स सिद्धांत भी देखें।