تجزیه مقدارهای منفرد

تجزیه مقادیر مفرد در ابتدا توسط هندسه‌های دیفرانسیل توسعه یافته بود، که مایل بودند با تبدیل‌های متعامد مستقل، از دو فضایی که بر روی آن عمل می‌کنند، مشخص کنند که آیا یک شکل دوقلو واقعی می‌تواند برابر شکل دیگری باشد یا خیر. Eugenio Beltrami و Camille Jordan به‌طور مستقل، در سالهای ۱۸۷۳ و ۱۸۷۴ به‌طور مستقل کشف کردند که مقادیر منفرد دو شکل، که به عنوان ماتریس نشان داده می‌شود، یک مجموعه کامل را از ثوابت برای اشکال دوقلو را تحت تعویض‌های متعامد تشکیل می‌دهد. همچنین جیمز جوزف سیلوستر در سال ۱۸۸۹ به‌طور مستقل از بلترامی و اردن به تجزیه مقادیر منفرد برای ماتریس‌های مربع رسید. سیلوستر مقادیر مفرد را ضربهای متعارف ماتریس A نامید. چهارمین ریاضیدان برای کشف تجزیه ارزش مفرد به‌طور مستقل، Autonne در سال ۱۹۱۵ است که از طریق تجزیه قطبی به آن دست یافت. به نظر می‌رسد اولین اثبات تجزیه ارزش مفرد برای ماتریس‌های مستطیل و پیچیده توسط کارل اکارت و گیل جی جوان در سال ۱۹۳۶ است که آن را به عنوان تعمیم تغییر محور اصلی ماتریس‌های هرمیتی می‌دیدند.

در سال ۱۹۰۷، ارهارد اشمیت یک آنالوگ از مقادیر مفرد را برای اپراتورهای انتگرال (تحت برخی فرضیات فنی ضعیف) تعریف کرد. به نظر می‌رسد وی از کار موازی روی مقادیر مفرد ماتریسهای محدود آگاه نبود. این نظریه پیشتر توسط ilemile Picard در سال ۱۹۱۰ ساخته شد، که اولین کسی است که اعداد را با مقادیر مفرد sigma می‌نامد.

روشهای عملی نیز برای محاسبه SVD به Kogbetliantz در سال ۱۹۵۴، ۱۹۵۵ و Hestenes در ۱۹۵۸ بازمی‌گردد. روش‌هایی که شبیه به روش eigenvalue Jacobi عمل می‌کرد. با این حال، این روش‌ها با روشی که Gene Golub و ویلیام کاهان که در سال ۱۹۶۵ منتشر کردند، جایگزین شدند. درنهایت در سال ۱۹۷۰، Golub و Christian Reinsch نوعی از الگوریتم Golub / Kahan را منتشر کردند که امروزه هنوز هم مورد استفاده قرار می‌گیرد.

دوران، پیمایش مختصات

در مورد خاص، زمانی که M یک ماتریس ${\displaystyle m\times m}$

به‌طور خاص، اگر M یک دترمینان مثبت داشته باشد، می‌توان${\displaystyle U}$

اگر ماتریس M حقیقی باشد اما مربعی نباشند، یعنی ${\displaystyle m\times n}$

مقادیر ویژه به عنوان شبه محور بیضوی

همان‌طور که در شکل نشان داده شده‌است، مقادیر تکین می‌توانند به عنوان اندازه نیم محور یک بیضی در 2D تعبیر شوند. این مفهوم را می‌توان به فضای ${\displaystyle n-n}$

مفهوم هندسی

از آنجا که U و V یکه هستند، می‌دانیم که ستونهای U از U1، … ، Um یک پایه متعامد ${\displaystyle K^m}$

تبدیل خطی:

${\displaystyle \left\{\begin{array}{c}T:K^n\to K^m\\ x\to Mx\end{array}\right\}}$

توضیحی به خصوص ساده با توجه به اساس تعامد دارد: ما داریم

${\displaystyle T(Vi)=\sigma iUii=1,...,min\{m,n\}}$

که در آن سیگما مقدار قطری ماتریس ${\displaystyle \mathrm{\Sigma }}$

