मैट्रिक्स पूर्णता

रैंक-1 के साथ आंशिक रूप से प्रकट 5 बाय 5 आव्यूह का आव्यूह समापन। बाएँ: अपूर्ण आव्यूह का अवलोकन किया गया; दाएं: आव्यूह पूर्णता परिणाम.

आव्यूह पूर्णता आंशिक रूप से देखे गए आव्यूह की लुप्त प्रविष्टियों को भरने का कार्य है, जो आंकड़ों में डेटा प्रतिरूपण (सांख्यिकी) करने के समान है। डेटासमुच्चय की विस्तृत श्रृंखला स्वाभाविक रूप से आव्यूह रूप में व्यवस्थित होती है। उदाहरण मूवी-रेटिंग आव्यूह है, जैसा कि नेटफ्लिक्स प्रॉब्लम में दिखाई देता है: रेटिंग आव्यूह दिया जाता है जिसमें प्रत्येक प्रविष्टि $(i,j)$ ग्राहक $i$ द्वारा मूवी $j$ की रेटिंग का प्रतिनिधित्व करती है, यदि ग्राहक $i$ मूवी $j$ ने देखा है जो कि विलुप्त है, हम ग्राहकों को आगे क्या देखना है इसके बारे में अच्छी सिफारिशें करने के लिए शेष प्रविष्टियों की भविष्यवाणी करना चाहेंगे। अन्य उदाहरण डाक्यूमेंट्स -शब्द आव्यूह है: डाक्यूमेंट्स के संग्रह में उपयोग किए गए शब्दों की आवृत्तियों को आव्यूह के रूप में दर्शाया जा सकता है, जहां प्रत्येक प्रविष्टि संकेतित डाक्यूमेंट्स में संबंधित शब्द के प्रकट होने की संख्या से मेल खाती है।

पूर्ण आव्यूह में स्वतंत्रता की डिग्री की संख्या पर किसी भी प्रतिबंध के बिना यह समस्या अनिर्धारित प्रणाली है क्योंकि छिपी हुई प्रविष्टियों को इच्छानुसार मान दिए जा सकते हैं। इस प्रकार हमें अच्छी तरह से प्रस्तुत समस्या बनाने के लिए आव्यूह पर कुछ धारणा की आवश्यकता होती है, जैसे कि यह मान लेना कि इसमें अधिकतम निर्धारक है, या तो धनात्मक निश्चित है, या तो निम्न-रैंक है।

उदाहरण के लिए, कोई यह मान सकता है कि आव्यूह में निम्न-रैंक संरचना है, और फिर निम्नतम रैंक (रैखिक बीजगणित) आव्यूह खोजने की प्रयास करें या, यदि पूर्ण आव्यूह की रैंक ज्ञात है, तो रैंक का आव्यूह (रैखिक बीजगणित) $r$ है जो ज्ञात प्रविष्टियों से मेल खाता है। चित्रण से पता चलता है कि आंशिक रूप से प्रकट रैंक -1 आव्यूह (बाईं ओर) को शून्य-त्रुटि (दाहिनी ओर) के साथ पूरा किया जा सकता है क्योंकि लापता प्रविष्टियों वाली सभी पंक्तियाँ तीसरी पंक्ति के समान होनी चाहिए। नेटफ्लिक्स समस्या के स्तिथियाँ में रेटिंग आव्यूह निम्न-रैंक होने की अपेक्षित है क्योंकि उपयोगकर्ता की प्राथमिकताओं को अधिकांशतः कुछ कारकों द्वारा वर्णित किया जा सकता है, जैसे कि फिल्म की शैली और रिलीज का समय अन्य अनुप्रयोगों में कंप्यूटर विज़न सम्मिलित है, जहां छवियों में विलुप्त पिक्सेल को फिर से बनाने की आवश्यकता होती है, आंशिक दूरी की जानकारी से नेटवर्क में सेंसर की वैश्विक स्थिति का पता लगाना और मल्टीक्लास वर्गीकरण आव्यूह पूर्णता समस्या सामान्य रूप से एनपी कठिन है, लेकिन अतिरिक्त मान्यताओं के तहत कुशल एल्गोरिदम हैं जो उच्च संभावना के साथ स्पष्ट पुनर्निर्माण प्राप्त करते हैं।

सांख्यिकीय सीखने के दृष्टिकोण से, आव्यूह पूर्णता समस्या आव्यूह नियमितीकरण का अनुप्रयोग है जो सदिश नियमितीकरण (गणित) का सामान्यीकरण है। उदाहरण के लिए, निम्न-रैंक आव्यूह पूर्णता समस्या में कोई परमाणु मानदंड $R(X)=\lambda \|X\|_{*}$ का रूप लेते हुए नियमितीकरण जुर्माना प्रयुक्त कर सकता है

निम्न रैंक आव्यूह पूर्णता

आव्यूह पूर्णता समस्या के प्रकारों में से निम्नतम रैंक (रैखिक बीजगणित) आव्यूह $X$ को ढूंढना है जो आव्यूह $M$ से मेल खाता है, जिसे हम समुच्चय $E$ में सभी देखी गई प्रविष्टियों के लिए पुनर्प्राप्त करना चाहते हैं इस समस्या का गणितीय सूत्रीकरण इस प्रकार है:

${\begin{aligned}&{\underset {X}{\text{min}}}&{\text{rank}}(X)\\&{\text{subject to}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}$

कैंडेस और रेख्त सिद्ध हुआ कि प्रेक्षित प्रविष्टियों के नमूने और पर्याप्त रूप से अनेक नमूना प्रविष्टियों पर धारणाओं के साथ इस समस्या का उच्च संभावना वाला अनूठा समाधान है।

ऐसा समतुल्य सूत्रीकरण, यह देखते हुए कि आव्यूह $M$ पुनर्प्राप्त किया जाना रैंक (रैखिक बीजगणित) $r$ के रूप में जाना जाता है, जहाँ $X$ के लिए हल करना है $X_{ij}=M_{ij}\;\;\forall i,j\in E$

धारणाएँ

विश्लेषण को सरल बनाने और यह सुनिश्चित करने के लिए कि समस्या कम निर्धारित नहीं है, अवलोकन की गई प्रविष्टियों के नमूने और नमूना प्रविष्टियों की संख्या पर अनेक धारणाएँ अधिकांशतः बनाई जाती हैं।

प्रेक्षित प्रविष्टियों का एकसमान नमूना

विश्लेषण को सुव्यवस्थित बनाने के लिए, अधिकांशतः यह मान लिया जाता है कि समुच्चय $E$ देखी गई प्रविष्टियों और निश्चित प्रमुखता को कार्डिनैलिटी $|E|$ की प्रविष्टियों के सभी सबसमुच्चय के संग्रह से यादृच्छिक रूप से समान रूप से नमूना लिया जाता है . विश्लेषण को और सरल बनाने के लिए, इसके अतिरिक्त यह मान लिया गया है कि $E$ बर्नौली नमूनाकरण द्वारा निर्मित किया गया है, अर्थात प्रत्येक प्रविष्टि को संभाव्यता $p$ के साथ देखा जाता है. यदि $p$ को ${\frac {N}{mn}}$ इसके लिए समुच्चय है जहाँ $N$, $E$ की वांछित अपेक्षित कार्डिनैलिटी है, और $m,\;n$ आव्यूह के आयाम हैं (मान लीजिए $m<n$ व्यापकता के नुकसान के बिना), $|E|$ उच्च संभावना के साथ $N$ के $O(n\log n)$ के अंदर है, इस प्रकार बर्नौली नमूनाकरण एकसमान नमूने के लिए अच्छा सन्निकटन है। और सरलीकरण यह मान लेना है कि प्रविष्टियाँ स्वतंत्र रूप से और प्रतिस्थापन के साथ नमूनाकृत की जाती हैं।

प्रेक्षित प्रविष्टियों की संख्या की निचली सीमा

मान लीजिये $m$ द्वारा $n$ आव्यूह $M$ (साथ $m<n$) हम रैंक (रैखिक बीजगणित) को पुनर्प्राप्त करने का प्रयास कर रहे हैं $r$. पहले कितनी प्रविष्टियाँ देखी जानी चाहिए, इस पर सूचना सैद्धांतिक निचली सीमा है $M$ विशिष्ट रूप से पुनर्निर्माण किया जा सकता है। के समुच्चय $m$ द्वारा $n$ इससे कम या उसके समान रैंक वाले आव्यूह $r$ में बीजगणितीय किस्म है ${\mathbb {C} }^{m\times n}$आयाम के साथ $(n+m)r-r^{2}$. इस परिणाम का उपयोग करते हुए, कोई इसे कम से कम दिखा तो सकता है $4nr-4r^{2}$ आव्यूह पूर्णता के लिए प्रविष्टियों का अवलोकन किया जाना चाहिए ${\mathbb {C} }^{n\times n}$ अनोखा समाधान पाने के लिए कब $r\leq n/2$ .

दूसरे, प्रति पंक्ति और स्तंभ में कम से कम प्रेक्षित प्रविष्टि होनी चाहिए $M$. का एकवचन मूल्य अपघटन $M$ द्वारा दिया गया है $U\Sigma V^{\dagger }$. यदि पंक्ति $i$ अप्राप्य है, इसे देखना आसान है $i^{\text{th}}$ का दायां एकवचन सदिश $M$, $v_{i}$, कुछ मनमाने मूल्य में बदला जा सकता है और फिर भी आव्यूह मिलान प्राप्त हो सकता है $M$ प्रेक्षित प्रविष्टियों के समुच्चय पर। इसी प्रकार, यदि कॉलम $j$ अवलोकित है, $j^{\text{th}}$ का बायां एकवचन सदिश $M$, $u_{i}$ मनमाना हो सकता है. यदि हम प्रेक्षित प्रविष्टियों के समुच्चय का बर्नौली नमूनाकरण मानते हैं, तो कूपन कलेक्टर की समस्या का तात्पर्य है कि प्रविष्टियाँ के क्रम पर $O(n\log n)$ यह सुनिश्चित करने के लिए अवश्य देखा जाना चाहिए कि उच्च संभावना के साथ प्रत्येक पंक्ति और स्तंभ से अवलोकन हो।

आवश्यक शर्तों को संयोजित करना और यह मान लेना $r\ll m,n$ (अनेक व्यावहारिक अनुप्रयोगों के लिए वैध धारणा), आव्यूह पूर्णता की समस्या को कम निर्धारित होने से रोकने के लिए आवश्यक देखी गई प्रविष्टियों की संख्या की निचली सीमा के क्रम पर है $nr\log n$.

असंगति

संपीडित संवेदन में असंगति की अवधारणा उत्पन्न हुई। इसे एकवचन वैक्टर सुनिश्चित करने के लिए आव्यूह पूर्णता के संदर्भ में पेश किया गया है $M$ इस अर्थ में बहुत विरल नहीं हैं कि प्रत्येक एकवचन सदिश के सभी निर्देशांक तुलनीय परिमाण के होते हैं, न कि केवल कुछ निर्देशांक जिनमें काफी बड़े परिमाण होते हैं। मानक आधार वैक्टर तब एकवचन वैक्टर और सदिश के रूप में अवांछनीय होते हैं ${\frac {1}{\sqrt {n}}}{\begin{bmatrix}1\\1\\\vdots \\1\end{bmatrix}}$ में $\mathbb {R} ^{n}$ ये इच्छित है। यदि एकवचन सदिश पर्याप्त रूप से विरल हों तो क्या गलत हो सकता है, इसके उदाहरण के रूप में, इस पर विचार करें $m$ द्वारा $n$ आव्यूह ${\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}$ एकल मूल्य अपघटन के साथ $I_{m}{\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}I_{n}$. की लगभग सभी प्रविष्टियाँ $M$ इसका पुनर्निर्माण करने से पहले इसका नमूना लिया जाना चाहिए।

कैंडेस और रेख्तआव्यूह की सुसंगतता को परिभाषित करें $U$ स्तंभ स्थान के साथ ए $r-$का आयामी उपस्थान $\mathbb {R} ^{n}$ जैसा $\mu (U)={\frac {n}{r}}\max _{i<n}\|P_{U}e_{i}\|^{2}$, कहाँ $P_{U}$ ओर्थोगोनल प्रोजेक्शन (गणित) है $U$. असंगतता तब दावा करती है कि एकवचन मूल्य अपघटन दिया गया है $U\Sigma V^{\dagger }$ की $m$ द्वारा $n$ आव्यूह $M$,

1. $\mu (U),\;\mu (V)\leq \mu _{0}$
2. की प्रविष्टियाँ $\sum _{k}u_{k}v_{k}^{\dagger }$ परिमाण ऊपरी सीमा से घिरा है $\mu _{1}{\sqrt {\frac {r}{mn}}}$

कुछ के लिए $\mu _{0},\;\mu _{1}$.

शोर के साथ निम्न रैंक आव्यूह पूर्णता

वास्तविक दुनिया के अनुप्रयोग में, अधिकांशतः केवल कुछ ही प्रविष्टियाँ देखी जाती हैं जो कम से कम थोड़ी मात्रा में शोर से दूषित हो जाती हैं। उदाहरण के लिए, नेटफ्लिक्स समस्या में, रेटिंग अनिश्चित हैं। कैंडेस और योजना दिखाया गया कि परमाणु मानक न्यूनतमकरण द्वारा केवल कुछ शोर वाले नमूनों से बड़े निम्न-रैंक आव्यूह की अनेक लापता प्रविष्टियों को भरना संभव है। शोर मॉडल मानता है कि हम निरीक्षण करते हैं

$Y_{ij}=M_{ij}+Z_{ij},(i,j)\in \Omega ,$ कहाँ ${Z_{ij}:(i,j)\in \Omega }$ शोर शब्द है. ध्यान दें कि शोर या तो स्टोकेस्टिक या नियतात्मक हो सकता है। वैकल्पिक रूप से मॉडल को इस प्रकार व्यक्त किया जा सकता है

$P_{\Omega }(Y)=P_{\Omega }(M)+P_{\Omega }(Z),$ कहाँ $Z$ $n\times n$ प्रविष्टियों के साथ आव्यूह $Z_{ij}$ के लिए $(i,j)\in \Omega$ ये मानते हुए $\|P_{\Omega }(Z)\|_{F}\leq \delta$ कुछ के लिए $\delta >0$ अपूर्ण आव्यूह को पुनर्प्राप्त करने के लिए, हम निम्नलिखित अनुकूलन समस्या को हल करने का प्रयास करते हैं:

${\begin{aligned}&{\underset {X}{\text{min}}}&\|X\|_{*}\\&{\text{subject to}}&\|P_{\Omega }(X-Y)\|_{F}\leq \delta \\\end{aligned}}$ डेटा के अनुरूप सभी आव्यूह में से, न्यूनतम परमाणु मानदंड वाला ढूंढें। कैंडेस और योजना दिखाया है कि यह पुनर्निर्माण स्पष्ट है। उन्होंने यह सिद्ध कर दिया है कि जब पूर्ण ध्वनि रहित पुनर्प्राप्ति होती है, तो गड़बड़ी की तुलना में आव्यूह पूर्णता स्थिर होती है। त्रुटि शोर स्तर के समानुपाती होती है $\delta$. इसलिए, जब शोर का स्तर छोटा होता है, तो त्रुटि छोटी होती है। यहां आव्यूह पूर्णता समस्या प्रतिबंधित आइसोमेट्री प्रॉपर्टी (आरआईपी) का पालन नहीं करती है। मैट्रिसेस के लिए, आरआईपी यह मान लेगा कि सैंपलिंग ऑपरेटर उसका पालन करता है

$(1-\delta )\|X\|_{F}^{2}\leq {\frac {1}{p}}\|P_{\Omega }(X)\|_{F}^{2}\leq (1+\delta )\|X\|_{F}^{2}$ सभी आव्यूह के लिए $X$ पर्याप्त रूप से छोटी रैंक के साथ और $\delta <1$ पर्याप्त रूप से छोटा. विधियाँ विरल सिग्नल पुनर्प्राप्ति समस्याओं पर भी प्रयुक्त होती हैं जिनमें RIP पकड़ में नहीं आता है।

उच्च रैंक आव्यूह पूर्णता

सामान्य तौर पर उच्च रैंक आव्यूह पूर्णता एनपी हार्ड है। हालाँकि, कुछ मान्यताओं के साथ, कुछ अधूरे उच्च रैंक आव्यूह या यहाँ तक कि पूर्ण रैंक आव्यूह को भी पूरा किया जा सकता है।

एरिक्सन, बाल्ज़ानो और नोवाक आव्यूह को पूरा करने की समस्या पर इस धारणा के साथ विचार किया है कि आव्यूह के कॉलम अनेक निम्न-रैंक उप-स्थानों के संघ से संबंधित हैं। चूंकि कॉलम उप-स्थानों के संघ से संबंधित हैं, इसलिए समस्या को क्लस्टरिंग उच्च-आयामी डेटा समस्या के लापता-डेटा संस्करण के रूप में देखा जा सकता है। होने देना $X$ सेम $n\times N$ आव्यूह जिसके (पूर्ण) कॉलम अधिक से अधिक के संघ में स्थित हैं $k$ उप-स्थान, प्रत्येक $rank\leq r<n$, और मान लीजिये $N\gg kn$. एरिक्सन, बाल्ज़ानो और नोवाक दिखाया गया है कि हल्की धारणाओं के तहत प्रत्येक कॉलम $X$ कम से कम लंबे समय तक अपूर्ण संस्करण से उच्च संभावना के साथ पूरी तरह से पुनर्प्राप्त किया जा सकता है $CrN\log ^{2}(n)$ की प्रविष्टियाँ $X$ यादृच्छिक रूप से समान रूप से देखे जाते हैं $C>1$ सामान्य असंगति स्थितियों, उप-स्थानों की ज्यामितीय व्यवस्था और उप-स्थानों पर स्तंभों के वितरण के आधार पर स्थिरांक।

एल्गोरिदम में अनेक चरण सम्मिलित हैं: (1) स्थानीय पड़ोस; (2) स्थानीय उपस्थान; (3) उपस्थान परिशोधन; (4) पूर्ण आव्यूह पूर्णता। इस पद्धति को इंटरनेट दूरी आव्यूह पूर्णता और टोपोलॉजी पहचान पर प्रयुक्त किया जा सकता है।

निम्न-रैंक आव्यूह समापन के लिए एल्गोरिदम

विभिन्न आव्यूह पूर्णता एल्गोरिदम प्रस्तावित किए गए हैं।इनमें उत्तल विश्राम-आधारित एल्गोरिदम सम्मिलित है,ग्रेडिएंट-आधारित एल्गोरिदम,और वैकल्पिक न्यूनतमकरण-आधारित एल्गोरिदम।

उत्तल विश्राम

रैंक न्यूनीकरण समस्या एनपी-हार्ड है। कैंडेस और रेचट द्वारा प्रस्तावित दृष्टिकोण, समस्या का उत्तल फ़ंक्शन विश्राम बनाना और परमाणु मानदंड (गणित) को कम करना है $\|M\|_{*}$ (जो एकवचन मानों का योग देता है $M$) के अतिरिक्त ${\text{rank}}(M)$ (जो गैर शून्य एकवचन मानों की संख्या की गणना करता है $M$).यह वैक्टर के लिए L0-मानदंड (गणित) के अतिरिक्त L1-मानदंड (गणित) को न्यूनतम करने के समान है। उत्तल फ़ंक्शन विश्राम को अर्धनिश्चित प्रोग्रामिंग (एसडीपी) का उपयोग करके हल किया जा सकता है, यह देखते हुए कि अनुकूलन समस्या इसके समान है

${\begin{aligned}&{\underset {W_{1},W_{2}}{\text{min}}}&&{\text{trace}}(W_{1})+{\text{trace}}(W_{2})\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\begin{bmatrix}W_{1}&X\\X^{T}&W_{2}\end{bmatrix}}\succeq 0\end{aligned}}$ उत्तल विश्राम को हल करने के लिए अर्धनिश्चित प्रोग्रामिंग का उपयोग करने की जटिलता है $O({\text{max}}(m,n)^{4})$. SDPT3 जैसे अत्याधुनिक सॉल्वर केवल 100 गुणा 100 तक के आकार के आव्यूह को संभाल सकते हैं वैकल्पिक प्रथम क्रम विधि जो उत्तल विश्राम को लगभग हल करती है वह काई, कैंडेस और शेन द्वारा प्रस्तुत सिंगुलर वैल्यू थ्रेशोल्डिंग एल्गोरिदम है।

