Matrix Chernoff bound
रैखिक बीजगणित में कुछ अनुप्रयोगों के लिए, यादृच्छिक मैट्रिक्स के एक सीमित योग के सबसे बड़े आइगेनवैल्यू के प्रायिकता वितरण के गुणों को जानना उपयोगी है। मान लीजिए कि यह यादृच्छिक मैट्रिक्स का एक परिमित अनुक्रम है। स्केलर्स के योग के लिए प्रसिद्ध चेर्नोफ बाउंड के अनुरूप, दिए गए पैरामीटर टी के लिए निम्नलिखित पर एक बाउंड की मांग की जाती हैः निम्नलिखित प्रमेय विभिन्न मान्यताओं के तहत इस सामान्य प्रश्न का उत्तर देते हैं; इन धारणाओं को उनके शास्त्रीय, स्केलर समकक्षों के अनुरूप नीचे नाम दिया गया है। इन सभी प्रमेयों को एक सामान्य परिणाम के विशिष्ट अनुप्रयोग के रूप में पाया जा सकता है जो नीचे दिया गया है। संबंधित कार्यों का सारांश दिया गया है। मैट्रिक्स गॉसियन और रेडेमाकर श्रृंखला स्व-संयुक्त मैट्रिक्स मामले आयाम के साथ निश्चित, स्व-संयुक्त मैट्रिक्स के एक सीमित अनुक्रम पर विचार करें, और स्वतंत्र मानक सामान्य या स्वतंत्र रेडेमाकर यादृच्छिक चर का एक सीमित अनुक्रम होने दें। फिर, सभी के लिए, जहां आयताकार मामले आयाम के साथ निश्चित, स्व-एडजॉइंट मैट्रिक्स के एक सीमित अनुक्रम पर विचार करें, और स्वतंत्र मानक सामान्य या स्वतंत्र रेडमेकर यादृच्छिक चर का एक सीमित अनुक्रम होने दें। फिर, सभी के लिए, मैट्रिक्स चेरनोफ़ असमानताएँ शास्त्रीय चेरनोफ़ सीमाएँ स्वतंत्र, गैर-नकारात्मक और समान रूप से बंधे यादृच्छिक चर के योग से संबंधित हैं। मैट्रिक्स सेटिंग में, एनालॉगस थ्योरम एक समान आइगेनवैल्यू बाउंड के अधीन पॉजिटिव-सेमाइडफाइनाइट यादृच्छिक मैट्रिक्स के योग से संबंधित है। मैट्रिक्स चेरनोफ I आयाम के साथ स्वतंत्र, यादृच्छिक, स्व-संयुक्त मैट्रिक्स के एक सीमित अनुक्रम पर विचार करें। मान लीजिए कि प्रत्येक यादृच्छिक मैट्रिक्स लगभग निश्चित रूप से संतुष्ट करता है। फिर मैट्रिक्स चेरनोफ II को परिभाषित करें स्वतंत्र, यादृच्छिक, स्व-संयुक्त मैट्रिक्स के एक अनुक्रम पर विचार करें जो लगभग निश्चित रूप से संतुष्ट करते हैं। औसत अपेक्षा के न्यूनतम और अधिकतम आइगेनवैल्यू की गणना करें, फिर द्विआधारी सूचना विचलन को परिभाषित किया जाता है। मैट्रिक्स बेनेट और बर्नस्टीन असमानताएँ स्केलर सेटिंग में, बेनेट और बर्नस्टीन असमानताएँ स्वतंत्र, शून्य-अर्थ यादृच्छिक चर के योग की ऊपरी पूंछ का वर्णन करती हैं जो या तो बंधे हुए हैं या उप-घातीय हैं। मैट्रिक्स के मामले में, अनुरूप परिणाम शून्य-अर्थ यादृच्छिक मैट्रिक्स के योग से संबंधित हैं। बाउंडेड केस आयाम के साथ स्वतंत्र, यादृच्छिक, स्व-संयुक्त मैट्रिक्स के एक सीमित अनुक्रम पर विचार करें। मान लीजिए कि प्रत्येक यादृच्छिक मैट्रिक्स लगभग निश्चित रूप से संतुष्ट करता है। कुल विचरण के मानक की गणना करें, फिर, असमानताओं की निम्नलिखित श्रृंखला सभी के लिए लागू होती हैः कार्य को परिभाषित किया गया है। सबएक्सपोनेंशियल केस आयाम के साथ स्वतंत्र, यादृच्छिक, स्व-एडजॉइंट मैट्रिक्स के एक सीमित अनुक्रम पर विचार करें। इसके लिए मान लीजिए। भिन्नता पैरामीटर की गणना करें, फिर, असमानताओं की निम्नलिखित श्रृंखला सभी के लिए होती हैः आयताकार मामले आयाम के साथ स्वतंत्र, यादृच्छिक, मैट्रिक्स के एक सीमित अनुक्रम पर विचार करें। मान लीजिए कि प्रत्येक यादृच्छिक मैट्रिक्स लगभग निश्चित रूप से संतुष्ट करता है। फिर, सभी धारणों के लिए विचरण मापदंड को परिभाषित करें। मैट्रिक्स एज़ुमा, होफ़्डिंग और मैक्डियारमिड असमानताएँ मैट्रिक्स एज़ुमा एज़ुमा की असमानता के स्केलर संस्करण में कहा गया है कि एक स्केलर मार्टिंगेल अपने औसत मूल्य के बारे में सामान्य एकाग्रता प्रदर्शित करता है, और विचलन के लिए पैमाने को अंतर अनुक्रम की कुल अधिकतम वर्ग सीमा द्वारा नियंत्रित किया जाता है। मैट्रिक्स सेटिंग में निम्नलिखित विस्तार है। आयाम के साथ स्व-संयुक्त मैट्रिक्स के एक सीमित अनुकूलित अनुक्रम पर विचार करें, और स्व-संयुक्त मैट्रिक्स के एक निश्चित अनुक्रम पर विचार करें जो लगभग निश्चित रूप से संतुष्ट करते हैं। भिन्नता पैरामीटर की गणना करें फिर, सभी के लिए जब अतिरिक्त जानकारी उपलब्ध हो तो 1/8 स्थिरांक को 1/2 तक बढ़ाया जा सकता है। एक मामला तब होता है जब प्रत्येक योग सशर्त रूप से सममित होता है। एक अन्य उदाहरण के लिए उस धारणा की आवश्यकता होती है जो लगभग निश्चित रूप से साथ चलती है। मैट्रिक्स होफ़्डिंग प्लेसिंग जोड़ धारणा कि मैट्रिक्स आज़ूमा में योग स्वतंत्र हैं, होफ़्डिंग की असमानताओं का एक मैट्रिक्स विस्तार देता है। आयाम के साथ स्वतंत्र, यादृच्छिक, स्व-संयुग्म मैट्रिक्स के एक सीमित अनुक्रम पर विचार करें, और निश्चित स्व-संयुग्म मैट्रिक्स का एक अनुक्रम होने दें। मान लीजिए कि प्रत्येक यादृच्छिक मैट्रिक्स लगभग निश्चित रूप से संतुष्ट करता है। फिर, उन सभी के लिए जहां इस परिणाम में सुधार स्थापित किया गया थाः उन सभी के लिए जहां मैट्रिक्स बाउंडेड डिफरेंस (मैक्डियारमिड) स्केलर सेटिंग में, मैक्डियारमिड की असमानता अज़ुमा की असमानता को डूब मार्टिंगेल पर लागू करके मतभेदों को सीमित करने का एक सामान्य तरीका प्रदान करती है। सीमित अंतर असमानता का एक संस्करण मैट्रिक्स सेटिंग में होता है। मान लीजिए कि यह यादृच्छिक चरों का एक स्वतंत्र परिवार है, और मान लीजिए कि यह एक ऐसा कार्य है जो चरों को आयाम के एक स्व-संयुक्त मैट्रिक्स में मानचित्रित करता है। निश्चित स्व-संयोजन मैट्रिक्स के एक अनुक्रम पर विचार करें जो प्रत्येक सूचकांक के लिए सभी संभावित मूल्यों को संतुष्ट करते हैं और उनकी सीमा तय करते हैं। भिन्नता पैरामीटर की गणना करें फिर, सभी जगह के लिए। इस परिणाम में सुधार स्थापित किया गया था (यह भी देखें): सभी के लिए कहाँ और संबंधित प्रमेयों का सर्वेक्षण इस प्रकार की पहली सीमाएँ इसके द्वारा प्राप्त की गई थीं। स्व-संयुक्त मैट्रिक्स गॉसियन और रेडमेकर सीमाओं के लिए उपरोक्त प्रमेय को याद करेंः आयाम के साथ निश्चित, स्व-संयुक्त मैट्रिक्स के एक सीमित अनुक्रम के लिए और स्वतंत्र मानक सामान्य या स्वतंत्र रेडमेकर यादृच्छिक चर के एक सीमित अनुक्रम के लिए, जहां अहल्स्वेड और विंटर समान परिणाम देंगे, सिवाय इसके। तुलनात्मक रूप से, उपरोक्त प्रमेय में कम्यूट्स और; अर्थात, यह सबसे बड़े आइगेनवैल्यूज के योग के बजाय योग का सबसे बड़ा आइगेनवैल्यू है। यह कभी भी अहलस्वेड-विंटर मान (मानक त्रिभुज असमानता द्वारा) से बड़ा नहीं होता है, लेकिन बहुत छोटा हो सकता है। इसलिए, उपरोक्त प्रमेय अहलस्वेड-विंटर परिणाम की तुलना में एक सख्त सीमा देता है। इसका मुख्य योगदान लाप्लास-परिवर्तन विधि का विस्तार था जिसका उपयोग स्केलर चेरनोफ बाउंड को साबित करने के लिए किया जाता था (देखें चेरनोफ bound#Additive फॉर्म (पूर्ण त्रुटि)) आत्म-संयुक्त मैट्रिक्स के मामले में। निम्नलिखित व्युत्पत्ति में दी गई प्रक्रिया। इस विषय पर हाल के सभी कार्य इसी प्रक्रिया का पालन करते हैं, और मुख्य अंतर बाद के चरणों का अनुसरण करते हैं। अहलस्वेड और विंटर आगे बढ़ने के लिए गोल्डन-थॉम्पसन असमानता का उपयोग करते हैं, जबकि ट्रॉप लीब के प्रमेय का उपयोग करते हैं। मान लीजिए कि कोई दाहिने हाथ की ओर लगभग स्थिर रखते हुए श्रृंखला (एन) की लंबाई और मैट्रिक्स (डी) के आयामों को बदलना चाहता है। फिर n लगभग d के लॉग के रूप में भिन्न होना चाहिए। कई पत्रों ने आयामों पर निर्भरता के बिना एक सीमा स्थापित करने का प्रयास किया है। रुडेल्सन और वर्शिनिन मैट्रिक्स के लिए एक परिणाम देते हैं जो दो वैक्टरों का बाहरी उत्पाद हैं। निम्न श्रेणी के मैट्रिक्स के लिए आयामी निर्भरता के बिना परिणाम प्रदान करें। मूल परिणाम अहलस्वेड-विंटर दृष्टिकोण से स्वतंत्र रूप से प्राप्त किया गया था, लेकिन अहलस्वेड-विंटर दृष्टिकोण का उपयोग करके एक समान परिणाम साबित करता है। अंत में, ओलिवेरा अहल्स्वेड-विंटर फ्रेमवर्क से स्वतंत्र रूप से मैट्रिक्स मार्टिंगेल्स के लिए एक परिणाम साबित करता है। ट्रॉप अहलस्वेड-विंटर ढांचे का उपयोग करके परिणाम में थोड़ा सुधार करता है। इस लेख में कोई भी परिणाम प्रस्तुत नहीं किया गया है। व्युत्पत्ति और प्रमाण अहलस्वेड और विंटर लाप्लास परिवर्तन तर्क अपने आप में एक महत्वपूर्ण परिणाम हैः मान लीजिए कि यह एक यादृच्छिक स्व-संयोजन मैट्रिक्स है। फिर इसे साबित करने के लिए, ठीक करें। फिर दूसरी से अंतिम असमानता मार्कोव की असमानता है। अंतिम असमानता तब से बनी हुई है। चूँकि सबसे बाएँ हिस्से की मात्रा स्वतंत्र होती है, इसलिए इसके लिए अधिकतम सीमा ऊपरी सीमा बनी रहती है। इस प्रकार, हमारा कार्य यह समझना है कि ट्रेस और एक्सपेक्टेशन दोनों रैखिक हैं, इसलिए हम उन्हें कम्यूट कर सकते हैं, इसलिए यह विचार करने के लिए पर्याप्त है, जिसे हम मैट्रिक्स जनरेटिंग फंक्शन कहते हैं। यही वह जगह है जहाँ के तरीके अलग-अलग होते हैं। इसके तुरंत बाद की प्रस्तुति आगे आती है। गोल्डन-थॉम्पसन असमानता का तात्पर्य है कि, जहाँ हमने कई बार अपेक्षा की रैखिकता का उपयोग किया। मान लीजिए। हम इस परिणाम को दोहराकर एक ऊपरी सीमा पा सकते हैं। यह देखते हुए कि, फिर इसे दोहराते हुए, हम प्राप्त करते हैं अब तक हमने एक असीम ओवर के साथ एक सीमा पाई है। बदले में, इसे सीमित किया जा सकता है। किसी भी दर पर, यह देखा जा सकता है कि कैसे अहलस्वेड-विंटर बाउंड सबसे बड़े आइगेनवैल्यूज के योग के रूप में उत्पन्न होता है। ट्रॉप का प्रमुख योगदान लिब के प्रमेय का अनुप्रयोग है जहाँ गोल्डन-थॉम्पसन असमानता को लागू किया गया था। ट्रॉप का परिणाम निम्नलिखित हैः यदि एक निश्चित स्व-संयोजन मैट्रिक्स है और एक यादृच्छिक स्व-संयोजन मैट्रिक्स है, तो प्रमाणः मान लीजिए। फिर लीब की प्रमेय हमें बताती है कि यह अवतल है। अंतिम चरण फ़ंक्शन के अंदर अपेक्षा को स्थानांतरित करने के लिए जेन्सेन की असमानता का उपयोग करना हैः यह हमें पेपर का प्रमुख परिणाम देता हैः मैट्रिक्स उत्पन्न करने वाले फ़ंक्शन के लॉग की उप-योजकता। लॉग एम. जी. एफ. की उप-संयोजनशीलता मान लीजिए कि यह स्वतंत्र, यादृच्छिक स्व-संयोजन मैट्रिक्स का एक सीमित अनुक्रम है। फिर सभी के लिए, प्रमाणः यह देने के लिए पर्याप्त है। परिभाषाओं का विस्तार करते हुए, हमें यह दिखाने की आवश्यकता है कि प्रमाण को पूरा करने के लिए, हम कुल अपेक्षा के नियम का उपयोग करते हैं। उम्मीद को शर्तित होने दें। चूँकि हम मानते हैं कि सभी स्वतंत्र हैं, परिभाषित करें। अंत में, हमारे पास है जहाँ प्रत्येक चरण m पर हम मास्टर टेल बाउंड के साथ ट्रॉप के कोरोलरी का उपयोग करते हैं। निम्नलिखित पिछले परिणाम से तत्काल हैः ऊपर दिए गए सभी प्रमेय इस सीमा से प्राप्त होते हैं; प्रमेय अनंत को बांधने के लिए विभिन्न तरीकों से बने होते हैं। ये कदम दिए गए प्रमाणों की तुलना में काफी सरल हैं। संदर्भ रैखिक बीजगणित