از این رو مفهوم هندسی قضیه تجزیه مقدار تکین به شرح زیر خلاصه می‌شود:

برای هر نگاشت خطی ${\displaystyle T:K^n\to K^m}$

برای درک بهتر تجزیه مقدار تکین و فاکتورگیری آن، حداقل در هنگام استفاده از فضای برداری، یک کره با شعاع یک را در نظر بگیرید. نگاشت خطی T این کره را بر روی فضای بیضوی ${\displaystyle R^m}$

ماتریس‌های متعامد U و V

از آنجا که ${\displaystyle U}$

در عمل تجزیه کامل مقادیر تکین، که نیازمند تجزیه کامل فضای تهی نیز هست. مورد نیاز نیست. در عوض گاهی بهتر است که از حالت کاهش یافتهٔ آن استفاده گردد.

تجزیه مقدار تکین سبک

${\displaystyle M=Un\mathrm{\Sigma }n{V}^T}$

فقط بردارهای ستون n از ${\displaystyle U}$

مرحله اول در محاسبه SVD سبک معمولاً تجزیه QR از M است، که می‌تواند محاسبه ای به‌طور قابل توجهی سریعتر انجام دهداگر ${\displaystyle n⩽m}$

تجزیه مقدار تکین فشرده

${\displaystyle M=Ur\mathrm{\Sigma }rV{r}^T}$

فقط بردارهای ستون r از بردارهای ردیف ${\displaystyle U}$

تجزیه مقدار تکین کوتاه شده

${\displaystyle M=Ut\mathrm{\Sigma }tV{t}^T}$

فقط بردارهای ستون t از بردارهای ردیف ${\displaystyle U}$

مقادیری که در سیگما وجود دارد در واقع همان مقادیرِ منحصر به فردی (Singular) است که می‌تواند در عملیاتِ کاهشِ ویژگی به ما کمک کند. ممکن است برای کسانی که با داده‌کاوی و عملیاتِ کاهشِ ویژگی کار نکرده باشند کمی مبهم به نظر برسد ولی در ادامه، آرام آرام این مباحث در ذهن جای خود را پیدا می‌کنند. در ادامه نیز کاهش داده به صورت کلی توضیح داده شده‌است.

تجزیه مقدار تکین را می‌توان به صورت زیر مشاهد کرد:

• بردارهای تکین چپ ماتریس M مجموعه‌ای از بردارهای تکین ${\displaystyle M{M}^T}$
  هستند.
• بردارهای نکین راست ماتریسM مجموعه‌ای از بردارهای تکین ${\displaystyle M^{T}M}$
  هستند.
• مقادیر ویژه غیر منفی ماتریس M جذر ریشه مقادیر تکین هر دو ماتریس ${\displaystyle M{M}^T}$
  و ${\displaystyle M^{T}M}$
  هستند.

رویکرد عددی

یک ماتریس M معمولاً با به‌صورت دو مرحله ای محاسبه می‌شود. در مرحله اول، ماتریس به یک ماتریس دو قطری کاهش می‌یابد. مرحله دوم SVD محاسبه ماتریس دو قطری است. این مرحله فقط با یک روش تکراری (مانند الگوریتم‌های و مقادیر ویژه) قابل انجام است. با این حال، در عمل محاسبه SVD تا دقت خاصی مانند دستگاه اپسیلون کافی است. اگر این دقت ثابت در نظر گرفته شود، n مرتبه تکرار نیاز دارد که هر کدام فلوتینگ پوینت از مرتبه n دارند.

اولین قدم را می‌توان با استفاده از بازتاب‌های Householder با هزینه 4mn2 - 4n3 / ۳ فلاپ انجام داد، با این فرض که فقط مقادیر تکین مورد نیاز هستند و نه بردارهای تکین. اگر m بسیار بزرگتر از n باشد، کاهش ماتریس M به به یک ماتریس سه قطری توسط روش QR و پس از آن تبدیل به یک ماتریس دو قطری با استفاده از روش Householder یک مزیت با هزینه کم محاسباتی خواهد بود.