कैंडेस और रेख्त बैनाच स्थानों पर यादृच्छिक चर के अध्ययन का उपयोग करके दिखाते हैं कि यदि देखी गई प्रविष्टियों की संख्या के क्रम पर है $\max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\log n$ (सामान्यता की हानि के बिना मान लें $m<n$), रैंक न्यूनीकरण समस्या का अनूठा समाधान है जो संभाव्यता के साथ इसके उत्तल विश्राम का समाधान भी होता है $1-{\frac {c}{n^{3}}}$ कुछ स्थिरांक के लिए $c$. यदि की रैंक $M$ छोटा है ($r\leq {\frac {n^{0.2}}{\mu _{0}}}$), प्रेक्षणों के समुच्चय का आकार के क्रम में कम हो जाता है $\mu _{0}n^{1.2}r\log n$. ये परिणाम इष्टतम के करीब हैं, क्योंकि आव्यूह पूर्णता समस्या को कम निर्धारित न करने के लिए देखी जाने वाली प्रविष्टियों की न्यूनतम संख्या के क्रम पर है $nr\log n$.

कैंडेस और ताओ द्वारा इस परिणाम में सुधार किया गया है। वे ऐसी सीमाएँ प्राप्त करते हैं जो मान्यताओं को मजबूत करके केवल पॉलीलॉगरिदमिक कार्यात्मक कारकों द्वारा इष्टतम सीमाओं से भिन्न होती हैं। असंगति संपत्ति के बजाय, वे पैरामीटर के साथ मजबूत असंगति संपत्ति मानते हैं $\mu _{3}$. यह संपत्ति बताती है कि:

1. $|\langle e_{a},P_{U}e_{a'}\rangle -{\frac {r}{m}}1_{a=a'}|\leq \mu _{3}{\frac {\sqrt {r}}{m}}$ के लिए $a,a'\leq m$ और $|\langle e_{b},P_{U}e_{b'}\rangle -{\frac {r}{n}}1_{b=b'}|\leq \mu _{3}{\frac {\sqrt {r}}{n}}$ के लिए $b,b'\leq n$
2. की प्रविष्टियाँ $\sum _{i}u_{i}v_{i}^{\dagger }$ द्वारा परिमाण में बंधे हैं $\mu _{3}{\sqrt {\frac {r}{mn}}}$

सहज रूप से, आव्यूह की मजबूत असंगति $U$ यह दावा करता है कि मानक आधार वैक्टर के ऑर्थोगोनल अनुमान $U$ यदि एकवचन सदिशों को यादृच्छिक रूप से वितरित किया जाए तो ऐसे परिमाण होते हैं जिनकी संभावना अधिक होती है।

कैंडेस और ताओ को वह कब मिला $r$ है $O(1)$ और प्रेक्षित प्रविष्टियों की संख्या के क्रम पर है $\mu _{3}^{4}n(\log n)^{2}$, रैंक न्यूनीकरण समस्या का अनूठा समाधान है जो संभाव्यता के साथ इसके उत्तल विश्राम का समाधान भी होता है $1-{\frac {c}{n^{3}}}$ कुछ स्थिरांक के लिए $c$. मनमानी के लिए $r$, इस दावे के लिए पर्याप्त प्रेक्षित प्रविष्टियों की संख्या सत्य है $\mu _{3}^{2}nr(\log n)^{6}$ और उत्तल विश्राम दृष्टिकोण रैंक बाधा के तहत फ्रोबेनियस वर्ग मानदंड को कम करना है। यह हल करने के समान है

${\begin{aligned}&{\underset {X}{\text{min}}}&&\Vert X\Vert _{F}^{2}\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\text{Rank}}(X)\leq k.\end{aligned}}$ ऑर्थोगोनल प्रोजेक्शन आव्यूह पेश करके $Y$ (अर्थ $Y^{2}=Y,Y=Y'$) के रैंक को मॉडल करने के लिए $X$ के जरिए $X=YX,{\text{trace}}(Y)\leq k$ और इस समस्या का उत्तल विश्राम लेते हुए, हम निम्नलिखित अर्धनिश्चित कार्यक्रम प्राप्त करते हैं

${\begin{aligned}&{\underset {X,Y,\theta }{\text{min}}}&&{\text{trace}}(\theta )\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\text{trace}}(Y)\leq k,0\preceq Y\preceq I\\&&&{\begin{pmatrix}Y&X\\X^{\top }&\theta \end{pmatrix}}\succeq 0.\end{aligned}}$ यदि इस विश्राम में Y प्रक्षेपण आव्यूह है (अर्थात, इसमें द्विआधारी eigenvalues ​​​​है), तो विश्राम तंग है। अन्यथा, यह समग्र उद्देश्य पर वैध निचली सीमा देता है। इसके अलावा, इसे Y के स्वदेशी मानों को लालचपूर्वक पूर्णांकित करके (थोड़े) बड़े उद्देश्य के साथ व्यवहार्य समाधान में परिवर्तित किया जा सकता है।उल्लेखनीय रूप से, इस उत्तल विश्राम को किसी भी एसडीपी को हल किए बिना एक्स और वाई पर वैकल्पिक न्यूनतमकरण द्वारा हल किया जा सकता है, और इस प्रकार यह एसडीपीटी 3 या मोसेक जैसे अत्याधुनिक एसडीपी सॉल्वरों की विशिष्ट संख्यात्मक सीमाओं से परे है।

