27780

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

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

برق مخابرات سيستم

1398

1401/07/30

دكتر فرزان حدادي

مهندسي برق

مسئله تكميل ماتريس، بازيابي يك ماتريس كم‌رتبه از تعداد كمي نمونە‌هاي مشاهده شده مي‌باشد. كاربرد وسيع اين مسئله در بسياري از حوزە‌ها مانند يادگيري ماشين، پردازش سيگنال، سيستم‌هاي پيشنهادگر، زلزله‌نگاري و تعيين موقعيت جهاني توجه محققان را به آن جلب كرده است. در اين پايان نامه، روش پيشنهاد مي‌شود كه از تكنيك تجزيه و بالا بردن بهرە برداري مي‌كند. ما در روش پيشنهادي بدون هيچ گونه فرضيات اضافي در مورد مدل مسئله، شرايط يقيني براي همگرايي كاهش گراديان بدست مي‌آوريم كه فقط به ماتريس جواب و مجموعه نمونە‌برداري شده بستگي دارد. مهمتر از آن، اين نوع تجزيه و تحليل بياني به فرم بسته از نرخ مجانبي همگرايي روش كاهش گراديان ارائه مي‌دهد كه دقيقاً با همگرايي الگوريتم در عمل مطابقت دارد و از هر دو جنبه تئوري و عملي مفيد مي‌باشد. در ادامه، به معرفي الگوريتم كاهش گراديان مي‌پردازيم. مسئله پيشنهادي، حداقل سازي تابع هدف نامحدب با استفاده از الگوريتم كاهش گراديان است. عملكرد اين الگوريتم در مسئله تكميل ماتريس مستطيلي تضمين شده است. نتايج عددي ارائه شده مزاياي استفاده از الگوريتم كاهش گراديان را در مسئله تكميل ماتريس نشان داده و بهبود سرعت و نرخ نمونە‌برداري روش پيشنهادي را در مقايسه با ساير روش ها نشان مي‌دهد.

1401/11/03

Rectangular Matrix Completion via Gradient Descent

10/22/2023 12:00:00 AM

Matrix completion is the problem of recovering a low rank matrix from partially observed entries. The wide application of this problem in many fields such as machine learning, signal processing, recommender systems,Seismic interpolation, and global positioning has attracted the attention of researchers. In this dissertation, a method is proposed that utilizes the technique of factorization and lifting. Without any additional assumptions about the underlying model, the proposed method identifies the deterministic conditions for convergence of gradient descent, which only depends on the solution matrix and the sampling set. More crucially, this type of analysis provides a closed-form expression of the asymptotic rate of convergence that exactly matches the linear convergence observed in practice.this analysis can be useful in both theoretical and practical aspects of the rectangular matrix completion problem. In the following, we introduce the gradient descent algorithm. The proposed problem is a nonconvex minimization problem using gradient descent algorithm. The performance of this algorithm is guaranteed in the rectangular matrix completion problem. The presented numerical results show the advantages of using gradient reduction in the problem of completing the matrix and improving the performance of the proposed method compared to other methods.

بالا بردن , بهينه‌سازي نامحدب , تجزيه , كاهش گراديان

lifting , nonconvex optimization , factorization , Gradient Descent

Zohreh Miri

Farzan Haddadi