AlirezaJJ

سلام
برای یک تمرین احتیاج دارم که بردار ویژه های یک ماتریس با ابعاد 17000 در 17000 را بدست بیارم. اما متلب قادر به محاسبه برای ماتریسی با این ابعاد نیست و خطا در حافظه میده. یک روش تو ویکی پدیا پیدا کردم که کامل توضیح داده نشده. کسی می تونه تو این زمینه کمکم کنه؟!؟!
در ضمن این ماتریس اسپارسه ...
پیشاپیش ممنون و سپاسگذارم ...

mahdiii

من خودم برای شناسایی چهره به این مورد برخوردم. اونجا مثلا k تا تصویر داریم که ابعادش مثلا [n,m] هست که به صورت ستونی تبدیلش می کنیم میشه [n*m,1]. بعد این بردارهای ستونی که تعدادش k تا هستند کنار هم می گذاریم میشه [n*m,k] . بعد لازم میشه که ماتریس کواریانسش رو به دست بیاریم حالا اینجا اگه A' *A بکنیم با 'A*A با هم فرق می کنه.
بعدش هم در نهایت می خواهیم از این ماتریس کواریانس بردار ویژه و مقادیر ویژه شو به دست بیاریم. ماتریس کواریانس ما در اصل دارای ابعاد n*m,n*m خواهد بود که دارای اندازه بزرگی خواهد بود یعنی به تعداد پیکسلها . بنابراین کاری که میشه کرد اینه که بجای محاسبه 'A*A که ابعادش میشد n*m,n*m می تونیم A' *A را محاسبه کنیم که ابعادش میشه k*k که به دلیل اینکه مقدار k خیلی کمتر از تعداد پیکسلهاست مشکلمان حل میشه و به راحتی می تونیم مقادیر و بردارهای ویژه رو محاسبه کنیم برای این ماتریس k*k .
k مثلا 50 هستش .
حال باید برداهای ویژه به دست آمده( با ابعاد k*1 به تعداد k) رو یه جوری به بردارهای ویژه اولیه با ابعاد n*m,1 به تعداد k تبدیل کنیم. برای این کار هم به راحتی A را در بردارهای ویژه به دست آمده ضرب می کنیم. A گفتیم دارای ابعاد n*m,k بود و بردارهای ویژه هم k*k . با ضربشون بردارهای ویژه اصلی به دست میاد برای همون ماتریس کواریانس با ابعاد زیاد. یعنی بردارهای ویژه اصلی با ابعادn*m,k .
لازمه بگم که اگه شما از ماتریس کواریانس با ابعاد زیاد بردار ویژه شو به دست می اوردین ابعادش میشد n*m,n*m که بردارهای ویژه ما n*m,1 خواهد بود به تعداد n*m
اما با محاسبه بالا دیدیم که بردار ویژه نهایی شد n*m,k که به علت اینکه فرض کردیم k تصویر داریم که k عدد کوچکی نسبت به n*m است مشکلی نخواهیم داشت و همین تعداد بردار ویژه برای ما کفایت می کند. یک جور کاهش بعد داده ایم. باز اگه مشکلی بود بگید اگه بتونم توضیح میدم.
راستی برای هر ماتریسی تعداد نامتناهی می توانیم بردار ویژه در نظر بگیریم که ما دوست داریم بردار ویژه ای را برگزینیم که دارای شرط نرم یک باشد. اگه بردار ویژه هایی که تو زبان متلب محاسبه می کنید نرمشو محاسبه کنید می بینید همه یک هستند. بنابراین در اینجا پس از محاسبه بردارهای ویژه اصلی و نهایی که گفتم ابعادش n*m,k خواهد بود لازمه کاری کنیم که نرمشون یک بشه. برای این کار هم تمام مولفه های مربوط به یک بردار ویژه را تقسیم بر رادیکال مجموع مربعات تک تک مولفه های آن می کنیم. با این کار نرم آن به یک تبدیل میشه. این صحبتی که کردید در مورد اسپارس و خلوت نمی دونم چطوری میشه ازش استفاده کرد. به هر حال این تعداد بعد خیلی زیادن و باید از این راهی که گفتم برید.موفق باشید