यह दृष्टिकोण अधिक सामान्य सुधार तकनीक का विशेष मामला है, जिसे ट्रेस-मैट्रिक्स-उत्तल उद्देश्य के साथ किसी भी निम्न-रैंक समस्या पर वैध निचली सीमा प्राप्त करने के लिए प्रयुक्त किया जा सकता है।

क्रमिक अवतरण

केशवन, मोंटानारी और ओहआव्यूह पूर्णता के प्रकार पर विचार करें जहां की रैंक (रैखिक बीजगणित)। $m$ द्वारा $n$ आव्यूह $M$, जिसे पुनर्प्राप्त किया जाना है, ज्ञात है $r$. वे प्रविष्टियों के बर्नौली नमूने, निरंतर पहलू अनुपात को मानते हैं ${\frac {m}{n}}$, की प्रविष्टियों का परिबद्ध परिमाण $M$ (ऊपरी सीमा रहने दें $M_{\text{max}}$), और स्थिर स्थिति संख्या ${\frac {\sigma _{1}}{\sigma _{r}}}$ (कहाँ $\sigma _{1}$ और $\sigma _{r}$ के सबसे बड़े और सबसे छोटे एकवचन मान हैं $M$ क्रमश)। इसके अलावा, वे मानते हैं कि दो असंगति स्थितियाँ संतुष्ट हैं $\mu _{0}$ और $\mu _{1}{\frac {\sigma _{1}}{\sigma _{r}}}$ कहाँ $\mu _{0}$ और $\mu _{1}$ स्थिरांक हैं. होने देना $M^{E}$ ऐसा आव्यूह बनें जो मेल खाता हो $M$ मंच पर $E$ प्रेक्षित प्रविष्टियों की संख्या अन्यत्र 0 है। फिर वे निम्नलिखित एल्गोरिथम प्रस्तावित करते हैं:

