Maximizing the smallest eigenvalue of a symmetric matrix: A submodular optimization approach

در این مقاله، مسئله انتخاب زیر ماتریس یک ماتریس قطعی مثبت به منظور دستیابی به یک محدودیت مطلوب در کوچکترین مقدار اختصاصی زیر ماتریس مورد بررسی قرار می گیرد. به حداکثر رساندن این کوچکترین مقدار خاص، برنامه های کاربردی برای انتخاب گره های ورودی به منظور تضمین اجماع شبکه های با لبه های منفی و حداکثر رساندن میزان همگرا از سیستم های توزیع شده است. ما یک رویکرد بهینه سازی زیرمودوئیدی را برای به حداکثر رساندن کوچکترین مقدار خاصی بوسیله ابتدا اثبات می کنیم که مثبت بودن مقادیر ویژه زیرمتریزه را می توان با استفاده از توزیع احتمالی فرم درجه دوم القاء شده توسط زیر ماتریکس مشخص کرد. ما سپس از این ارتباط استفاده می کنیم تا ثابت کنیم که قطعیت مثبت یک زیرماتیک را می توان به عنوان یک محدودیت در عملکرد یک زیرمودولار بیان کرد. ما ثابت می کنیم که رویکرد ما نتیجه الگوریتم های چندجملهای زمان را با مرزهای قابل تحقق در اندازه زیر مقیاس می یابد. ما همچنین تعمیم ها را به ماتریس های غیر متقارن، شرایط مناسب جایگزین برای کوچکترین مقدار خاص برای عبور از حد مورد نظر که برای ماتریس های لاپلازی معتبر است، و ارزیابی عددی ارائه می کنیم.