Matrix Chernoff bound
لکیری الجبرا میں بعض ایپلی کیشنز کے لیے، بے ترتیب میٹرکس کے محدود مجموعے کی سب سے بڑی آئجن ویلیو کی امکانات کی تقسیم کی خصوصیات کو جاننا مفید ہے۔ فرض کریں کہ یہ بے ترتیب میٹرکس کی ایک محدود ترتیب ہے۔ اسکیلرز کے مجموعوں کے لیے پابند معروف چرنوف کے مترادف، ایک دیئے گئے پیرامیٹر t کے لیے درج ذیل پر ایک باؤنڈ طلب کیا جاتا ہے: درج ذیل تھیوریمز مختلف مفروضوں کے تحت اس عام سوال کا جواب دیتے ہیں۔ ان مفروضوں کو ذیل میں ان کے کلاسیکی، اسکیلر ہم منصبوں سے مشابہت کے ذریعے نامزد کیا گیا ہے۔ ان تمام نظریات کو ایک عام نتیجہ کے مخصوص اطلاق کے طور پر پایا جا سکتا ہے جو ذیل میں اخذ کیا گیا ہے۔ متعلقہ کاموں کا خلاصہ دیا گیا ہے۔ میٹرکس گوسیئن اور ریڈماچر سیریز سیلف ایڈجوائنٹ میٹرکس کیس طول و عرض کے ساتھ فکسڈ، سیلف ایڈجوائنٹ میٹرکس کی ایک محدود ترتیب پر غور کریں، اور آزاد معیاری نارمل یا آزاد ریڈماچر بے ترتیب متغیرات کی ایک محدود ترتیب ہونے دیں۔ پھر، سب کے لیے، جہاں مستطیل صورت طول و عرض کے ساتھ فکسڈ، سیلف ایڈجوائنٹ میٹرکس کی ایک محدود ترتیب پر غور کریں، اور آزاد معیاری نارمل یا آزاد ریڈماچر بے ترتیب متغیرات کی ایک محدود ترتیب ہونے دیں۔ تغیر کے پیرامیٹر کی وضاحت کریں پھر، سب کے لیے، میٹرکس چرنوف کی عدم مساوات کلاسیکی چرنوف کی حدود آزاد، غیر منفی، اور یکساں طور پر پابند بے ترتیب متغیرات کے مجموعے سے متعلق ہیں۔ میٹرکس کی ترتیب میں، اینالاگس تھیوریم ایک یکساں آئجن ویلیو باؤنڈ کے تابع مثبت-سیمیڈفائنٹ بے ترتیب میٹرکس کے مجموعے سے متعلق ہے۔ میٹرکس چرنوف I طول و عرض کے ساتھ آزاد، بے ترتیب، خود سے منسلک میٹرکس کی ایک محدود ترتیب پر غور کریں۔ فرض کریں کہ ہر بے ترتیب میٹرکس تقریبا یقینی طور پر مطمئن کرتا ہے۔ پھر میٹرکس چرنوف II کی وضاحت کریں آزاد، بے ترتیب، خود سے منسلک میٹرکس کی ایک ترتیب پر غور کریں جو تقریبا یقینی طور پر مطمئن کرتی ہے۔ اوسط توقع کی کم از کم اور زیادہ سے زیادہ آئجن ویلیوز کا حساب لگائیں، پھر بائنری معلومات کے انحراف کی تعریف اس طرح کی جاتی ہے۔ میٹرکس بینیٹ اور برنسٹین کی عدم مساوات اسکیلر ترتیب میں، بینیٹ اور برنسٹین کی عدم مساوات آزاد، صفر معنی کے بے ترتیب متغیرات کے مجموعے کی اوپری دم کو بیان کرتی ہیں جو یا تو پابند ہیں یا ذیلی متغیر ہیں۔ میٹرکس کے معاملے میں، مماثل نتائج کا تعلق صفر معنی کے بے ترتیب میٹرکس کے مجموعے سے ہے۔ باؤنڈڈ کیس طول و عرض کے ساتھ آزاد، بے ترتیب، سیلف ایڈجائنٹ میٹرکس کی ایک محدود ترتیب پر غور کریں۔ فرض کریں کہ ہر بے ترتیب میٹرکس تقریبا یقینی طور پر مطمئن کرتا ہے۔ کل تغیر کے معیار کا حساب لگائیں، پھر، عدم مساوات کا درج ذیل سلسلہ سب کے لیے ہے: فنکشن کی تعریف اس طرح کی گئی ہے۔ سب ایکسپونینشیل کیس طول و عرض کے ساتھ آزاد، بے ترتیب، سیلف ایڈجوائنٹ میٹرکس کی ایک محدود ترتیب پر غور کریں۔ اس کے لیے فرض کریں۔ تغیر پیرامیٹر کا حساب لگائیں، پھر، عدم مساوات کا درج ذیل سلسلہ سب کے لیے ہے: آئتاکار صورت طول و عرض کے ساتھ آزاد، بے ترتیب، میٹرکس کی ایک محدود ترتیب پر غور کریں۔ فرض کریں کہ ہر بے ترتیب میٹرکس تقریبا یقینی طور پر مطمئن کرتا ہے۔ تغیر پیرامیٹر کی وضاحت کریں پھر، تمام ہولڈز کے لیے۔ میٹرکس ازوما، ہوفڈنگ، اور میکڈیرمڈ عدم مساوات میٹرکس ازوما کی عدم مساوات کے اسکیلر ورژن میں کہا گیا ہے کہ ایک اسکیلر مارٹنگیل اپنی اوسط قیمت کے بارے میں معمول کی حراستی ظاہر کرتا ہے، اور انحراف کے پیمانے کو فرق کی ترتیب کی کل زیادہ سے زیادہ مربع رینج کے ذریعے کنٹرول کیا جاتا ہے۔ میٹرکس کی ترتیب میں توسیع درج ذیل ہے۔ طول و عرض کے ساتھ سیلف ایڈجائنٹ میٹرکس کی ایک محدود موافقت شدہ ترتیب، اور سیلف ایڈجائنٹ میٹرکس کی ایک مقررہ ترتیب پر غور کریں جو تقریبا یقینی طور پر مطمئن کرتی ہے۔ تغیر پیرامیٹر کا حساب لگائیں پھر، تمام کے لیے مستقل 1/8 کو 1/2 تک بہتر بنایا جا سکتا ہے جب اضافی معلومات دستیاب ہوں۔ ایک معاملہ اس وقت ہوتا ہے جب ہر خلاصہ مشروط طور پر ہم آہنگ ہوتا ہے۔ ایک اور مثال میں اس مفروضے کی ضرورت ہوتی ہے جو تقریبا یقینی طور پر اس کے ساتھ سفر کرتا ہے۔ میٹرکس ہوفڈنگ پلیسنگ ایڈیشن کا یہ مفروضہ کہ میٹرکس ازوما میں خلاصہ آزاد ہیں، ہوفڈنگ کی عدم مساوات کی میٹرکس توسیع دیتا ہے۔ طول و عرض کے ساتھ آزاد، بے ترتیب، سیلف ایڈجوائنٹ میٹرکس کی ایک محدود ترتیب پر غور کریں، اور طے شدہ سیلف ایڈجوائنٹ میٹرکس کی ایک ترتیب ہونے دیں۔ فرض کریں کہ ہر بے ترتیب میٹرکس تقریبا یقینی طور پر مطمئن کرتا ہے۔ پھر، ان سب کے لیے جہاں اس نتیجے میں بہتری قائم کی گئی تھی: ان سب کے لیے جہاں میٹرکس نے فرق کو محدود کیا (میکڈیرمڈ) اسکیلر ترتیب میں، میکڈیرمڈ کی عدم مساوات ازوما کی عدم مساوات کو ڈوب مارٹنگیل پر لاگو کرکے اختلافات کو محدود کرنے کا ایک مشترکہ طریقہ فراہم کرتی ہے۔ محدود اختلافات کی عدم مساوات کا ایک ورژن میٹرکس کی ترتیب میں ہوتا ہے۔ ایک آزاد، بے ترتیب متغیرات کا خاندان بننے دیں، اور ایک ایسا فنکشن بننے دیں جو متغیرات کو طول و عرض کے سیلف ایڈجوائنٹ میٹرکس میں نقشہ بناتا ہے۔ فکسڈ سیلف ایڈجائنٹ میٹرکس کی ایک ترتیب پر غور کریں جو ہر انڈیکس کے لیے تمام ممکنہ اقدار پر کہاں اور رینج کو پورا کرتی ہے۔ تغیر پیرامیٹر کا حساب لگائیں پھر، تمام جگہوں کے لیے۔ اس نتیجے میں بہتری قائم کی گئی تھی (یہ بھی دیکھیں): سب کے لیے جہاں اور متعلقہ نظریات کا سروے اس قسم کی پہلی حدود سے اخذ کی گئی تھیں۔ سیلف ایڈجوائنٹ میٹرکس گوسیئن اور ریڈماچر باؤنڈز کے لیے اوپر دیے گئے تھیوریم کو یاد کریں: طول و عرض کے ساتھ فکسڈ، سیلف ایڈجوائنٹ میٹرکس کی ایک محدود ترتیب کے لیے اور آزاد معیاری نارمل یا آزاد ریڈماچر بے ترتیب متغیرات کی ایک محدود ترتیب کے لیے، جہاں ایہلسویڈ اور ونٹر ایک ہی نتیجہ دیں گے، سوائے اس کے کہ۔ اس کے مقابلے میں، مندرجہ بالا تھیوریم میں کمیوٹس اور ؛ یعنی، یہ سب سے بڑی آئجن ویلیوز کے مجموعے کے بجائے رقم کی سب سے بڑی آئجن ویلیو ہے۔ یہ ایہلسویڈ-ونٹر ویلیو (عام مثلث عدم مساوات کے لحاظ سے) سے کبھی بڑا نہیں ہوتا، لیکن بہت چھوٹا ہو سکتا ہے۔ لہذا، اوپر کا نظریہ ایہلسویڈ-ونٹر کے نتیجے سے زیادہ سخت باؤنڈ دیتا ہے۔ کی اہم شراکت لیپلیس-ٹرانسفارم طریقہ کار کی توسیع تھی جو اسکیلر چرنوف باؤنڈ کو ثابت کرنے کے لیے استعمال ہوتی تھی (دیکھیں چرنوف bound#Additive فارم (مطلق غلطی)) سیلف ایڈجوائنٹ میٹرکس کے معاملے میں۔ مندرجہ ذیل مشتق میں دیا گیا طریقہ کار۔ اس موضوع پر تمام حالیہ کام اسی طریقہ کار کی پیروی کرتے ہیں، اور اہم اختلافات بعد کے مراحل کی پیروی کرتے ہیں۔ ایہلسویڈ اور ونٹر آگے بڑھنے کے لیے گولڈن تھامسن عدم مساوات کا استعمال کرتے ہیں، جبکہ ٹراپ لیب کا نظریہ استعمال کرتا ہے۔ فرض کریں کہ کوئی دائیں ہاتھ کی طرف تقریبا مستقل رکھتے ہوئے سیریز (n) کی لمبائی اور میٹرکس (d) کے طول و عرض کو تبدیل کرنا چاہتا ہے۔ پھر n تقریبا d کے لاگ کے طور پر مختلف ہونا چاہیے۔ کئی کاغذات نے طول و عرض پر انحصار کے بغیر باؤنڈ قائم کرنے کی کوشش کی ہے۔ Rudelson اور Vershynin میٹرکس کے لیے نتیجہ دیتے ہیں جو دو ویکٹروں کا بیرونی پروڈکٹ ہیں۔ نچلے درجے کے میٹرکس کے لیے جہتی انحصار کے بغیر نتیجہ فراہم کریں۔ اصل نتیجہ ایہلسویڈ-ونٹر اپروچ سے آزادانہ طور پر اخذ کیا گیا تھا، لیکن ایہلسویڈ-ونٹر اپروچ کا استعمال کرتے ہوئے اسی طرح کا نتیجہ ثابت ہوتا ہے۔ آخر میں، اولیویرا ایہلسویڈ-ونٹر فریم ورک سے آزادانہ طور پر میٹرکس مارٹنگلز کے لیے نتیجہ ثابت کرتا ہے۔ ایہلسویڈ-ونٹر فریم ورک کا استعمال کرتے ہوئے ٹراپ نتیجہ میں قدرے بہتری لاتا ہے۔ اس مضمون میں کوئی نتیجہ پیش نہیں کیا گیا ہے۔ ماخوذیت اور ثبوت ایہلسویڈ اور ونٹر میں پائی جانے والی لیپلیس ٹرانسفارم دلیل اپنے آپ میں ایک اہم نتیجہ ہے: آئیے ایک بے ترتیب سیلف ایڈجوائنٹ میٹرکس بنیں۔ پھر اسے ثابت کرنے کے لیے اسے ٹھیک کریں۔ پھر دوسری سے آخری عدم مساوات مارکوف کی عدم مساوات ہے۔ آخری عدم مساوات تب سے برقرار ہے۔ چونکہ سب سے بائیں طرف کی مقدار اس سے آزاد ہے، اس لیے انفیمیم اوور اس کے لیے ایک اوپری حد رہتا ہے۔ اس طرح، ہمارا کام سمجھنا ہے، اس کے باوجود، چونکہ سراغ اور توقع دونوں لکیری ہیں، ہم انہیں منتقل کر سکتے ہیں، لہذا اس پر غور کرنا کافی ہے، جسے ہم میٹرکس جنریٹنگ فنکشن کہتے ہیں۔ یہ وہ جگہ ہے جہاں کے طریقے اور مختلف ہوتے ہیں۔ فوری طور پر اگلی پریزنٹیشن اس کے بعد ہے۔ گولڈن-تھامسن عدم مساوات کا مطلب یہ ہے کہ، جہاں ہم نے توقع کی لکیری کو کئی بار استعمال کیا۔ فرض کریں۔ ہم اس نتیجہ کو دہرا کر ایک اوپری حد تلاش کر سکتے ہیں۔ یہ نوٹ کرتے ہوئے کہ، پھر اس کی تکرار کرتے ہوئے، ہم حاصل کرتے ہیں۔ اب تک ہم نے ایک لامحدود اوور کے ساتھ ایک باؤنڈ پایا ہے۔ بدلے میں، یہ پابند کیا جا سکتا ہے. کسی بھی صورت میں، کوئی یہ دیکھ سکتا ہے کہ کس طرح ایہلسویڈ-ونٹر باؤنڈ سب سے بڑی آئجین ویلیوز کے مجموعے کے طور پر پیدا ہوتا ہے۔ ٹراپ کی اہم شراکت لیب کے نظریہ کا اطلاق ہے جہاں گولڈن تھامسن عدم مساوات کا اطلاق کیا گیا تھا۔ ٹراپ کا نتیجہ مندرجہ ذیل ہے: اگر ایک فکسڈ سیلف ایڈجوائنٹ میٹرکس ہے اور بے ترتیب سیلف ایڈجوائنٹ میٹرکس ہے، تو ثبوت: چلو۔ پھر لیب کا نظریہ ہمیں بتاتا ہے کہ یہ کنکیو ہے۔ حتمی مرحلہ جینسن کی عدم مساوات کو فنکشن کے اندر توقع کو منتقل کرنے کے لیے استعمال کرنا ہے: اس سے ہمیں کاغذ کا بڑا نتیجہ ملتا ہے: میٹرکس جنریٹنگ فنکشن کے لاگ کی ذیلی اضافہ۔ لاگ ایم جی ایف کی ذیلی اضافہ آزاد، بے ترتیب سیلف ایڈجوائنٹ میٹرکس کی ایک محدود ترتیب ہے۔ پھر سب کے لیے، ثبوت: جانے دینا کافی ہے۔ تعریفوں کو وسعت دیتے ہوئے، ہمیں یہ ظاہر کرنے کی ضرورت ہے کہ ثبوت کو مکمل کرنے کے لیے، ہم کل توقع کا قانون استعمال کرتے ہیں۔ توقع کو مشروط ہونے دیں۔ چونکہ ہم فرض کرتے ہیں کہ تمام آزاد ہیں، اس کی وضاحت کریں۔ آخر میں، ہمارے پاس ہے جہاں ہر قدم m پر ہم ماسٹر ٹیل باؤنڈ کے ساتھ ٹراپ کا ارتقاء استعمال کرتے ہیں۔ مندرجہ ذیل پچھلے نتیجے سے فوری ہے: اوپر دیئے گئے تمام نظریات اس باؤنڈ سے اخذ کیے گئے ہیں۔ تھیوریمز انفیمیم کو باؤنڈ کرنے کے لیے مختلف طریقوں پر مشتمل ہیں۔ یہ اقدامات دیے گئے ثبوتوں کے مقابلے میں نمایاں طور پر آسان ہیں۔ حوالہ جات لکیری الجبرا