1. काट-छांट करना $M^{E}$ से अधिक डिग्री वाले स्तंभों से सभी अवलोकनों को हटाकर ${\frac {2|E|}{n}}$ कॉलम में प्रविष्टियों को 0 पर समुच्चय करके। इसी प्रकार इससे बड़ी डिग्री वाली पंक्तियों से सभी अवलोकन हटा दें ${\frac {2|E|}{n}}$.
2. परियोजना $M^{E}$ इसके पहले पर $r$ प्रमुख कंपोनेंट विश्लेषण। परिणामी आव्यूह को कॉल करें ${\text{Tr}}(M^{E})$.
3. हल करना $\min _{X,Y}\min _{S\in \mathbb {R} ^{r\times r}}{\frac {1}{2}}\sum _{i,j\in E}(M_{ij}-(XSY^{\dagger })_{ij})^{2}+\rho G(X,Y)$ कहाँ $G(X,Y)$ पंक्ति खोज के साथ ढतला हुआ वंश द्वारा कुछ नियमितीकरण (गणित) फ़ंक्शन है। प्रारंभ $X,\;Y$ पर $X_{0},\;Y_{0}$ कहाँ ${\text{Tr}}(M_{E})=X_{0}S_{0}Y_{0}^{\dagger }$. तय करना $G(X,Y)$ कुछ फ़ंक्शन फ़ोर्सिंग के रूप में $X,\;Y$ यदि ग्रेडिएंट डिसेंट के दौरान असंगत बने रहें $X_{0}$ और $Y_{0}$ असंगत हैं.
4. आव्यूह लौटाएं $XSY^{\dagger }$.

एल्गोरिथम के चरण 1 और 2 से आव्यूह प्राप्त होता है ${\text{Tr}}(M^{E})$ सच्चे आव्यूह के बहुत करीब $M$ (जैसा कि मूल माध्य वर्ग विचलन | मूल माध्य वर्ग त्रुटि (आरएमएसई) द्वारा मापा जाता है) उच्च संभावना के साथ। विशेषकर, संभाव्यता के साथ $1-{\frac {1}{n^{3}}}$, ${\frac {1}{mnM_{\text{max}}^{2}}}\|M-{\text{Tr}}(M^{E})\|_{F}^{2}\leq C{\frac {r}{m|E|}}{\sqrt {\frac {m}{n}}}$ कुछ स्थिरांक के लिए $C$. $\|\cdot \|_{F}$ फ्रोबेनियस आव्यूह मानदंड को दर्शाता है। ध्यान दें कि इस परिणाम को धारण करने के लिए मान्यताओं के पूरे समुच्चय की आवश्यकता नहीं है। उदाहरण के लिए, असंगति की स्थिति केवल स्पष्ट पुनर्निर्माण में ही प्रयुक्त होती है। अंत में, हालाँकि ट्रिमिंग काउंटर सहज ज्ञान युक्त लग सकती है क्योंकि इसमें जानकारी को बाहर फेंकना सम्मिलित है, यह प्रोजेक्टिंग सुनिश्चित करता है $M^{E}$ इसके पहले पर $r$ प्रमुख घटक विश्लेषण अंतर्निहित आव्यूह के बारे में अधिक जानकारी देता है $M$ देखी गई प्रविष्टियों के बारे में।

