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

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

आव्यूह पूर्णता आंशिक रूप से देखे गए आव्यूह की लुप्त प्रविष्टियों को एकत्रित करने का कार्य है, जो आंकड़ों में डेटा प्रतिरूपण (सांख्यिकी) करने के समान है। डेटासमुच्चय की विस्तृत श्रृंखला स्वाभाविक रूप से आव्यूह रूप में व्यवस्थित होती है। उदाहरण मूवी-रेटिंग आव्यूह है, जैसा कि नेटफ्लिक्स प्रॉब्लम में दिखाई देता है: रेटिंग आव्यूह दिया जाता है जिसमें प्रत्येक प्रविष्टि $(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$ को विशिष्ट रूप से पुनर्निर्मित करने से पहले कितनी प्रविष्टियों को देखा जाना चाहिए, इस पर एक सूचना सैद्धांतिक निचली सीमा है। जहाँ $r$ से कम या उसके समान रैंक वाले $n$ आव्यूहों द्वारा $m$ का समुच्चय ${\mathbb {C} }^{m\times n}$ आयाम $(n+m)r-r^{2}$ के साथ एक बीजगणितीय किस्म है। इस परिणाम का उपयोग करके, कोई यह दिखा सकता है कि $r\leq n/2$ होने पर अद्वितीय समाधान प्राप्त करने के लिए ${\mathbb {C} }^{n\times n}$ में आव्यूह पूर्णता के लिए कम से कम $4nr-4r^{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$ प्रस्तुत किया गया है इस अर्थ में बहुत विरल नहीं हैं कि प्रत्येक एकवचन सदिश के सभी निर्देशांक तुलनीय परिमाण के होते हैं, न कि केवल कुछ निर्देशांक जिनमें काफी बड़े परिमाण होते हैं। मानक आधार सदिश तब एकवचन सदिश और सदिश के रूप में अवांछनीय होते हैं और $\mathbb {R} ^{n}$ में सदिश ${\frac {1}{\sqrt {n}}}{\begin{bmatrix}1\\1\\\vdots \\1\end{bmatrix}}$वांछनीय है। यदि एकवचन सदिश पर्याप्त रूप से विरल हों तो क्या असत्य हो सकता है, इसके उदाहरण के रूप में, एकवचन मान अपघटन $I_{m}{\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}I_{n}$ के साथ $m$ द्वारा $n$ आव्यूह ${\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}$ इस पर विचार करें तथा इसका पुनर्निर्माण करने से पहले $M$ की लगभग सभी प्रविष्टियाँ इसका नमूना लिया जाना चाहिए।

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

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$ आव्यूह है जिसमें $(i,j)\in \Omega$ के लिए प्रविष्टियाँ $Z_{ij}$ हैं, यह मानते हुए कि कुछ $\delta >0$ के लिए $\|P_{\Omega }(Z)\|_{F}\leq \delta$। अपूर्ण आव्यूह को पुनर्प्राप्त करने के लिए, हम निम्नलिखित अनुकूलन समस्या को हल करने का प्रयास करते हैं:

${\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$ कम से कम लंबे समय तक अपूर्ण संस्करण से उच्च संभावना के साथ पूरी तरह से पुनर्प्राप्त किया जा सकता है जब तक $X$ कि की कम से कम $CrN\log ^{2}(n)$ की प्रविष्टियाँ $C>1$ यादृच्छिक रूप से समान रूप से देखे जाते हैं सामान्य असंबद्धता स्थितियों, उप-स्थानों की ज्यामितीय व्यवस्था और उप-स्थानों पर स्तंभों के वितरण के आधार पर स्थिरांक होता है |

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

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

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

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

रैंक न्यूनीकरण समस्या एनपी-हार्ड है। कैंडेस और रेचट द्वारा प्रस्तावित दृष्टिकोण, समस्या का उत्तल फलन विश्राम बनाना और परमाणु मानदंड $\|M\|_{*}$ (जो $M$ के एकवचन मानों का योग देता है ) को कम करना है तथा $M$ के शून्य एकवचन मान के अतिरिक्त ${\text{rank}}(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})$ है. एसडीपीटी3 जैसे अत्याधुनिक सॉल्वर केवल 100 गुणा 100 तक के आकार के आव्यूह को संभाल सकते हैं तथा वैकल्पिक प्रथम क्रम विधि जो उत्तल विश्राम को लगभग हल करती है वह काई, कैंडेस और शेन द्वारा प्रस्तुत सिंगुलर वैल्यू थ्रेशोल्डिंग एल्गोरिदम है।

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

$X=YX,{\text{trace}}(Y)\leq k$ के माध्यम से $X$ की रैंक को मॉडल करने के लिए ऑर्थोगोनल प्रोजेक्शन आव्यूह $Y$ (अर्थ $Y^{2}=Y,Y=Y'$) प्रस्तुत करके और इस समस्या का उत्तल विश्राम लेते हुए, हम निम्नलिखित अर्धनिश्चित फलन प्राप्त करते हैं

${\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 प्रक्षेपण आव्यूह है (अर्थात, इसमें बाइनरी आइजेनवैल्यू ​​​​है), तो विश्राम तंग है। अन्यथा, यह समग्र उद्देश्य पर वैध निचली सीमा देता है। इसके अतरिक्त, इसे Y के आइजेनवैल्यू को लालचपूर्वक पूर्णांकित करके (थोड़े) बड़े उद्देश्य के साथ व्यवहार्य समाधान में परिवर्तित किया जा सकता है। उल्लेखनीय रूप से, इस उत्तल विश्राम को किसी भी एसडीपी को हल किए बिना X और 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}$ ऐसा आव्यूह बनें जो प्रेक्षित प्रविष्टियों के मंच $E$ पर $M$ से मेल खाता हो और संख्या अन्यत्र 0 है। फिर वह निम्नलिखित एल्गोरिथम प्रस्तावित करते हैं:

1. स्तम्भ में प्रविष्टियों को 0 पर समुच्चय करके ${\frac {2|E|}{n}}$ से अधिक डिग्री वाले स्तंभों से सभी अवलोकनों को हटाकर $M^{E}$ को ट्रिम करें। इसी प्रकार के ${\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 }$. यदि $X_{0}$ और $Y_{0}$ असंगत हैं. तब $G(X,Y)$ को कुछ फ़ंक्शन के रूप में सेट करें, जो $X,\;Y$ को ग्रेडिएंट डिसेंट के समय असंगत रहने के लिए बाध्य करता है।
4. आव्यूह $XSY^{\dagger }$ लौटाएं .

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

चरण 3 में, उम्मीदवार आव्यूह $X,\;Y$ का स्थान को यह ध्यान देकर कम किया जा सकता है कि आंतरिक न्यूनतमकरण समस्या का $(X,Y)$ के लिए वही समाधान है जो कि $(XQ,YR)$ से संबंधित है जहाँ $Q$ और $R$ ऑर्थोनॉर्मल $r$ है तथा $r$ मैट्रिसेस द्वारा फिर दो ग्रासमैनियन के क्रॉस उत्पाद पर ग्रेडिएंट डिसेंट का प्रदर्शन किया जा सकता है। यदि $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}}$

जैन, नेत्रपल्ली और सांघवी द्वारा प्रस्तावित ऑल्ट मिन कम्पलीट एल्गोरिदम यहां सूचीबद्ध है:

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

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

$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-डी समिष्ट में हैं।

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

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

यह भी देखें

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