26067

ارائه روشي جديد براي تقريب ماتريس كم رتبه با بخش بندي زير ماتريسي

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

مهندسي برق-مخابرات سيستم

1400/09/23

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

مهندسي برق

تقريب ماتريس كم رتبه ، به دست آوردن يك ماتريس با رتبه پايين تر نسبت به ماتريس اصلي است. به طوري كه در حين تقريب اطلاعات ماتريس اصلي نيز تا حد امكان حفظ مي‌شود. تقريب ماتريس كم رتبه نقش مهمي در زمينه پردازش داده و پردازش سيگنال دارد. از كاربرد هاي آن مي‌توان به تحليل و پردازش تصاوير فراطيفي، تحليل تصاوير پزشكي، كاهش ابعاد داده و ... اشاره نمود. يك نمايش كم رتبه مي‌تواند حافظه مورد نياز و هزينه هاي محاسباتي در پردازش داده هاي بزرگ را به طور قابل توجهي كاهش دهد. در اين پايان نامه، يك الگوريتم جديد تقريب ماتريس كم رتبه با بخش بندي زيرماتريسي ارائه مي‌كنيم. ابتدا ابعاد ماتريس ورودي را با نمونه برداري تصادفي كاهش مي‌دهيم. براي محاسبه تقريب ماتريس كم رتبه از ماتريس با ابعاد پايين (فشرده )، يك مسئله بهينه سازي با پارامتر تنظيم كننده براي ايجاد مصالحه بين خطا و پيچيدگي مدل (رتبه) پيشنهاد مي‌كنيم. براي حل آن از آستانه گذاري نرم مقدار منفرد استفاده مي‌كنيم. اين موضوع باعث مي‌شود بتوانيم از Stein’s unbiased risk estimate (SURE) براي تخمين خطاي ميانگين مربعات (MSE ) استفاده كنيم. اين روش تقريب ماتريس كم رتبه را به صورت موازي به هر كدام از زير ماتريس هاي ماتريس با ابعاد پايين اعمال مي‌كنيم. با استفاده از تقريب هاي كم رتبه زير ماتريس ها و روش Truncated SVD، يك تقريب ماتريس كم رتبه از ماتريس ابعاد پايين به دست مي‌آوريم. سپس با استفاده از آن تقريب ماتريس كم رتبه نهايي را به دست مي‌آوريم. طبق آزمايش هاي عددي انجام شده، الگوريتم ارائه شده از نظر خطا عملكرد مناسبي دارد. بخش‌بندي زير ماتريسي كاهش قابل توجهي را در زمان انجام محاسبات نسبت به حالت بدون بخش‌بندي زير ماتريسي ايجاد مي‌كند. با افزايش تعداد زير ماتريس ها و پردازش موازي مي‌توان زمان انجام محاسبات را كم تر كرد. همچنين، با به كارگيري روش تكرار توان مي‌توانيم دقت الگوريتم را افزايش دهيم.

1400/11/20

A New Method for Low-Rank Matrix Approximation using Submatrix Partitioning

12/14/2022 12:00:00 AM

The low-rank matrix approximation is to approximate a given original matrix by a low-rank matrix. This should be performed in such a way that the information of the original matrix is preserved as much as possible. Low-rank approximation plays an important role in data and signal processing. Some applications for low-rank approximation include analysis and processing of hyperspectral images, analysis of medical images, reduction of data dimensions and so on. A low-rank presentation can significantly reduce memory requirements and the computational costs in the big data processing. In this dissertation, we present a new low-rank matrix approximation algorithm based on submatrix partitioning. First, we reduce the dimensions of the input matrix by random sampling technique. To calculate a low-rank matrix approximation from compressed matrix, we propose an optimization problem with an adjusting parameter to incorporate the error and model complexity (rank). To solve this problem, we use the Singular Value Soft Thresholding, which allows us to use Stein’s unbiased risk estimate (SURE) technique to estimate the Mean-Square Error (MSE). Apply this low-rank matrix approximation method in parallel to each of the compressed matrix submatrices. Using the low-rank approximations of the submatrices and the Truncated SVD method, we obtain a low-rank matrix approximation of the compressed matrix. Then we use it to obtain the final low-rank matrix approximation. According to the numerical experiments, the proposed algorithm has a good performance in reducing the approximation error. Also, partitioning causes a significant reduction in computation time compared to the non-partitioning case. By increasing the number of submatrices and parallel processing, the computation time can be reduced. Also, by using the power iteration method, we can increase the accuracy of the algorithm.

تقريب ماتريس كم رتبه , SURE , بخش بندي زير ماتريسي , Truncated SVD , نمونه برداري تصادفي , MSE

Low-rank matrix approximation , SURE , Partitioning , Truncated SVD , Random sampling , MSE estimation