चरण 3 में, उम्मीदवार आव्यूह का स्थान $X,\;Y$ यह ध्यान देकर कम किया जा सकता है कि आंतरिक न्यूनतमकरण समस्या का समाधान समान है $(X,Y)$ से संबंधित $(XQ,YR)$ कहाँ $Q$ और $R$ आह, रूढ़िवादिता $r$ द्वारा $r$ matrices. फिर दो ग्रासमैनियन के क्रॉस उत्पाद पर ग्रेडिएंट डिसेंट का प्रदर्शन किया जा सकता है। यदि $r\ll m,\;n$ और प्रेक्षित प्रविष्टि समुच्चय के क्रम में है $nr\log n$, चरण 3 द्वारा लौटाया गया आव्यूह बिल्कुल सही है $M$. तब एल्गोरिथ्म ऑर्डर इष्टतम है, क्योंकि हम जानते हैं कि आव्यूह पूर्णता समस्या के लिए सिस्टम को कम निर्धारित नहीं किया जाना चाहिए, प्रविष्टियों की संख्या क्रम में होनी चाहिए $nr\log n$.

वैकल्पिक न्यूनतम वर्ग न्यूनतमकरण

वैकल्पिक न्यूनीकरण निम्न-रैंक आव्यूह खोजने के लिए व्यापक रूप से प्रयुक्त और अनुभवजन्य रूप से सफल दृष्टिकोण का प्रतिनिधित्व करता है जो दिए गए डेटा के लिए सबसे उपयुक्त है। उदाहरण के लिए, निम्न-रैंक आव्यूह पूर्णता की समस्या के लिए, इस विधि को सबसे स्पष्ट और कुशल में से माना जाता है, और नेटफ्लिक्स समस्या में विजेता प्रविष्टि का प्रमुख घटक बनता है। वैकल्पिक न्यूनतमकरण दृष्टिकोण में, निम्न-रैंक लक्ष्य आव्यूह को द्विरेखीय रूप में लिखा जाता है:

$X=UV^{T}$;

फिर एल्गोरिदम सर्वश्रेष्ठ खोजने के बीच वैकल्पिक होता है $U$ और सबसे अच्छा $V$. जबकि समग्र समस्या गैर-उत्तल है, प्रत्येक उप-समस्या आम तौर पर उत्तल होती है और इसे कुशलता से हल किया जा सकता है। जैन, नेत्रपल्ली और संघवी आव्यूह पूर्णता और आव्यूह सेंसिंग दोनों के लिए वैकल्पिक न्यूनतमकरण के प्रदर्शन के लिए पहली गारंटी दी गई है।

वैकल्पिक न्यूनतमकरण एल्गोरिथ्म को निम्नलिखित गैर-उत्तल समस्या को हल करने के अनुमानित तरीके के रूप में देखा जा सकता है:

${\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}$ जैन, नेत्रपल्ली और सांघवी द्वारा प्रस्तावित AltMinComplete एल्गोरिदम यहां सूचीबद्ध है:# इनपुट: अवलोकित समुच्चय $\Omega$, मूल्य $P_{\Omega }(M)$

1. बंटवारा $\Omega$ में $2T+1$ सबसमुच्चय $\Omega _{0},\cdots ,\Omega _{2T}$ के प्रत्येक तत्व के साथ $\Omega$ में से से संबंधित $\Omega _{t}$ समान संभावना के साथ (प्रतिस्थापन के साथ नमूनाकरण)
2. ${\hat {U}}^{0}=SVD({\frac {1}{p}}P_{\Omega _{0}}(M),k)$ यानी, शीर्ष-$k$ के बाएँ एकवचन सदिश ${\frac {1}{p}}P_{\Omega _{0}}(M)$
3. क्लिपिंग: के सभी तत्वों को समुच्चय करें ${\hat {U}}^{0}$ जिसका परिमाण इससे भी अधिक है ${\frac {2\mu {\sqrt {k}}}{\sqrt {n}}}$ के स्तंभों को शून्य और लंबोसामान्यीकृत करना ${\hat {U}}^{0}$
4. के लिए $t=0,\cdots ,T-1$ करना
5. $\quad {\hat {V}}^{t+1}\leftarrow {\text{argmin}}_{V\in \mathbb {R} ^{n\times k}}\|P_{\Omega _{t+1}}({\hat {U}}V^{T}-M)\|_{F}^{2}$
6. $\quad {\hat {U}}^{t+1}\leftarrow {\text{argmin}}_{U\in \mathbb {R} ^{m\times k}}\|P_{\Omega _{T+t+1}}(U({\hat {V}}^{t+1})^{T}-M)\|_{F}^{2}$
7. के लिए समाप्त
8. वापस करना $X={\hat {U}}^{T}({\hat {V}}^{T})^{T}$