مرحله دوم را می‌توان با یک نوع از الگوریتم QR برای محاسبه مقادیر ویژه انجام داد که برای اولین بار توسط Golub & Kahan (1965) بیان شده‌است. سابروتینLAPACK با نام DGESVD این روش تکرار را با کمی اصلاح برای مقدار کم مقادیر تکین پوشش می‌دهد.

همین الگوریتم در کتابخانه علمی GNU (GSL) پیاده‌سازی شده‌است. GSL همچنین یک روش جایگزین ارائه می‌دهد که از یک طرفه سازی جاکوبی یک طرفه در مرحله ۲ استفاده می‌کند (GSL Team 2007). این روش ماتریس SVD دو قطری را با حل توالی از مسئله‌های ۲ × 2 SVD، شبیه به نحوه حل الگوریتم eigenvalue Jacobi، از روش‌های ۲ × ۲ مقادیر ویژه را محاسبه می‌کند. روش دیگر برای مرحله ۲ از ایده‌آلگوریتم‌های ویژه تقسیم و تسخیر استفاده می‌کند (Trefethen & Bau III 1997، سخنرانی ۳۱).

یک روش جایگزین وجود دارد که صریحاً از تجزیه مقادیر ویژه استفاده نمی‌کند. معمولاً مسئله‌های مقدار تکین یک ماتریس M به یک مسئله مقادیر متقارن معادل مانند${\displaystyle M{M}^T}$

تبدیل می‌شوند.

رویکردهایی که از تجزیه مقادیر ویژه استفاده می‌کنند بر اساس الگوریتم QR هستند که به خوبی توسعه یافته‌اند تا پایدار و سریع باشند. توجه داشته باشید که مقادیر منحصر به فرد حقیق راست و بردار چپ برای ایجاد دگرگونی هایتشابه لازم ندارند. می‌توان به‌طور متناوب بین تجزیه QR و تجزیه LQ برای یافتن ماتریس قطری حقیقی هرمتی تکرار ایجاد کند. تجزیه QR به M ⇒ Q R می‌دهد و تجزیه LQ از R به *R ⇒ L P می‌دهد؛ بنابراین، در هر تکرار، *M ⇒ Q L P را داریم، M ⇐ L را متعامد و تکرار می‌کند. سرانجام، این تکرار بین تجزیه QR و تجزیه LQ باعث تولید ماتریس‌های واحد چپ و راست می‌شود. این روش به آسانی قابل تسریع نیست، چرا که این الگوریتم ممکن است دچار تغییر در طیف و شکل گردد. دلیل این امر این است که روش تغییر بدون استفاده از تبدیل شباهت به راحتی تعریف نمی‌شود. با این حال، این رویکرد تکراری برای اجرا بسیار ساده است، بنابراین وقتی سرعت اهمیتی ندارد ، انتخاب خوبی است.

نتیجه تحلیلی تجزیه مقدار تکین ۲ × ۲

مقادیر متکین یک ماتریس ۲ × ۲ را می‌توان به صورت تحلیلی یافت. بگذارید ماتریس M به صورت زیر باشد:

${\displaystyle M=Z0I+Z1\sigma 1+Z2\sigma 2+Z3\sigma 3}$

که در آن ${\displaystyle Zi\in C}$

${\displaystyle \sigma \pm =\pm \sqrt{|Z0{|}^2+|Z1{|}^2+|Z2{|}^2+|Z3{|}^2\pm \sqrt{|Z0{|}^2+|Z1{|}^2+|Z2{|}^2+|Z3{|}^2-|Z{0}^2-Z{1}^2-Z{2}^2-Z{3}^2{|}^2}}}$

محاسبه SVD به کمک نرم‌افزار متلب

به کمک نرم‌افزار متلب می‌توان SVD یک ماتریس را محاسبه کرد.

