26087

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

دكتري

برق

95

26/08/1400

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

برق

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

1400/11/30

Methods of Using Manifold Geometry in Matrix Completion

11/17/2022 12:00:00 AM

The local isomorphism of a manifold with Euclidean space helps to generalize and solve the inverse problems of Euclidean space to the manifold space. Although data structures are usually in the form of manifolds, they are generally modeled on Euclidean space for simplicity, which can result in higher computational complexity and lower accuracy. In general, inverse modeling and problem solving is done using the definition of an optimization problem and its solution. In this dissertation, in terms of side information about inverse problems, we present the geometric structure for each inverse problem that is used to solve the optimization problem. The inverse problems discussed in this dissertation are: -High rank matrix completion The first inverse problem is the problem of high rank matrix completion that has various applications, including identifying the Internet network topology. We solve this problem by having additional information about row and column space and presenting an optimization problem on a new manifold. The performance improvement of the proposed algorithm in term of the normalized error criterion is in some cases more than 15% compared to other existing methods. As the probability of observation increases, the error recovery performance of our proposed algorithm is greatly improved until the error value reaches about 0.12. While the performance of the best other algorithms is about 0.19. - Completion of low-rank bipolar matrices; The second inverse problem is the problem of completing low-rank bipolar matrices, one of the applications of which is collaborative filtering. In order to solve these inverse problems, we consider two different modes of low observation error and high observation error, for both cases, we propose manifold optimization problems and prove the convergence of some algorithm for them. In the first case, we use the manifold of rank-one matrices and also use the gradient descent algorithm to solve the problem. In the second case, we model the problem on a Riemannian sphere and use the trust region method to solve the problem. For both cases, we have considered the specific application of haplotype assembly. The simulation results in the first case show an improvement in the performance of haplotype estimates of about 10% by the Hamming distance criterion compared to other algorithms. In the second case, in some experiments, performance improvement compared to other algorithms is observed up to 20% by Hamming distance criterion. - Solve the maximum cut problem; The third inverse problem is the problem of maximum cut of an unweighted undirected graph without loop, which is used in problems such as data clustering. To solve this problem, we present an optimization problem on the manifold that contains the properties of the maximum cut problem and prove its convergence. According to the simulation results, our proposed algorithm is 35 times faster than other algorithms in solving problems for known graphs with a maximum number of vertices 3000; While it can reach the cut size of 0.96 with the best algorithms available. More importantly, our proposed algorithm is easily capable of solving the problem of maximum cut for very large vertices. While other existing algorithms, even for 5000 vertices, it takes a very long time (more than 10,000 seconds) to converge. Therefore, the proposed algorithm is a very fast and accurate algorithm in solving the maximum cut problem.

منيفلد

manifold