उन्होंने देख कर दिखाया $|\Omega |=O(({\frac {\sigma _{1}^{*}}{\sigma _{k}^{*}}})^{6}k^{7}\log n\log(k\|M\|_{F}/\epsilon ))$ असंगत आव्यूह की यादृच्छिक प्रविष्टियाँ $M$, AltMinComplete एल्गोरिदम पुनर्प्राप्त कर सकता है $M$ में $O(\log(1/\epsilon ))$ कदम। नमूना जटिलता के संदर्भ में ($|\Omega |$), सैद्धांतिक रूप से, वैकल्पिक न्यूनतमकरण के लिए बड़ी आवश्यकता हो सकती है $\Omega$ उत्तल विश्राम से. हालाँकि अनुभवजन्य रूप से ऐसा नहीं लगता है जिसका तात्पर्य यह है कि नमूना जटिलता सीमा को और कड़ा किया जा सकता है। समय की जटिलता के संदर्भ में, उन्होंने दिखाया कि AltMinComplete को समय की आवश्यकता है

$O(|\Omega |k^{2}\log(1/\epsilon ))$.

यह ध्यान देने योग्य है कि, हालांकि उत्तल विश्राम आधारित तरीकों का कठोर विश्लेषण होता है, वैकल्पिक न्यूनतमकरण आधारित एल्गोरिदम व्यवहार में अधिक सफल होते हैं।

अनुप्रयोग

आव्यूह पूर्णता के अनेक अनुप्रयोगों को कैंडेस और प्लान द्वारा संक्षेपित किया गया हैनिम्नलिखित नुसार:

सहयोगात्मक फ़िल्टरिंग

सहयोगात्मक फ़िल्टरिंग अनेक उपयोगकर्ताओं से स्वाद संबंधी जानकारी एकत्र करके उपयोगकर्ता की रुचियों के बारे में स्वचालित पूर्वानुमान लगाने का कार्य है। ऐप्पल, अमेज़ॅन, बार्न्स एंड नोबल और नेटफ्लिक्स जैसी कंपनियां आंशिक ज्ञान से अपने उपयोगकर्ता की प्राथमिकताओं का अनुमान लगाने की प्रयास कर रही हैं। इस प्रकार की आव्यूह पूर्णता समस्या में, अज्ञात पूर्ण आव्यूह को अधिकांशतः निम्न रैंक माना जाता है क्योंकि केवल कुछ कारक ही आमतौर पर किसी व्यक्ति के स्वाद या पसंद में योगदान करते हैं।

सिस्टम पहचान

नियंत्रण में, कोई व्यक्ति असतत-समय रैखिक समय-अपरिवर्तनीय राज्य-अंतरिक्ष मॉडल को फिट करना चाहेगा

${\begin{aligned}x(t+1)&=Ax(t)+Bu(t)\\y(t)&=Cx(t)+Du(t)\end{aligned}}$ इनपुट के अनुक्रम के लिए $u(t)\in \mathbb {R} ^{m}$ और आउटपुट $y(t)\in \mathbb {R} ^{p},t=0,\ldots ,N$. सदिश $x(t)\in \mathbb {R} ^{n}$ समय पर सिस्टम की स्थिति है $t$ और $n$ सिस्टम मॉडल का क्रम है. इनपुट/आउटपुट जोड़ी से, कोई मैट्रिस पुनर्प्राप्त करना चाहेगा $A,B,C,D$ और प्रारंभिक अवस्था $x(0)$. इस समस्या को निम्न-रैंक आव्यूह पूर्णता समस्या के रूप में भी देखा जा सकता है।

इंटरनेट ऑफ थिंग्स (IoT) स्थानीयकरण

IoT सेंसर नेटवर्क में स्थानीयकरण (या वैश्विक स्थिति) समस्या स्वाभाविक रूप से उभरती है। समस्या यूक्लिडियन अंतरिक्ष में स्थानीय या जोड़ीदार दूरियों के आंशिक समुच्चय से सेंसर मानचित्र को पुनर्प्राप्त करना है। इस प्रकार यह रैंक दो के साथ आव्यूह पूर्णता समस्या है यदि सेंसर 2-डी विमान में स्थित हैं और तीन यदि वे 3-डी अंतरिक्ष में हैं।

सामाजिक नेटवर्क पुनर्प्राप्ति

वास्तविक दुनिया के अधिकांश सामाजिक नेटवर्क में निम्न-रैंक दूरी वाले मैट्रिसेस होते हैं। जब हम पूरे नेटवर्क को मापने में सक्षम नहीं होते हैं, जो निजी नोड्स, सीमित भंडारण या गणना संसाधनों जैसे कारणों से हो सकता है, तो हमारे पास ज्ञात दूरी प्रविष्टियों का केवल अंश होता है। आपराधिक नेटवर्क ऐसे नेटवर्क का अच्छा उदाहरण हैं। इन न देखी गई दूरियों को पुनर्प्राप्त करने के लिए निम्न-रैंक आव्यूह पूर्णता का उपयोग किया जा सकता है।

यह भी देखें

• मैट्रिक्स नियमितीकरण
• नेटफ्लिक्स पुरस्कार
• सहयोगी को छानने
• सिस्टम पहचान
• उत्तल अनुकूलन
• प्रतिरूपण (सांख्यिकी)