روشهاي استفاده از هندسه منيفلد در تكميل ماتريس

دكتري

يكريختي موضعي يك منيفلد با فضاي اقليدسي كمك مي‌كند مسائل معكوس فضاي اقليدسي را به فضاي منيفلد تعميم داده و حل نمود. هر چند كه ساختارهاي داده معمولاً به شكل منيفلد هستند، عموماً مسائل را به منظور سادگي بر روي فضاي اقليدسي مدل مي‌كنند كه هزينه اين سادگي، مي‌تواند پيچيدگي محاسباتي بالاتر و دقت كم‌تر باشد. به صورت كلي، مدل‌سازي و حل مسائل معكوس با استفاده از تعريف يك مسئله بهينه‌سازي و حل آن صورت مي‌پذيرد. در اين رساله، با لحاظ اطلاعات جانبي موجود در رابطه با مسائل معكوس، ساختار هندسي براي هر مسئله معكوس ارائه مي‌كنيم كه در حل مسئله بهينه‌سازي مورد استفاده قرار مي‌گيرد. مسائل معكوس مورد بررسي در اين رساله عبارتند از: - تكميل ماتريس‌هاي رتبه بالا؛ مسئله معكوس اول، مسئله تكميل ماتريس‌هاي رتبه بالا است كه كاربردهاي مختلفي از جمله شناسايي توپولوژي شبكه اينترنت دارد. اين مسئله را با در دست داشتن اطلاعات جانبي در رابطه با فضاي سطري و ستوني و ارائه يك مسئله بهينه‌سازي بر روي يك منيفلد جديد حل مي‌كنيم. بهبود عملكرد الگوريتم پيشنهادي با معيار خطاي نرماليزه شده، در برخي موارد بيشتر از 15 درصد نسبت به ساير روش‌هاي موجود است. با افزايش احتمال مشاهده، عملكرد خطاي بازيابي الگوريتم پيشنهادي ما به مراتب بهتر مي‌شود تا جاييكه مقدار خطا به حدود 0.12 مي‌رسد. در حاليكه عملكرد بهترين ساير الگوريتم‌ها، تا حدود 0.19 مي‌رسد. - تكميل ماتريس‌هاي دوقطبي رتبه پايين؛ مسئله معكوس دوم، مسئله تكميل ماتريس‌هاي دوقطبي رتبه پايين است كه از كاربردهاي آن مي‌توان به فيلترينگ مشاركتي اشاره كرد. به منظور حل اين دسته از مسائل معكوس، ما دو حالت مختلف خطاي مشاهدات كم و خطاي مشاهدات زياد را بررسي مي‌كنيم كه براي هر دو حالت، مسئله بهينه‌سازي منيفلد پيشنهاد كرده و همگرايي الگوريتم را براي آن‌ها اثبات مي‌كنيم. در حالت اول، منيفلد ماتريس‌هاي رتبه يك را استفاده كرده‌ايم و همچنين از الگوريتم گراديان كاهشي به منظور حل مسئله بهره برده‌ايم. در حالت دوم، مسئله را بر روي كره ريماني مدل كرده‌ايم و روش ناحيه اعتماد را براي حل مسئله استفاده كرده‌ايم. براي هر دو حالت، كاربرد خاص بازيابي هاپلوتايپ را در نظر گرفته‌ايم. نتايج شبيه‌سازي در حالت اول نشان‌دهنده بهبود عملكرد تخمين هاپلوتايپ به اندازه حدود 10 درصد با معيار فاصله همينگ نسبت به ساير الگوريتم‌ها است. در حالت دوم نيز در برخي آزمايش‌ها، بهبود عملكرد نسبت به ساير الگوريتم‌ها تا 20 درصد با معيار فاصله همينگ مشاهده مي‌شود. - حل مسئله حداكثر برش؛ مسئله معكوس سوم، مسئله حداكثر برش يك گراف بدون وزن بدون جهت و بدون حلقه است كه در مسائلي از جمله خوشه‌بندي داده كاربرد دارد. براي حل اين مسئله يك مسئله بهينه‌سازي بر روي منيفلد كه دربردارنده ويژگي‌هاي مسئله حداكثر برش است را ارائه و همگرايي آن را اثبات مي‌كنيم. طبق نتايج شبيه‌سازي، الگوريتم پيشنهادي ما 35 برابر سريعتر از ساير الگوريتم‌ها در حل مسئله براي گراف‌هاي شناخته شده با حداكثر تعداد رئوس 3000 است؛ در حاليكه مي‌تواند به دقت 0/96 اندازه برش بهترين الگوريتم‌هاي موجود برسد. از اين مهمتر، الگوريتم پيشنهادي ما براحتي توانايي حل مسئله حداكثر برش به ازاي تعداد رئوس بسيار بالا را نيز دارد. در حاليكه ساير الگوريتم‌هاي موجود، حتي به ازاي 5000 يال هم مدت زمان بسيار زيادي (بيش از 10000 ثانيه) نياز دارند تا همگرا شوند. بنابراين الگوريتم پيشنهادي يك الگوريتم بسيار سريع و با دقت مناسب در حل مسئله حداكثر برش است.

210076

دانشگاه علم و صنعت ايران

برق

محمد حسين كهايي