Matrix Chernoff bound
રેખીય બીજગણિતમાં અમુક ઉપયોગો માટે, રેન્ડમ મેટ્રિસીસના મર્યાદિત સરવાળાના સૌથી મોટા આઈગન વેલ્યુના સંભાવના વિતરણના ગુણધર્મોને જાણવું ઉપયોગી છે. ધારો કે તે રેન્ડમ મેટ્રિસીસનો મર્યાદિત ક્રમ છે. સ્કેલર્સના સરવાળા માટે બંધાયેલા જાણીતા ચેર્નોફની જેમ, આપેલ પરિમાણ t માટે નીચેની મર્યાદા માંગવામાં આવે છેઃ નીચેના પ્રમેયો વિવિધ ધારણાઓ હેઠળ આ સામાન્ય પ્રશ્નનો જવાબ આપે છે; આ ધારણાઓને તેમના શાસ્ત્રીય, સ્કેલર સમકક્ષો સાથે સામ્યતા દ્વારા નીચે નામ આપવામાં આવ્યા છે. આ તમામ પ્રમેયો સામાન્ય પરિણામના ચોક્કસ ઉપયોગ તરીકે મળી શકે છે, જે નીચે તારવેલ છે. સંબંધિત કાર્યોનો સારાંશ આપવામાં આવ્યો છે. મેટ્રિક્સ ગૌસીયન અને રેડેમાકર શ્રેણી સ્વ-સંલગ્ન મેટ્રિક્સ કેસ પરિમાણ સાથે નિશ્ચિત, સ્વ-સંલગ્ન મેટ્રિક્સના મર્યાદિત ક્રમને ધ્યાનમાં લો, અને સ્વતંત્ર પ્રમાણભૂત સામાન્ય અથવા સ્વતંત્ર રેડેમાકર રેન્ડમ ચલોનો મર્યાદિત ક્રમ બનવા દો. પછી, બધા માટે, જ્યાં લંબચોરસ કેસ પરિમાણ સાથે નિશ્ચિત, સ્વ-સંલગ્ન મેટ્રિસીસના મર્યાદિત ક્રમને ધ્યાનમાં લો, અને ચાલો સ્વતંત્ર પ્રમાણભૂત સામાન્ય અથવા સ્વતંત્ર રેડેમાકર રેન્ડમ ચલોનો મર્યાદિત ક્રમ હોઈએ. પછી, બધા માટે, મેટ્રિક્સ ચેર્નોફ અસમાનતાઓ શાસ્ત્રીય ચેર્નોફ સીમાઓ સ્વતંત્ર, બિન-નકારાત્મક અને સમાન રીતે બંધાયેલા રેન્ડમ ચલોના સરવાળાને લગતી છે. મેટ્રિક્સ સેટિંગમાં, એનાલોગસ થીયરમ એક સમાન આઈગન વેલ્યુ બાઉન્ડને આધિન પોઝિટિવ-સેમાઇડફાઇનાઇટ રેન્ડમ મેટ્રિક્સના સરવાળાની ચિંતા કરે છે. મેટ્રિક્સ ચેર્નોફ I પરિમાણ સાથે સ્વતંત્ર, અવ્યવસ્થિત, સ્વ-સંલગ્ન મેટ્રિક્સના મર્યાદિત ક્રમને ધ્યાનમાં લો. ધારો કે દરેક રેન્ડમ મેટ્રિક્સ લગભગ ચોક્કસપણે સંતુષ્ટ કરે છે. પછી મેટ્રિક્સ ચેર્નોફ II વ્યાખ્યાયિત કરો સ્વતંત્ર, અવ્યવસ્થિત, સ્વ-સંલગ્ન મેટ્રિસીસના ક્રમનો વિચાર કરો જે લગભગ ચોક્કસપણે સંતોષ આપે છે. સરેરાશ અપેક્ષાઓના લઘુતમ અને મહત્તમ આઈગન વેલ્યુની ગણતરી કરો, પછી દ્વિસંગી માહિતીના વિચલનને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે. મેટ્રિક્સ બેનેટ અને બર્નસ્ટીન અસમાનતાઓ સ્કેલર સેટિંગમાં, બેનેટ અને બર્નસ્ટીન અસમાનતાઓ સ્વતંત્ર, શૂન્ય-અર્થ રેન્ડમ ચલોના સરવાળાની ઉપરની પૂંછડીનું વર્ણન કરે છે જે કાં તો બંધાયેલ અથવા સબએક્સપોનેન્શિયલ હોય છે. મેટ્રિક્સના કિસ્સામાં, સમાન પરિણામો શૂન્ય-અર્થ રેન્ડમ મેટ્રિક્સના સરવાળાને સંબંધિત છે. બાઉન્ડેડ કેસ પરિમાણ સાથે સ્વતંત્ર, રેન્ડમ, સ્વ-સંલગ્ન મેટ્રિસીસના મર્યાદિત ક્રમને ધ્યાનમાં લો. ધારો કે દરેક રેન્ડમ મેટ્રિક્સ લગભગ ચોક્કસપણે સંતુષ્ટ કરે છે. કુલ ભિન્નતાના ધોરણની ગણતરી કરો, પછી, અસમાનતાઓની નીચેની સાંકળ બધા માટે ધરાવે છેઃ કાર્યને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે. સબએક્સપોનેન્શલ કેસ પરિમાણ સાથે સ્વતંત્ર, અવ્યવસ્થિત, સ્વ-સંલગ્ન મેટ્રિસીસના મર્યાદિત ક્રમને ધ્યાનમાં લો. તે માટે ધારો. ભિન્નતા પરિમાણની ગણતરી કરો, પછી, અસમાનતાઓની નીચેની સાંકળ બધા માટે ધરાવે છેઃ લંબચોરસ કેસ પરિમાણ સાથે સ્વતંત્ર, રેન્ડમ, મેટ્રિસીસનો મર્યાદિત ક્રમ ધ્યાનમાં લો. ધારો કે દરેક રેન્ડમ મેટ્રિક્સ લગભગ ચોક્કસપણે સંતુષ્ટ કરે છે. પછી, બધા માટે ભિન્નતા પરિમાણને વ્યાખ્યાયિત કરો. મેટ્રિક્સ અઝુમા, હોફડિંગ અને મેકડાયર્મિડ અસમાનતાઓ મેટ્રિક્સ અઝુમા અઝુમાની અસમાનતાનું સ્કેલર વર્ઝન જણાવે છે કે સ્કેલર માર્ટિંગેલ તેના સરેરાશ મૂલ્ય વિશે સામાન્ય સાંદ્રતા દર્શાવે છે, અને વિચલનો માટેનું પ્રમાણ તફાવત ક્રમની કુલ મહત્તમ ચોરસ શ્રેણી દ્વારા નિયંત્રિત થાય છે. મેટ્રિક્સ સેટિંગમાં નીચેનું વિસ્તરણ છે. પરિમાણ સાથે સ્વ-સંલગ્ન મેટ્રિસીસનો મર્યાદિત અનુકૂલિત ક્રમ અને લગભગ ચોક્કસપણે સંતોષતા સ્વ-સંયુક્ત મેટ્રિસીસનો નિશ્ચિત ક્રમ ધ્યાનમાં લો. ભિન્નતા પરિમાણની ગણતરી કરો પછી, બધા માટે જ્યારે વધારાની માહિતી ઉપલબ્ધ હોય ત્યારે અચળાંક 1/8 ને સુધારીને 1/2 કરી શકાય છે. એક કેસ ત્યારે થાય છે જ્યારે દરેક સરવાળો શરતી રીતે સપ્રમાણ હોય. અન્ય એક ઉદાહરણ માટે એવી ધારણાની જરૂર છે જે લગભગ ચોક્કસપણે સાથે મુસાફરી કરે છે. મેટ્રિક્સ હોફડિંગ પ્લેસમેન્ટ એડિશન ધારણા કે મેટ્રિક્સ અઝુમામાં સરવાળા સ્વતંત્ર છે તે હોફડિંગની અસમાનતાઓનું મેટ્રિક્સ વિસ્તરણ આપે છે. પરિમાણ સાથે સ્વતંત્ર, અવ્યવસ્થિત, સ્વ-સંલગ્ન મેટ્રિસીસના મર્યાદિત ક્રમને ધ્યાનમાં લો, અને નિશ્ચિત સ્વ-સંલગ્ન મેટ્રિસીસનો ક્રમ બનવા દો. ધારો કે દરેક રેન્ડમ મેટ્રિક્સ લગભગ ચોક્કસપણે સંતુષ્ટ કરે છે. પછી, બધા માટે જ્યાં આ પરિણામમાં સુધારો સ્થાપિત કરવામાં આવ્યો હતોઃ બધા માટે જ્યાં મેટ્રિક્સ બાઉન્ડેડ તફાવત (મેકડિયારમિડ) સ્કેલર સેટિંગમાં, મેકડિયારમિડની અસમાનતા અઝુમાની અસમાનતાને ડૂબ માર્ટીંગેલ પર લાગુ કરીને તફાવતોને બંધાવવાની એક સામાન્ય રીત પ્રદાન કરે છે. બંધાયેલ તફાવતોની અસમાનતાનું સંસ્કરણ મેટ્રિક્સ સેટિંગમાં છે. ચાલો એક સ્વતંત્ર, રેન્ડમ વેરિયેબલ્સનો પરિવાર બનીએ, અને ચાલો એક એવું કાર્ય બનીએ જે પરિમાણના સ્વ-સંલગ્ન મેટ્રિક્સમાં વેરિયેબલ્સનો નકશો બનાવે છે. નિશ્ચિત સ્વ-સંલગ્ન મેટ્રિસીસના ક્રમને ધ્યાનમાં લો જે દરેક અનુક્રમણિકાના તમામ સંભવિત મૂલ્યોને ક્યાં અને ક્યાં સંતોષ આપે છે. પછી, બધી જગ્યાઓ માટે ભિન્નતા પરિમાણની ગણતરી કરો. આ પરિણામમાં સુધારો સ્થાપિત કરવામાં આવ્યો હતો (આ પણ જુઓ): બધા માટે ક્યાં અને સંબંધિત પ્રમેયોનો સર્વે આ પ્રકારની પ્રથમ સીમાઓ આના દ્વારા મેળવવામાં આવી હતી. સેલ્ફ-એડજોઈન્ટ મેટ્રિક્સ ગૌસીયન અને રેડેમાકર બાઉન્ડ્સ માટે ઉપરના પ્રમેયને યાદ કરી લોઃ પરિમાણ સાથે નિશ્ચિત, સેલ્ફ-એડજોઈન્ટ મેટ્રિક્સના મર્યાદિત ક્રમ માટે અને સ્વતંત્ર પ્રમાણભૂત સામાન્ય અથવા સ્વતંત્ર રેડેમાકર રેન્ડમ વેરિયેબલ્સના મર્યાદિત ક્રમ માટે, પછી જ્યાં અહલ્સ્વેડ અને વિન્ટર સમાન પરિણામ આપશે, સિવાય કે. તુલનાત્મક રીતે, ઉપરના પ્રમેયમાં કોમ્યુટ્સ અને; એટલે કે, તે સૌથી મોટા આઈગનવેલ્યુના સરવાળાને બદલે સરવાળાનું સૌથી મોટું આઈગનવેલ્યુ છે. તે અહલ્સ્વેડ-વિન્ટર મૂલ્ય (સામાન્ય ત્રિકોણ અસમાનતા દ્વારા) કરતા ક્યારેય મોટું નથી, પરંતુ તે ઘણું નાનું હોઈ શકે છે. તેથી, ઉપરનું પ્રમેય અહલસ્વેડ-વિન્ટર પરિણામ કરતાં વધુ કડક બાઉન્ડ આપે છે. તેનું મુખ્ય યોગદાન સ્વ-સંલગ્ન મેટ્રિસીસના કિસ્સામાં સ્કેલર ચેર્નોફ બાઉન્ડ (ચેર્નોફ bound#Additive ફોર્મ (સંપૂર્ણ ભૂલ) જુઓ) ને સાબિત કરવા માટે ઉપયોગમાં લેવાતી લાપ્લાસ-ટ્રાન્સફોર્મ પદ્ધતિનું વિસ્તરણ હતું. નીચેની વ્યુત્પત્તિમાં આપવામાં આવેલી પ્રક્રિયા. આ વિષય પરની તમામ તાજેતરની કૃતિઓ આ જ પ્રક્રિયાને અનુસરે છે, અને મુખ્ય તફાવતો અનુગામી પગલાઓથી અનુસરે છે. અહ્લસ્વેડ અને વિન્ટર આગળ વધવા માટે ગોલ્ડન-થોમ્પસન અસમાનતાનો ઉપયોગ કરે છે, જ્યારે ટ્રોપ લીબના પ્રમેયનો ઉપયોગ કરે છે. ધારો કે કોઈ વ્યક્તિ જમણી બાજુને લગભગ સ્થિર રાખીને શ્રેણી (n) ની લંબાઈ અને મેટ્રિસીસ (d) ના પરિમાણોમાં ફેરફાર કરવા માંગે છે. પછી n એ લગભગ d ના લોગ તરીકે બદલાતો હોવો જોઈએ. કેટલાક કાગળોએ પરિમાણો પર નિર્ભરતા વિના બાઉન્ડ સ્થાપિત કરવાનો પ્રયાસ કર્યો છે. રુડેલ્સન અને વર્શિનિન મેટ્રિસીસ માટે પરિણામ આપે છે જે બે વેક્ટરનું બાહ્ય ઉત્પાદન છે. નીચા ક્રમના મેટ્રિસીસ માટે પરિમાણીય અવલંબન વિના પરિણામ પ્રદાન કરે છે. મૂળ પરિણામ અહ્લસ્વેડ-વિન્ટર અભિગમમાંથી સ્વતંત્ર રીતે મેળવવામાં આવ્યું હતું, પરંતુ અહ્લસ્વેડ-વિન્ટર અભિગમનો ઉપયોગ કરીને સમાન પરિણામ સાબિત કરે છે. છેવટે, ઓલિવેરા એ એલસ્વેડ-વિન્ટર ફ્રેમવર્કથી સ્વતંત્ર રીતે મેટ્રિક્સ માર્ટિંગેલ્સ માટે પરિણામ સાબિત કરે છે. એહલ્સ્વેડ-વિન્ટર ફ્રેમવર્કનો ઉપયોગ કરીને ટ્રોપ પરિણામમાં થોડો સુધારો કરે છે. આ લેખમાં કોઈ પરિણામ રજૂ કરવામાં આવ્યું નથી. વ્યુત્પત્તિ અને સાબિતી અહલસ્વેડ અને વિન્ટર લાપ્લાસ ટ્રાન્સફોર્મ દલીલ તેના પોતાના અધિકારમાં નોંધપાત્ર પરિણામ છેઃ ચાલો રેન્ડમ સ્વ-સંલગ્ન મેટ્રિક્સ બનીએ. પછી આ સાબિત કરવા માટે, તેને ઠીક કરો. પછી બીજીથી છેલ્લી અસમાનતા માર્કોવની અસમાનતા છે. છેલ્લી અસમાનતા ત્યારથી ચાલુ છે. ડાબી બાજુની સૌથી વધુ માત્રા તેનાથી સ્વતંત્ર હોવાથી, અનંત ઓવર તેના માટે ઉપલી સીમા રહે છે. આમ, આપણું કાર્ય સમજવાનું છે તેમ છતાં, ટ્રેસ અને અપેક્ષા બંને રેખીય હોવાથી, આપણે તેમને પરિવર્તિત કરી શકીએ છીએ, તેથી તે ધ્યાનમાં લેવા માટે પૂરતું છે, જેને આપણે મેટ્રિક્સ જનરેટિંગ ફંક્શન કહીએ છીએ. આ તે છે જ્યાં પદ્ધતિઓ અલગ પડે છે. તરત જ નીચેની પ્રસ્તુતિ અનુસરે છે. ગોલ્ડન-થોમ્પસન અસમાનતા સૂચવે છે કે, જ્યાં આપણે અપેક્ષાઓની રેખીયતાનો ઘણી વખત ઉપયોગ કર્યો હતો. ધારો. આ પરિણામનું પુનરાવર્તન કરીને આપણે ઉપરની સીમા શોધી શકીએ છીએ. નોંધ્યું છે કે, પછી આનું પુનરાવર્તન કરીને, આપણે મેળવીએ છીએ અત્યાર સુધી આપણે અનંત ઓવર સાથે બાઉન્ડ શોધી કાઢ્યું છે. બદલામાં, આને મર્યાદિત કરી શકાય છે. કોઈપણ રીતે, કોઈ પણ જોઈ શકે છે કે અહલ્સ્વેડ-વિન્ટર બાઉન્ડ સૌથી મોટા આઈગનવેલ્યુના સરવાળા તરીકે કેવી રીતે ઉદ્ભવે છે. ટ્રોપનું મુખ્ય યોગદાન લિબના પ્રમેયનો ઉપયોગ છે જ્યાં ગોલ્ડન-થોમ્પસન અસમાનતાને લાગુ કરવામાં આવી હતી. ટ્રોપનો પરિણામ નીચે મુજબ છેઃ જો તે એક નિશ્ચિત સ્વ-સંલગ્ન મેટ્રિક્સ હોય અને એક અવ્યવસ્થિત સ્વ-સંલગ્ન મેટ્રિક્સ હોય, તો પુરાવોઃ ચાલો. પછી લીબનો પ્રમેય આપણને કહે છે કે તે અંતર્મુખ છે. અંતિમ પગલું ફંક્શનની અંદર અપેક્ષા ખસેડવા માટે જેનસનની અસમાનતાનો ઉપયોગ કરવાનો છેઃ આ આપણને પેપરનું મુખ્ય પરિણામ આપે છેઃ મેટ્રિક્સ જનરેટિંગ ફંક્શનના લોગની સબએડિટીવિટી. લોગ mgf ની સબએડિટિવિટી ચાલો સ્વતંત્ર, રેન્ડમ સેલ્ફ-એડજોઈન્ટ મેટ્રિસીસનો મર્યાદિત ક્રમ હોઈએ. પછી બધા માટે, પુરાવોઃ તે આપવા માટે પૂરતું છે. વ્યાખ્યાઓને વિસ્તૃત કરીને, આપણે બતાવવાની જરૂર છે કે સાબિતી પૂર્ણ કરવા માટે, આપણે કુલ અપેક્ષાઓના કાયદાનો ઉપયોગ કરીએ છીએ. અપેક્ષા શરતી હોવી જોઈએ. કારણ કે આપણે ધારીએ છીએ કે બધા સ્વતંત્ર છે, વ્યાખ્યાયિત કરો. છેવટે, આપણી પાસે છે જ્યાં દરેક પગલા m પર આપણે માસ્ટર ટેલ બાઉન્ડ સાથે ટ્રોપના ઉપસંહારનો ઉપયોગ કરીએ છીએ. નીચેના અગાઉના પરિણામથી તાત્કાલિક છેઃ ઉપર આપેલા તમામ પ્રમેયો આ બાઉન્ડમાંથી મેળવવામાં આવ્યા છે; પ્રમેયો અનંતને બાંધવા માટે વિવિધ રીતે બનેલો છે. આ પગલાંઓ આપેલા પુરાવાઓ કરતાં નોંધપાત્ર રીતે સરળ છે. સંદર્ભો રેખીય બીજગણિત