دستور (svd(A مقادیر ویژه ماتریس A را بدست می‌دهد و با استفاده از دستور [u s v] = svd[A] ماتریس‌های متعامد و ماتریس مقادیر ویژه، به شما نمایش داده می‌شود.

ماتریس زیر را در نظر می‌گیریم:

تجزیهٔ مقدارهای منفرد این ماتریس برای UΣV به صورت زیر است:

توجه داشته باشید که Σ خارج از خط مورب صفر (خاکستری ایتالیک) است و یک عنصر مورب صفر (قرمز پررنگ) است. علاوه بر این، به دلیل اینکه ماتریس‌های U و V∗ یکتا هستند، ضرب آن‌ها توسط ترانهاده مزدوج آن‌ها ضرب می‌شود، همان‌طور که در زیر نشان‌داده شده‌است. در این حالت، به دلیل اینکه U و V∗ حقیقی هستند، هر کدام یک ماتریس متعامد هستند.

در حالت خاص در صورتی که ${\displaystyle V}$

همچنین یک تقسیم معتبر ارزش ویژه است.

Pseudo-Inverse

تجزیه مقدار تکین می‌تواند برای محاسبه شبه معکوس ماتریس مورد استفاده قرار گیرد. در واقع، شبه معکوس ماتریس M با تجزیه مقدار تکین ${\displaystyle M=U\mathrm{\Sigma }{V}^T}$

${\displaystyle M^{+}=V{\mathrm{\Sigma }}^{+}{U}^T}$

${\displaystyle {\mathrm{\Sigma }}^{+}}$

حل معادلات خطی همگن

یکی از کاربردهای این روش حل دستگاه معادلات است که در سه حالت می‌تواند بررسی گردد. ماتریس A با ابعاد M*N را درنظر بگیرید. حالت‌های زیر ممکن است رخ دهد:

1. M= N؛ که تعداد معادلات و مجهولات برابر و روابط خطی هستند.
2. M<N؛ تعداد معادلات از مجهولات کمتر است وSVD قابلیت حل آن را دارد.
3. M>N؛ در این صورت با دسته معادلات خطی حداقل مربعات سروکار داریم، با روش SVD قابلیت پیدا کردن جواب ممکن است.

مجموعه ای از معادلات خطی همگن را می‌توان به عنوان Ax = ۰ برای یک ماتریس A و بردار x نوشت. یک حالت معمول این است که A مشخص بوده و x غیر صفر تعیین می‌گردد که معادله را ارضا می‌کند. چنین x متعلق به فضای تهی A است و گاهی اوقات یک بردار تهی A (بردار راست) A نامیده می‌شود. بردار x را می‌توان به عنوان یک بردار است تکین که مطابق با مقدار تکین A که صفر است، توصیف کرد. این مشاهده به این معناست که اگر A یک ماتریس مربعی باشد و هیچ مقدار تکین اضمحلالی نداشته باشد، در نتیجه معادلات هیچ X غیر صفری به عنوان جواب ندارند. همچنین به این معنی است که اگر چندین مقدار تکین اضمحلالی وجود داشته باشد، هر ترکیب خطی از بردارهای تکین راست مربوطه یک جواب برای این دسته از معادلات خواهند بود.

کمینه حداقل مربعات

مسئله حداقل مربعات به تعیین مقدار بردار X که نرم دوم بردار Ax را با قید ${\displaystyle \parallel x\parallel <!--\; -->=1}$

مجموع مربعات مقادیر منفرد باید برابر با واریانس کلی در A باشد؛ بنابراین، اندازه هر یک از این مقادیر بیان می‌کند که چه مقدار از واریانس کلی برای هر بردار منفرد محاسبه می‌شود.

محدوده، فضای تهی و مرتبه

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

در نتیجه، درجه M برابر است با مقادیر تکین غیر صفر که برابر با تعداد عناصر قطری غیر صفر در Σ است. در جبر خطی عددی از مقادیر تکین می‌توان برای تعیین رتبه مؤثر یک ماتریس استفاده کرد، چرا که خطا گرد کردن ممکن است به مقادیر کوچک اما غیر صفر در مرتبه ماتریس منجر شوند.

تقریب ماتریس درجه پایین

در برخی از کاربردهای عملی نیاز به حل مسئله تقریب یک ماتریس مانند ${\displaystyle M}$

${\displaystyle \overline{M}=U\overline{\mathrm{\Sigma }}{V}^T}$

پردازش سیگنال

روش تجزیه مقدار تکین و شبه معکوس با موفقیت برای پردازش سیگنال، پردازش تصویر و داده‌های بزرگ (به عنوان مثال، در پردازش سیگنال ژنومی) استفاده شده‌اند.

کاهش داده

کاهش داده یا داده‌کاوی (به انگلیسی: Data Mining)، به مفهوم استخراج اطلاعات نهان یا الگوها و روابط مشخص در حجم زیادی از داده‌ها در یک یا چند بانک اطلاعاتی بزرگ گفته می‌شود. بسیاری از مردم داده کاوی را مترادف واژه‌های رایج کشف دانش در پایگاه‌داده‌ها (به انگلیسی: knowledge discovery in databases) (اختصاری KDD) می‌دانند. داده‌کاوی، پایگاه‌ها و مجموعه حجیم داده‌ها را در پی کشف و استخراج، مورد تحلیل قرار می‌دهد. این‌گونه مطالعات و کاوش‌ها را به واقع می‌توان همان امتداد و استمرار دانش کهن و همه جا گیر آمار دانست. تفاوت عمده در مقیاس، وسعت و گوناگونی زمینه‌ها و کاربردها، و نیز ابعاد و اندازه‌های داده‌های امروزین است که شیوه‌های ماشینی مربوط به یادگیری، مدل‌سازی، و آموزش را طلب می‌نماید.

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

اگر تعداد و انواع مناسبی از ویژگی‌ها برای حل یک مسئله خاص به الگوریتم‌های یادگیری ماشین داده شود، این الگوریتم‌ها به خوبی کار می‌کنند. اما، در صورتی که تعداد ویژگی‌ها (متغیرها) بسیار زیاد باشد، اغلب الگوریتم‌های یادگیری ماشین در حل مسئله دچار مشکل می‌شوند، زیرا با مسئله «داده‌های ابعاد بالا» (High Dimensional Data) مواجه خواهیم بود. در اینجا است که بحث «کاهش ابعاد» (Dimensionality Reduction) مطرح می‌شود. ویژگی (Feature) یا بُعد (Dimension) در واقع پایهٔ بسیاری از عملیاتِ داده‌کاوی و یادگیری‌ماشین است.

از طرفی بیان کردیم که که چگونه یک SVD با کاهش تعداد مقادیر تکین می‌تواند یک ماتریس را بسیار دقیق تقریب بزند. از این ویژگی می‌توان برای فشرده‌سازی داده‌ها با فرم‌های کوتاه شده UU, SS و VV به جای AA و برای کاهش متغیر از جایگزینی AA با UU استفاده کرد. البته در پایان، بر اساس معادله (۴) باید با ضرب SS و VV نتایج را به دستگاه مختصات اصلی تبدیل کرد.

کاربرد SVD در علم سیالات

از جمله کاربردهای این روش در علم مکانیک سیالات را می‌توان به موارد زیر اشاره کرد.

1. تحلیل داده‌های آزمایشگاهی و کاهش داده
2. کاهش میزان اغتشاشات تصویر برداری سیال
3. یافتن مدال‌های انرژی جریان آشفته
4. فیلتر اغتشاشات موج صوتی ناشی از حرکت سیال تراکم پذیر
5. استخراج انرژی و انستروفی سیال از دادهٔ خروجی تصویر برداری PIV و DPIV

• جبر خطی عددی
• تحلیل مولفه‌های اصلی
• ویژه‌مقدار

• Strang G (1998). "Introduction to Linear Algebra". Section 6.7. 3rd ed. , Wellesley-Cambridge Press. ISBN 0-9614088-5-5.
• Friedberg, S. H. , Insel, A. J. , Spence, L. E. (2003). "Linear Algebra", 4th ed. , Prentice Hall. ISBN 0-13-008451-4

• بعضی تجزیه‌های مفید در جبر خطی عددی و کاربرد آن‌ها، توسط بهروز خاوری
• مقایسهٔ روش‌های پایدارسازی مستقیم و تکراری در پایدارسازی مسئلهٔ انتقال به سمت پایین تعیین ژئوئید، عبدالرضا صفری، و یحیی الله توکلی، مجلهٔ فیزیک زمین و فضا، دورهٔ ۳۴، شمارهٔ ۱، ۱۳۸۷، صفحهٔ ۱۰۸–۸۹