CUR मैट्रिक्स सन्निकटन: Difference between revisions
(Created page with "एक CUR मैट्रिक्स सन्निकटन तीन मैट्रिक्स (गणित) का एक सेट है, जब एक सा...") |
No edit summary |
||
| Line 1: | Line 1: | ||
एक | एक सीयूआर आव्यूह सन्निकटन तीन [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] का एक सेट है जब एक साथ गुणा किया जाता है, तो किसी दिए गए आव्यूह का निकट से अनुमान लगाया जाता है।<ref name=mahoney>{{cite web|title=बेहतर डेटा विश्लेषण के लिए CUR मैट्रिक्स अपघटन|url=http://www.pnas.org/content/106/3/697.full|accessdate=26 June 2012|author=Michael W. Mahoney|author2=Petros Drineas}}</ref><ref>{{cite conference|title=इष्टतम CUR मैट्रिक्स अपघटन| conference = STOC '14 Proceedings of the forty-sixth annual ACM symposium on Theory of Computing|last1= Boutsidis |first1= Christos |last2=Woodruff|first2=David P.|year=2014}}</ref><ref>{{cite conference|title=प्रवेशवार एल1-मानदंड त्रुटि के साथ निम्न रैंक सन्निकटन| conference = STOC '17 Proceedings of the forty-ninth annual ACM symposium on Theory of Computing|last1=Song|first1=Zhao|last2=Woodruff|first2=David P.|last3=Zhong|first3=Peilin|year=2017| arxiv = 1611.00898}}</ref> एक सीयूआर सन्निकटन का उपयोग उसी तरह किया जा सकता है जैसे एकवचन मूल्य अपघटन (एसवीडी) के निम्न-पद सन्निकटन सीयूआर सन्निकटन एसवीडी की तुलना में कम स्पष्ट हैं किंतु वे दो प्रमुख लाभ प्रदान करते हैं दोनों इस तथ्य से उपजी हैं कि पंक्तियाँ और स्तंभ मूल आव्यूह से आते हैं (बाएँ और दाएँ एकवचन वैक्टर के अतिरिक्त ): | ||
* एसवीडी बनाम कम विषम समय जटिलता के साथ इसकी गणना करने के | * एसवीडी बनाम कम विषम समय जटिलता के साथ इसकी गणना करने के विधि हैं। | ||
* मैट्रिसेस अधिक व्याख्यात्मक हैं; विघटित | * मैट्रिसेस अधिक व्याख्यात्मक हैं; विघटित आव्यूह में पंक्तियों और स्तंभों का अर्थ अनिवार्य रूप से मूल आव्यूह में उनके अर्थ के समान होता है। | ||
औपचारिक रूप से | औपचारिक रूप से आव्यूह A का एक सीयूआर आव्यूह सन्निकटन तीन आव्यूह C, U, और R है जैसे कि C को A के स्तम्भ से बनाया गया है, R को A की पंक्तियों से बनाया गया है, और उत्पाद सीयूआर निकट से A का अनुमान लगाता है। सामान्यतः सीयूआर है एक [[रैंक (रैखिक बीजगणित)|पद (रैखिक बीजगणित)]] -k सन्निकटन के रूप में चुना गया है, जिसका अर्थ है कि C में A के k स्तम्भ हैं, R में A की k पंक्तियाँ हैं और U एक k-by-k आव्यूह है। किसी दिए गए पद के लिए कई संभावित सीयूआर आव्यूह सन्निकटन और कई सीयूआर आव्यूह सन्निकटन हैं। | ||
सीयूआर आव्यूह सन्निकटन अधिकांशतः होता है प्रमुख घटक विश्लेषण में SVD के निम्न-पद सन्निकटन के स्थान पर उपयोग किया जाता है। सीयूआर कम स्पष्ट है, किंतु आव्यूह C के स्तम्भ A से लिए गए हैं और R की पंक्तियाँ A से ली गई हैं। PCA में, A के प्रत्येक स्तम्भ में डेटा नमूना होता है; इस प्रकार, आव्यूह C डेटा नमूनों के एक उपसमुच्चय से बना है। एसवीडी के बाएं एकवचन वैक्टर की तुलना में व्याख्या करना बहुत आसान है, जो घुमाए गए स्थान में डेटा का प्रतिनिधित्व करते हैं। इसी तरह आव्यूह आर प्रत्येक डेटा नमूने के लिए मापे गए चर के उपसमुच्चय से बना है। एसवीडी के सही एकवचन वैक्टर की तुलना में इसे समझना आसान है जो अंतरिक्ष में डेटा का एक और घुमाव है। | |||
'''आर आव्यूह सन्निकटन अधिकांशतः होता है प्रमुख घटक विश्लेषण में SVD के निम्न-पद सन्निकटन के स्थान पर उपयोग किया जाता है। सीयूआर कम स्पष्ट है, किंतु आव्यूह C के स्तम्भ A से लिए गए हैं और R की''' | |||
== गणितीय परिभाषा == | == गणितीय परिभाषा == | ||
हैम और हुआंग पद <math>r</math> के साथ एक आव्यूह <math>L</math> के सीयूआर अपघटन की मूल बातों का वर्णन करते हुए निम्नलिखित प्रमेय देते हैं।<ref>Keaton Hamm and Longxiu Huang. Perspectives on CUR decompositions. Applied and Computational Harmonic Analysis, 48(3):1088–1099, 2020.</ref> | |||
प्रमेय:<math>I, J \subseteq [n]</math>के साथ पंक्ति और स्तंभ सूचकांकों <math>|I|, |J| \ge r</math> पर विचार करें। सबमैट्रिसेस को निरूपित करें <math>C = L_{:,J},</math> <math>U = L_{I,J}</math> और <math>R = L_{I,:}</math>। अगर पद (<math>U</math> ) = पद (<math>L</math>), तो <math>L = CU^+R</math>, जहां <math>(\cdot)^+</math> मूर-पेनरोज़ स्यूडोइनवर्स को दर्शाता है। | |||
दूसरे शब्दों में यदि <math>L</math> की पद कम है तो हम <math>L</math> की कुछ पंक्तियों <math>R</math> और स्तम्भ <math>C</math> के साथ समान पद का एक उप-आव्यूह <math>U = L_{I,J}</math> ले सकते हैं और | |||
का पुनर्निर्माण करने के लिए उनका उपयोग कर सकते हैं। . | |||
== एल्गोरिदम == | == एल्गोरिदम == | ||
सीयूआर आव्यूह सन्निकटन अद्वितीय नहीं है और एक की गणना के लिए कई एल्गोरिदम हैं। एक एल्गोरिथमकुर है ।<ref name=mahoney /> | |||
रैखिक समय | "रैखिक समय सीयूआर " एल्गोरिद्म यादृच्छिक रूप से (प्रतिस्थापन के साथ) स्तंभों का चयन करके J को चुनता है जिसमें वर्गित स्तंभ मानदंडों के समानुपातिक संभाव्यता होती है, <math>\|L_{:,j}\|_2^2</math> और इसी प्रकार वर्गाकार पंक्ति मानदंडों के अनुपात में I का नमूनाकरण, <math>\|L_{i}\|_2^2</math> लेखक दिखाते हैं कि <math>|J| \approx k /\varepsilon^4</math> और <math>|I| \approx k / \varepsilon^2</math> लेकर <math>0 \le \varepsilon</math> , एल्गोरिथ्म फ्रोबेनियस एरर बाउंड <math>\|A - CUR\|_F \le \|A - A_k\|_F + \varepsilon \|A\|_F</math> प्राप्त करता है। जहां <math>A_k</math> इष्टतम पद k सन्निकटन है<ref>{{Cite journal |last=Drineas |first=Petros |last2=Kannan |first2=Ravi |last3=Mahoney |first3=Michael W. |date=2006-01-01 |title=Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication |url=https://epubs.siam.org/doi/abs/10.1137/S0097539704442684 |journal=SIAM Journal on Computing |volume=36 |issue=1 |pages=132–157 |doi=10.1137/S0097539704442684 |issn=0097-5397}}</ref>। | ||
लेखक | |||
== टेंसर == | == टेंसर == | ||
टेन्सर-कर्ट अपघटन | टेन्सर-कर्ट अपघटन आव्यूह -सीयूआर अपघटन का एक सामान्यीकरण है। औपचारिक रूप से, टेंसर A का कर्ट टेंसर सन्निकटन तीन मैट्रिसेस और एक (कोर-) टेंसर ''C'', ''R'', ''T'' और ''U'' ऐसा है कि ''C'' को ''A'' के स्तम्भ से बनाया गया है, ''R'' को ''A'' की पंक्तियों से बनाया गया है, ''T'' को ट्यूबों से बनाया गया है। A का और उत्पाद U(C,R,T) (जहाँ <math>i,j,l</math>-इसकी प्रविष्टि<math>\sum_{i',j',l'}U_{i',j',l'}C_{i,i'}R_{j,j'}T_{l,l'} </math>निकट से A का अनुमान लगाता है। सामान्यतः कर्ट को पद-के सन्निकटन के रूप में चुना जाता है, जो इसका अर्थ है कि C में A का k स्तम्भ है, R में A की k पंक्तियाँ हैं T में A की ट्यूब हैं और U k-by-k-by-k (कोर-) टेंसर है।<ref>{{cite arXiv|title=सापेक्ष त्रुटि टेन्सर निम्न रैंक सन्निकटन|eprint = 1704.08246|last1=Song|first1=Zhao|last2=Woodruff|first2=David P.|last3=Zhong|first3=Peilin|class=cs.DS|year=2017}}</ref> | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 10:10, 27 May 2023
एक सीयूआर आव्यूह सन्निकटन तीन आव्यूह (गणित) का एक सेट है जब एक साथ गुणा किया जाता है, तो किसी दिए गए आव्यूह का निकट से अनुमान लगाया जाता है।[1][2][3] एक सीयूआर सन्निकटन का उपयोग उसी तरह किया जा सकता है जैसे एकवचन मूल्य अपघटन (एसवीडी) के निम्न-पद सन्निकटन सीयूआर सन्निकटन एसवीडी की तुलना में कम स्पष्ट हैं किंतु वे दो प्रमुख लाभ प्रदान करते हैं दोनों इस तथ्य से उपजी हैं कि पंक्तियाँ और स्तंभ मूल आव्यूह से आते हैं (बाएँ और दाएँ एकवचन वैक्टर के अतिरिक्त ):
- एसवीडी बनाम कम विषम समय जटिलता के साथ इसकी गणना करने के विधि हैं।
- मैट्रिसेस अधिक व्याख्यात्मक हैं; विघटित आव्यूह में पंक्तियों और स्तंभों का अर्थ अनिवार्य रूप से मूल आव्यूह में उनके अर्थ के समान होता है।
औपचारिक रूप से आव्यूह A का एक सीयूआर आव्यूह सन्निकटन तीन आव्यूह C, U, और R है जैसे कि C को A के स्तम्भ से बनाया गया है, R को A की पंक्तियों से बनाया गया है, और उत्पाद सीयूआर निकट से A का अनुमान लगाता है। सामान्यतः सीयूआर है एक पद (रैखिक बीजगणित) -k सन्निकटन के रूप में चुना गया है, जिसका अर्थ है कि C में A के k स्तम्भ हैं, R में A की k पंक्तियाँ हैं और U एक k-by-k आव्यूह है। किसी दिए गए पद के लिए कई संभावित सीयूआर आव्यूह सन्निकटन और कई सीयूआर आव्यूह सन्निकटन हैं।
सीयूआर आव्यूह सन्निकटन अधिकांशतः होता है प्रमुख घटक विश्लेषण में SVD के निम्न-पद सन्निकटन के स्थान पर उपयोग किया जाता है। सीयूआर कम स्पष्ट है, किंतु आव्यूह C के स्तम्भ A से लिए गए हैं और R की पंक्तियाँ A से ली गई हैं। PCA में, A के प्रत्येक स्तम्भ में डेटा नमूना होता है; इस प्रकार, आव्यूह C डेटा नमूनों के एक उपसमुच्चय से बना है। एसवीडी के बाएं एकवचन वैक्टर की तुलना में व्याख्या करना बहुत आसान है, जो घुमाए गए स्थान में डेटा का प्रतिनिधित्व करते हैं। इसी तरह आव्यूह आर प्रत्येक डेटा नमूने के लिए मापे गए चर के उपसमुच्चय से बना है। एसवीडी के सही एकवचन वैक्टर की तुलना में इसे समझना आसान है जो अंतरिक्ष में डेटा का एक और घुमाव है।
आर आव्यूह सन्निकटन अधिकांशतः होता है प्रमुख घटक विश्लेषण में SVD के निम्न-पद सन्निकटन के स्थान पर उपयोग किया जाता है। सीयूआर कम स्पष्ट है, किंतु आव्यूह C के स्तम्भ A से लिए गए हैं और R की
गणितीय परिभाषा
हैम और हुआंग पद के साथ एक आव्यूह के सीयूआर अपघटन की मूल बातों का वर्णन करते हुए निम्नलिखित प्रमेय देते हैं।[4]
प्रमेय:के साथ पंक्ति और स्तंभ सूचकांकों पर विचार करें। सबमैट्रिसेस को निरूपित करें और । अगर पद ( ) = पद (), तो , जहां मूर-पेनरोज़ स्यूडोइनवर्स को दर्शाता है।
दूसरे शब्दों में यदि की पद कम है तो हम की कुछ पंक्तियों और स्तम्भ के साथ समान पद का एक उप-आव्यूह ले सकते हैं और
का पुनर्निर्माण करने के लिए उनका उपयोग कर सकते हैं। .
एल्गोरिदम
सीयूआर आव्यूह सन्निकटन अद्वितीय नहीं है और एक की गणना के लिए कई एल्गोरिदम हैं। एक एल्गोरिथमकुर है ।[1]
"रैखिक समय सीयूआर " एल्गोरिद्म यादृच्छिक रूप से (प्रतिस्थापन के साथ) स्तंभों का चयन करके J को चुनता है जिसमें वर्गित स्तंभ मानदंडों के समानुपातिक संभाव्यता होती है, और इसी प्रकार वर्गाकार पंक्ति मानदंडों के अनुपात में I का नमूनाकरण, लेखक दिखाते हैं कि और लेकर , एल्गोरिथ्म फ्रोबेनियस एरर बाउंड प्राप्त करता है। जहां इष्टतम पद k सन्निकटन है[5]।
टेंसर
टेन्सर-कर्ट अपघटन आव्यूह -सीयूआर अपघटन का एक सामान्यीकरण है। औपचारिक रूप से, टेंसर A का कर्ट टेंसर सन्निकटन तीन मैट्रिसेस और एक (कोर-) टेंसर C, R, T और U ऐसा है कि C को A के स्तम्भ से बनाया गया है, R को A की पंक्तियों से बनाया गया है, T को ट्यूबों से बनाया गया है। A का और उत्पाद U(C,R,T) (जहाँ -इसकी प्रविष्टिनिकट से A का अनुमान लगाता है। सामान्यतः कर्ट को पद-के सन्निकटन के रूप में चुना जाता है, जो इसका अर्थ है कि C में A का k स्तम्भ है, R में A की k पंक्तियाँ हैं T में A की ट्यूब हैं और U k-by-k-by-k (कोर-) टेंसर है।[6]
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 Michael W. Mahoney; Petros Drineas. "बेहतर डेटा विश्लेषण के लिए CUR मैट्रिक्स अपघटन". Retrieved 26 June 2012.
- ↑ Boutsidis, Christos; Woodruff, David P. (2014). इष्टतम CUR मैट्रिक्स अपघटन. STOC '14 Proceedings of the forty-sixth annual ACM symposium on Theory of Computing.
- ↑ Song, Zhao; Woodruff, David P.; Zhong, Peilin (2017). प्रवेशवार एल1-मानदंड त्रुटि के साथ निम्न रैंक सन्निकटन. STOC '17 Proceedings of the forty-ninth annual ACM symposium on Theory of Computing. arXiv:1611.00898.
- ↑ Keaton Hamm and Longxiu Huang. Perspectives on CUR decompositions. Applied and Computational Harmonic Analysis, 48(3):1088–1099, 2020.
- ↑ Drineas, Petros; Kannan, Ravi; Mahoney, Michael W. (2006-01-01). "Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication". SIAM Journal on Computing. 36 (1): 132–157. doi:10.1137/S0097539704442684. ISSN 0097-5397.
- ↑ Song, Zhao; Woodruff, David P.; Zhong, Peilin (2017). "सापेक्ष त्रुटि टेन्सर निम्न रैंक सन्निकटन". arXiv:1704.08246 [cs.DS].
