بهبود برخی از روش های حل مسئله ی تکمیل ماتریس

Document Type : Research Paper

Authors

گروه ریاضی کاربردی، دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر، استان تهران، ایران

10.22072/wala.2020.110303.1233

Abstract

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

Keywords


[1] E. Adeli-Mosabbeb and M. Fathy, Non-negative matrix completion for action detection, Image and Vision Computing
     39 (2015), 38-51.
[2] J.F. Cai, E.J. Candès and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20(4) 
     (2010), 1956-1982.
[3] J. Fan and T.W. Chow, Matrix completion by least-square, low-rank, and sparse self-representations,  Pattern 
     Recognition, 71 (2017), 290-305.
[4] X. Hu, N. Tong, J. Wang, S. Ding and X. Zhao, Matrix completion-based MIMO radar imaging with sparse planar array, 
     Signal Process., 131 (2017), 49-57.
[5] S.G. Lee and H.G. Seol, A survey on the matrix completion problem, Trends Math., 4 (2001), 38-43.   
[6] Y. Liu , L.C. Jiao and F. Shang, A fast tri-factorization method for low rank matrix recovery and completion, Pattern 
      Recognition, 46}(1) (2013), 163-173.
[7] A. Majumdar  and R.K. Ward, Some empirical advances in matrix completion, Signal Process., 91(5) (2011), 1334-1338.
[8] Y. Shen, Z. Wen and Y. Zhang, Augmented Lagrangian alternating direction method for matrix separation based on 
     low-rank factorization, Optim. Methods Softw., 29(2) (2014), 239-263.
[9] J. Tanner and K. Wei, Low rank matrix completion by alternating steepest descent Methods, Appl. Comput. Harmon. 
     Anal., 40(2) (2016), 417-429.
[10] J.Y. Wadood, Image Reconstruction from a Limited Number of Samples: A Matrix-Completion-Based Approach,  Ph.D. 
       thesis, McGill University Libraries, 2011.
[11] Z. Wen, W. Yin and Y. Zhang, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Math. Program. Comput., 4(24) (2012), 333-361.