AlirezaJJ

خیلی ممنونم! دقیقا چیزی بود که دنبالش بودم. فقط همین نرمال کردنش رو نمیدونستم چطوره، که گفتین.
یه نقطه مبهمه دیگم برام داشت که هنوز پا برجاست. اونم مربعی نبودن ماتریس بردارهای ویژه است. نمی فهمم یعنی چی!!؟؟! بردار ویژه کدوم فیچرها حذف شده؟ کلا نمیدونم ...

mahdiii

ببینید من دقیقا نفهمیدم شما چی می خواهید. من تنها اون چیزی رو که تو شناسایی چهره بهش برخوردم بازگو کردم. در شناسایی چهره هم ما این مشکلو داریم که برای محاسبه بردارهای ویژه ماتریس کواریانس اصلی که ابعادش هست n*m,n*m یعنی به تعداد پیکسلها، که بردارهای ویژه اون هم میشه به همین ابعاد یعنی n*m,n*m که میشه این جوری گفت که ما n*m بردار ویژه داریم با ابعاد n*m,1 اما چون در این مساله خاص فرض کردیم که تعداد تصاویر ما مثلا k هستش که k عدد کوچکی نسبت به n*m هست و برای ساخت ماتریس کواریانس همون طوری که گفتم می تونیم به جای ضرب A در ترانهادش ابتدا ترانهاده A رو بگیریم و بعد در خودش ضرب کنیم که میشه اینجوری k*k ابعاد ماتریس بردار ویژهمون که باید به بردار ویژه اصلی تبدیل شه. حالا چطوری؟ فقط کافیه A رو در اون ضرب کنیم که میشه n*m,k با k*k ضرب بشه ابعادمون میشه n*m,k که باید حتما اون نرمال سازی هم انجام بشه روش. می بینید که تعداد بردارهای ویژه به جای n*m شد k که یه جور کاهش بعد داده ایم و بهترین بردارهای ویژه رو نگه داشتیم که چونکه تعداد تصاویرمون تنها k تا بوده تنها با همین k بردار ویژه می تونیم تصاویرو توصیف کنیم و همین تعداد بردار ویژه کافیه برامون. بقیش لازم نیست.
اما مساله ای که شما اینجا گفتید ماتریسی دارید با ابعاد بزرگ مثلا 17000*17000 که من در مساله خودم اونو شبیه به ماتریس کواریانس گرفتم. دیدید که من ماتریس کواریانسو از ماتریس A ضربش در ترانهادش به دست آوردم. یعنی من ماتریس A رو داشتم و با اون ماتریس کواریانسو به دست آوردم اما در اینجا شما تنها یک ماتریس با ابعاد بزرگ دارید که از چیزی ساخته نشده است!!!! یک سوال این ماتریس متقارن است یا خیر. فقط اسپارس است؟
در اینترنت یه جستجو کردم
computation eigen vectors and values for huge and large matrices
یه روش تکراری گفته بود که چجوری میشه این کارو کرد. به اسپارسم اشاره کرده بود و گفته بود که اگه ماتریستون متقارن و positive definite باشه حتما به جواب اصلی همگرا میشه.

mahdiii

من اینترنت یک چند دقیقه جستجو کردم. مطلب زیاده در این مورد تو stack overflow و mathoverflow
خیلیا اینو سوال کردند.

Tim Davis: sparse matrix algorithm research, sparse matrix software, sparse matrix collection
r - How expensive is it to compute the eigenvalues of a matrix? - Stack Overflow
Computing the largest Eigenvalue of a very large sparse matrix? - MathOverflow
http://www.mathworks.com/access/help.../ref/eigs.html
چندتا بسته هم معرفی کردند تو تولباکس متلب برای همین کار که خیلی مفیده و سریع محاسبه می کنه
فقط همه هم گفته بودند که زمانی که ماتریست دارای ابعاد زیاده تو همه بردارهای ویژشو نمی خوای بنابراین بهترینهاشو بهت برمی گردونه با روشهای تکراری. که همین اسپارسی که گفتی کمک می کنه.
گفته بود مرتبه زمانی اون در بدترین حالت o(n3) هست که خیلی زیاد میشه با این ابعاد