CUR मैट्रिक्स सन्निकटन

एक CUR मैट्रिक्स सन्निकटन तीन मैट्रिक्स (गणित) का एक सेट है, जब एक साथ गुणा किया जाता है, तो किसी दिए गए मैट्रिक्स का बारीकी से अनुमान लगाया जाता है। एक CUR सन्निकटन का उपयोग उसी तरह किया जा सकता है जैसे एकवचन मूल्य अपघटन (SVD) के निम्न-रैंक सन्निकटन। CUR सन्निकटन SVD की तुलना में कम सटीक हैं, लेकिन वे दो प्रमुख लाभ प्रदान करते हैं, दोनों इस तथ्य से उपजी हैं कि पंक्तियाँ और स्तंभ मूल मैट्रिक्स से आते हैं (बाएँ और दाएँ एकवचन वैक्टर के बजाय):

• एसवीडी बनाम कम विषम समय जटिलता के साथ इसकी गणना करने के तरीके हैं।
• मैट्रिसेस अधिक व्याख्यात्मक हैं; विघटित मैट्रिक्स में पंक्तियों और स्तंभों का अर्थ अनिवार्य रूप से मूल मैट्रिक्स में उनके अर्थ के समान होता है।

औपचारिक रूप से, मैट्रिक्स A का एक CUR मैट्रिक्स सन्निकटन तीन मैट्रिक्स C, U, और R है जैसे कि C को A के कॉलम से बनाया गया है, R को A की पंक्तियों से बनाया गया है, और उत्पाद CUR बारीकी से A का अनुमान लगाता है। आमतौर पर CUR है एक रैंक (रैखिक बीजगणित) -k सन्निकटन के रूप में चुना गया है, जिसका अर्थ है कि C में A के k कॉलम हैं, R में A की k पंक्तियाँ हैं, और U एक k-by-k मैट्रिक्स है। किसी दिए गए रैंक के लिए कई संभावित CUR मैट्रिक्स सन्निकटन और कई CUR मैट्रिक्स सन्निकटन हैं।

CUR मैट्रिक्स सन्निकटन अक्सर होता है प्रमुख घटक विश्लेषण में SVD के निम्न-रैंक सन्निकटन के स्थान पर उपयोग किया जाता है। CUR कम सटीक है, लेकिन मैट्रिक्स C के कॉलम A से लिए गए हैं और R की पंक्तियाँ A से ली गई हैं। PCA में, A के प्रत्येक कॉलम में डेटा नमूना होता है; इस प्रकार, मैट्रिक्स C डेटा नमूनों के एक सबसेट से बना है। एसवीडी के बाएं एकवचन वैक्टर की तुलना में व्याख्या करना बहुत आसान है, जो घुमाए गए स्थान में डेटा का प्रतिनिधित्व करते हैं। इसी तरह, मैट्रिक्स आर प्रत्येक डेटा नमूने के लिए मापे गए चर के सबसेट से बना है। एसवीडी के सही एकवचन वैक्टर की तुलना में इसे समझना आसान है, जो अंतरिक्ष में डेटा का एक और घुमाव है।

गणितीय परिभाषा

हम्म और हुआंग एक मैट्रिक्स के CUR अपघटन की मूल बातों का वर्णन करते हुए निम्नलिखित प्रमेय देता है $L$ रैंक के साथ $r$:

प्रमेय: पंक्ति और स्तंभ सूचकांकों पर विचार करें $I,J\subseteq [n]$ साथ $|I|,|J|\geq r$. सबमैट्रिसेस को निरूपित करें $C=L_{:,J},$ $U=L_{I,J}$ और $R=L_{I,:}$. अगर रैंक ($U$) = रैंक ($L$), तब $L=CU^{+}R$, कहाँ $(\cdot )^{+}$ मूर-पेनरोज़ स्यूडोइनवर्स को दर्शाता है।

दूसरे शब्दों में, अगर $L$ निम्न रैंक है, हम एक उप-मैट्रिक्स ले सकते हैं $U=L_{I,J}$ कुछ पंक्तियों के साथ एक ही रैंक के $R$ और कॉलम $C$ का $L$ और उनका पुनर्निर्माण करने के लिए उपयोग करें $L$.

एल्गोरिदम

CUR मैट्रिक्स सन्निकटन अद्वितीय नहीं है और एक की गणना के लिए कई एल्गोरिदम हैं। एक है एल्गोरिथमकुर।

रैखिक समय CUR एल्गोरिथम यादृच्छिक रूप से (प्रतिस्थापन के साथ) स्तंभों का नमूना लेकर जे को चुकता स्तंभ मानदंडों के आनुपातिक संभावना के साथ चुनता है, $\|L_{:,j}\|_{2}^{2}$; और इसी तरह नमूनाकरण मैं वर्ग पंक्ति मानदंडों के लिए आनुपातिक, $\|L_{i}\|_{2}^{2}$. लेखक यह दिखाते हैं ले रहा $|J|\approx k/\varepsilon ^{4}$ और $|I|\approx k/\varepsilon ^{2}$ कहाँ $0\leq \varepsilon$, एल्गोरिथम फ्रोबेनियस एरर बाउंड प्राप्त करता है $\|A-CUR\|_{F}\leq \|A-A_{k}\|_{F}+\varepsilon \|A\|_{F}$, कहाँ $A_{k}$ इष्टतम रैंक k सन्निकटन है।

टेंसर

टेन्सर-कर्ट अपघटन मैट्रिक्स-CUR अपघटन का एक सामान्यीकरण है। औपचारिक रूप से, टेंसर ए का कर्ट टेंसर सन्निकटन तीन मैट्रिसेस और एक (कोर-) टेंसर सी, आर, टी और यू ऐसा है कि सी को ए के कॉलम से बनाया गया है, आर को ए की पंक्तियों से बनाया गया है, टी को ट्यूबों से बनाया गया है। A का और यह कि उत्पाद U(C,R,T) (जहाँ $i,j,l$-इसकी चौथी एंट्री है $\sum _{i',j',l'}U_{i',j',l'}C_{i,i'}R_{j,j'}T_{l,l'}$) बारीकी से A का अनुमान लगाता है। आमतौर पर CURT को एक रैंक (रैखिक बीजगणित) -k सन्निकटन के रूप में चुना जाता है, जिसका अर्थ है कि C में A के k कॉलम हैं, R में A की k पंक्तियाँ हैं, T में A की ट्यूब हैं और U एक k- है बाय-के-बाय-के (कोर-) टेंसर।

यह भी देखें

• आयामीता में कमी