Calculating the Singular Values and Pseudo-Inverse of a Matrix

خلاصه

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

نمای سریع

چگونه SVD را روی کامپیوتر، سریع و بدون از دست دادن دقت، واقعاً حساب کنیم.

یافته‌های کلیدی

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

هدف

هدف، یافتن روشی بود که مقادیر منفرد و شبه‌وارون یک ماتریس دلخواه را با پایداری عددی بالا محاسبه کند و بتوان از آن برای حل مسائل کمترین مربعات استفاده کرد.

روش

گولوب و کاهان الگوریتمی دومرحله‌ای پیشنهاد دادند: نخست ماتریس با تبدیل‌های متعامد (هاوس‌هولدر) به شکل دوقطری تبدیل می‌شود و سپس با یک فرایند تکراری، مقادیر منفرد این ماتریس دوقطری محاسبه می‌شود. آن‌ها همچنین نشان دادند چگونه از همین تجزیه برای ساخت شبه‌وارون و حل مسائل کمترین مربعات استفاده کرد.

نتایج

الگوریتم دوقطری‌سازی مبتنی بر تبدیل‌های متعامد ارائه شد که دقت مقادیر منفرد کوچک را حفظ می‌کند و مبنای پیاده‌سازی‌های استاندارد بعدی قرار گرفت.

نتیجه‌گیری

نویسندگان نتیجه گرفتند که SVD نه‌تنها یک ابزار نظری بلکه روش انتخابی برای حل عددی مسائل کمترین مربعات و مسائل بدوضع است.

مفاهیم کلیدی

SVD، شبه‌وارون، کمترین مربعات، جبر خطی عددی، پایداری عددی

مطالعه‌ی بیشتر

https://doi.org/10.1137/0702016

تحلیل

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

محدودیت‌ها

الگوریتم برای ماتریس‌های چگال و با ابعاد متوسط طراحی شده و برای ماتریس‌های بسیار بزرگ یا تُنُک هزینه‌ی محاسباتی و حافظه‌ی آن بالاست. همچنین کل طیف مقادیر منفرد را محاسبه می‌کند، در حالی که در بسیاری از کاربردهای امروزی فقط چند مقدار بزرگ لازم است؛ به همین دلیل روش‌های تکراری و تصادفی‌شده بعدها توسعه یافتند.

کارهای آینده

مقاله راه را برای بهبود پایداری و سرعت مراحل تکراری، و گسترش روش به ماتریس‌های بزرگ‌تر و ساختارمندتر باز گذاشت؛ مسیری که به الگوریتم گولوب-رینش و بعدها به روش‌های تکراری و تصادفی‌شده انجامید.

کاربرد عملی

الگوریتم گولوب-کاهان و نسخه‌های بهبودیافته‌ی آن هنوز موتور واقعی توابع SVD در کتابخانه‌هایی مانند LAPACK، numpy و MATLAB هستند؛ یعنی هر بار که در پایتون SVD می‌گیرید، عملاً میراث همین مقاله اجرا می‌شود. برای پروژه‌ی ربات انسان‌نما و ربات انگشت‌دار، شبه‌وارونِ محاسبه‌شده با همین روش، ابزار استاندارد حل سینماتیک معکوس و مدیریت وضعیت‌های تکین است.