19481

۱۹۴۸۱

روش نوين تكميل ماتريس با استفاده از نرم تغييرات كل در ساختار گراف

كارشناسي ارشد

مخابرات

۱۳۹۴

۱۳۹۷/۰۲/۲۵

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

برق

در سالهاي اخير موضوع تكميل ماتريس مورد توجه قرار گرفته است. چالش اصلي مسألهي تكميل ماتريس، بازيابي كامل يك ماتريس رتبه پايين از روي مشاهده‌ي تعداد محدودي از درايه‌هاي آن ماتريس ميباشد. همچنين مدل‌سازي ارتباط بين سطر‌هاي ماتريس به صورت گراف، موجب معرفي تكميل ماتريس گراف شده است. مسأله‌ي تكميل ماتريس گراف از طريق افزودن عبارت تغييرات كل گراف به تابع هدف مسأله‌ي تكميل ماتريس، اقدام به بازيابي ماتريس مي‌نمايد. در اين پايان‌نامه از ماتريس لاپلاسين جهتدار براي تعريف تغييرات كل گراف استفاده نموده و روشي جديد براي تكميل ماتريس گراف ارائه مي‌دهيم. روش‌هاي پيشنهادي بر اساس نحوه‌ي مشاهده‌ي درايه‌هاي ماتريس در شرايط وجود نويز و داده‌ي پَرت تقسيم‌بندي مي‌شوند. روش‌هاي GMCM-DL در حالت بدون نويز، GMCR-DL براي مشاهدات نويزي و GMCO-DL در حالت وجود همزمان نويز و داده‌ي پرت در مشاهدات، ارائه مي‌گردند و روش حل تكرارشونده‌ي آن‌ها بر اساس الگوريتم پروكسيمال بدست آورده مي‌شود. نتايج شبيه‌سازي نشان مي‌دهند كه با كاهش درصد مشاهده‌ي درايه‌ها، كارايي روش‌هاي پيشنهادي در بازيابي ماتريس نسبت به ساير روش‌هاي تكميل ماتريس گراف افزايش مي‌يابد. علاوه بر اين، به كارگيري روش‌هاي پيشنهادي موجب مي‌گردد تا بازيابي يك سطر از ماتريس بدون مشاهده‌ي هيچ يك از درايه‌هاي آن امكان‌پذير مي‌باشد. اين الگوي مشاهده‌ي درايه‌ها را مشاهدات سطري نام‌گذاري مي‌نماييم. همچنين نتايج شبيه‌سازي روش پيشنهادي را با ساير روش‌هاي تكميل ماتريس گراف در حالت مشاهدات يكنواخت و سطري مقايسه مي‌نماييم. واژه‌هاي كليدي: تكميل ماتريس، پردازش سيگنال گراف،گراف جهتدار، تغييرات كل،الگوريتم پروكسيمال.

1397/07/22

Novel Approch for Matrix Completion using Total Variation Norm on Graph structure

10/14/2018 12:00:00 AM

Matrix completion problem has gathered a lot of attention in recent years. Exact recovery of a low rank matrix from a few subsets of its entries is the main challenge in matrix completion. The graph matrix completion has been introduced based on the fact that the relation between rows (or columns) of a matrix can be modeled by a graph structure. The graph matrix completion problem may be formulated by minimizing the nuclear norm in addition to the graph total variation. In this thesis, we apply the graph total variation base on directed Laplacian and introduce a new method for graph matrix completion. We introduce the GMCM-DL and GMCR-DL algorithms for the absent and presence noise, respectively and the GMCO-DL algorithm in presence of noise and outliers in observations. Also, we present an iterative solution for the proposed methods based on proximal algorithms. Simulation results indicate that the proposed methods outperform the other methods when the percentage of observed entries collapses. Furthermore, using our methods, we are able to recover a row of a matrix with observing none of its entries. We refer to this matrix completion approach as the row observation technique. Moreover, we compare the proposed methods with other matrix completion methods for uniform and row observations. Keywords: Matrix completion, Signal processing on graphs, Directed graph, Total variation, Proximal Algorithms.