Higher-order singular value decomposition
کثیر لکیری الجبرا میں، ٹینسر کا اعلی درجے کا واحد قدر سڑنا (HOSVD) ایک مخصوص آرتھوگنل ٹکر سڑنا ہے۔ اسے میٹرکس واحد قدر سڑنے کی عمومی شکل کی ایک قسم سمجھا جا سکتا ہے۔ اس کی ایپلی کیشنز کمپیوٹر وژن، کمپیوٹر گرافکس، مشین لرننگ، سائنٹفک کمپیوٹنگ، اور سگنل پروسیسنگ میں ہیں۔ کچھ پہلوؤں کا سراغ 1928 میں ایف ایل ہچکاک تک لگایا جا سکتا ہے، لیکن یہ ایل آر ٹکر ہی تھے جنہوں نے 1960 کی دہائی میں تیسرے درجے کے ٹینسرز کے لیے جنرل ٹکر سڑنا تیار کیا، جس کی مزید وکالت ایل ڈی لیتھوور اور دیگر نے کی۔ ان کے کثیر لکیری ایس وی ڈی کے کام میں جو طاقت کے طریقہ کار کو استعمال کرتا ہے، یا واسیلسکو اور ٹیرزوپولوس نے اس کی وکالت کی جس نے ایم موڈ ایس وی ڈی کو ایک متوازی الگورتھم تیار کیا جو میٹرکس ایس وی ڈی کو استعمال کرتا ہے۔ ہائیر آرڈر سنگل ویلیو ڈکمپزیشن (ایچ او ایس وی ڈی) کی اصطلاح ڈیلاتھاوور کے طور پر تیار کی گئی تھی، لیکن الگورتھم جسے عام طور پر ادب میں ایچ او ایس وی ڈی کہا جاتا ہے اور ٹکر یا ڈیلاتھاوور سے منسوب کیا جاتا ہے اسے واسیلسکو اور ٹیرزوپولوس نے تیار کیا تھا۔ ایچ او ایس وی ڈی کی مضبوط اور ایل 1 معیار پر مبنی اقسام بھی تجویز کی گئی ہیں۔ تعریف اس مضمون کے مقصد کے لیے، تجریدی ٹینسر کو ایم-وے صف کے طور پر کسی بنیاد کے حوالے سے نقاط میں دیا جاتا ہے، جس کی طرف بھی اشارہ کیا جاتا ہے، جہاں ایم طریقوں کی تعداد اور ٹینسر کی ترتیب ہے۔ پیچیدہ اعداد ہیں اور اس میں حقیقی اعداد اور خالص خیالی اعداد دونوں شامل ہیں۔ فرض کریں کہ ایک یکطرفہ میٹرکس جس میں معیاری موڈ کے بائیں واحد ویکٹر کی بنیاد ہوتی ہے-m اس طرح چپٹا ہوتا ہے کہ کا jth کالم کی سب سے بڑی واحد قدر سے مطابقت رکھتا ہے۔ مشاہدہ کریں کہ موڈ/فیکٹر میٹرکس خاص طور پر موڈ m چپٹا کرنے کی مخصوص تعریف پر منحصر نہیں ہے۔ کثیر لکیری ضرب کی خصوصیات کے مطابق، ہمارے پاس ہے جہاں کنجوگیٹ ٹرانسپوز کی نشاندہی کرتا ہے۔ دوسری مساوات اس لیے ہے کہ s یک جہتی میٹرکس ہیں۔ اب بنیادی ٹینسر کی وضاحت کریں۔ پھر، کا HOSVD سڑنا ہے۔ مندرجہ بالا تعمیر سے پتہ چلتا ہے کہ ہر ٹینسر میں HOSVD ہوتا ہے۔ کمپیکٹ HOSVD جیسا کہ میٹرکس کے کمپیکٹ سنگل ویلیو سڑنے کے معاملے میں، کمپیکٹ HOSVD پر غور کرنا بھی ممکن ہے، جو ایپلی کیشنز میں بہت مفید ہے۔ فرض کریں کہ یہ یکطرفہ کالموں والا ایک میٹرکس ہے جس میں بائیں واحد ویکٹروں کی بنیاد ہوتی ہے جو کہ کے معیاری عنصر-m چپٹے ہونے کی غیر صفر واحد اقدار سے مطابقت رکھتی ہے۔ کالموں کو اس طرح ترتیب دیا جائے کہ کالم کا واں کالم کے سب سے بڑے غیر صفر واحد قدر سے مطابقت رکھتا ہے۔ چونکہ کالم کی شکل کی تصویر کے لیے ایک بنیاد ہے، ہمارے پاس جہاں پہلی مساوات آرتھوگنل پروجیکشنز کی خصوصیات کی وجہ سے ہے (ہرمیٹین اندرونی پروڈکٹ میں) اور آخری مساوات کثیر لکیری ضرب کی خصوصیات کی وجہ سے ہے۔ چونکہ چپٹے نقشے دو طرفہ نقشے ہیں اور مندرجہ بالا فارمولا سب کے لیے درست ہے، اس لیے ہم اس سے پہلے کی طرح پاتے ہیں جہاں کور ٹینسر اب سائز کا ہے۔ کثیر لکیری درجہ کی کثیر لکیری درجہ بندی کو رینک-کے ساتھ ظاہر کیا جاتا ہے۔ ملٹی لائنر رینک ایک ٹپل ہے جہاں۔ تمام ٹپل ملٹی لائنر رینک نہیں ہوتے ہیں۔ کثیر لکیری صفوں کو پابند کیا جاتا ہے اور یہ اس رکاوٹ کو پورا کرتا ہے جو برقرار رکھنا ضروری ہے۔ کمپیکٹ ایچ او ایس وی ڈی اس لحاظ سے ایک رینک ظاہر کرنے والا ڈمپپوزیشن ہے کہ اس کے بنیادی ٹینسر کے طول و عرض ٹینسر کے ملٹی لینیر رینک کے اجزاء سے مطابقت رکھتے ہیں۔ تشریح مندرجہ ذیل ہندسی تشریح مکمل اور کمپیکٹ ایچ او ایس وی ڈی دونوں کے لیے درست ہے۔ مان لیں کہ ٹینسر کا کثیر لکیری درجہ ہے۔ چونکہ یہ ایک کثیر جہتی صف ہے، اس لیے ہم اسے اس کی پیروی کے طور پر بڑھا سکتے ہیں جہاں اس کا واں معیاری بیس ویکٹر ہے۔ کثیر لکیری ضرب کی تعریف کے مطابق، اس کا ماننا ہے کہ جہاں کے کالم ہیں۔ یہ تصدیق کرنا آسان ہے کہ یہ ٹینسرز کا ایک آرتھونورمل سیٹ ہے۔ اس کا مطلب یہ ہے کہ ایچ او ایس وی ڈی کی تشریح کثیر جہتی صف کے طور پر دیئے گئے کوفیشنٹس کے ساتھ خاص طور پر منتخب کردہ آرتھونورمل بنیاد کے حوالے سے ٹینسر کو ظاہر کرنے کے ایک طریقے کے طور پر کی جا سکتی ہے۔ کمپیوٹیشن ایک رینک-کے ساتھ ایک ٹینسر ہونے دیں، جہاں ایک ذیلی سیٹ کے طور پر حقیقی ہوتے ہیں۔ کلاسیکی کمپیوٹیشن ملٹی لینیر ایس وی ڈی اور ایم موڈ ایس وی ڈی کی کمپیوٹنگ کی حکمت عملی 1960 کی دہائی میں ایل آر ٹکر نے متعارف کرائی تھی، جس کی مزید وکالت ایل ڈی لاتوور اور دیگر نے کی تھی، اور واسیلسکو اور ٹیرزوپولس نے کی تھی۔ HOSVD کی اصطلاح لیوین ڈی لیتھوور نے تیار کی تھی، لیکن الگورتھم جسے عام طور پر ادب میں HOSVD کہا جاتا ہے اسے واسیلسکو اور ٹیرزوپولوس نے M-موڈ SVD کے نام سے متعارف کرایا تھا۔ یہ ایک متوازی حساب ہے جو میٹرکس ایس وی ڈی کو آرتھونورمل موڈ میٹرکس کا حساب لگانے کے لیے استعمال کرتا ہے۔ ایم-موڈ ایس وی ڈی: کے لیے، مندرجہ ذیل کام کریں: موڈ-ایم چپٹا کرنے کی تعمیر کریں ؛ (کمپیکٹ) واحد قدر سڑنے کا حساب لگائیں، اور بائیں واحد ویکٹرز کو ذخیرہ کریں ؛ ملٹی لینیر ضرب انٹرلیسنگ کمپیوٹیشن کے ذریعے کور ٹینسر کا حساب لگائیں ایک ایسی حکمت عملی جو نمایاں طور پر تیز ہوتی ہے جب کچھ یا سبھی کور ٹینسر اور فیکٹر میٹرکس کی کمپیوٹیشن کو آپس میں جوڑنے پر مشتمل ہوتے ہیں، جیسا کہ درج ذیل ہے: سیٹ کریں ؛ درج ذیل انجام دینے کے لیے: معیاری موڈ-چپٹا کرنے کی تعمیر کریں ؛ (کمپیکٹ) واحد قدر سڑنے کا حساب لگائیں، اور بائیں واحد ویکٹرز کو محفوظ کریں ؛ سیٹ کریں، یا، مساوی طور پر،۔ ان-پلیس کمپیوٹیشن HOSVD کو اصل ٹینسر کو HOSVD کور ٹینسر کے ذریعے اوور رائٹ کرکے فیوزڈ ان-پلیس سیکوینسلی ٹرنکیٹڈ ہائر آرڈر سنگل ویلیو ڈیکمپزیشن (FIST-HOSVD) الگورتھم کے ذریعے جگہ جگہ پر شمار کیا جا سکتا ہے، جس سے HOSVD کمپیوٹنگ کی میموری کی کھپت میں نمایاں کمی واقع ہوتی ہے۔ تخمینہ ایپلی کیشنز میں، جیسے کہ ذیل میں مذکور، ایک عام مسئلہ ایک دیئے گئے ٹینسر کو کم کثیر لکیری رینک کے ساتھ ایک کے قریب کرنے پر مشتمل ہوتا ہے۔ رسمی طور پر، اگر کے ملٹی لینیر رینک کو اس کے ذریعے ظاہر کیا جاتا ہے، تو ایک غیر لکیری غیر کنویکس-آپٹیمائزیشن مسئلہ ہے جس کے ساتھ کم شدہ ملٹی لینیر رینک ہے، اور معمول فروبینئس معیار ہے۔ اس اصلاح کے مسئلے کو حل کرنے کی کوشش کرنے کا ایک آسان خیال کلاسک یا انٹرلیسڈ کمپیوٹیشن کے مرحلہ 2 میں (کمپیکٹ) ایس وی ڈی کو کاٹنا ہے۔ کلاسیکی طور پر کٹے ہوئے ایچ او ایس وی ڈی کو کلاسک کمپیوٹیشن میں مرحلہ 2 کی جگہ ایک رینک کٹے ہوئے ایس وی ڈی کا حساب لگا کر حاصل کیا جاتا ہے، اور اوپری بائیں واحد ویکٹر کو ذخیرہ کیا جاتا ہے ؛ جبکہ ایک ترتیب سے کٹے ہوئے ایچ او ایس وی ڈی (یا یکے بعد دیگرے کٹے ہوئے ایچ او ایس وی ڈی) کو انٹرلیسڈ کمپیوٹیشن میں مرحلہ 2 کی جگہ ایک رینک کٹے ہوئے ایس وی ڈی کا حساب لگا کر حاصل کیا جاتا ہے، اور اوپری بائیں واحد ویکٹر کو محفوظ کیا جاتا ہے۔ بدقسمتی سے، کٹوتی کے نتیجے میں بہترین کم کثیر لکیری درجہ بندی کی اصلاح کے مسئلے کا بہترین حل نہیں ملتا ہے۔ تاہم، کلاسیکی اور انٹرلییوڈ کٹے ہوئے ایچ او ایس وی ڈی دونوں کا نتیجہ ایک نیم بہترین حل میں نکلتا ہے: اگر کلاسیکی یا ترتیب وار کٹے ہوئے ایچ او ایس وی ڈی کی نشاندہی کرتا ہے اور بہترین کم ملٹی لینیر رینک کے تخمینے کے مسئلے کے بہترین حل کی نشاندہی کرتا ہے، تو عملی طور پر اس کا مطلب یہ ہے کہ اگر ایک چھوٹی سی غلطی کے ساتھ ایک بہترین حل موجود ہے، تو ایک کٹا ہوا ایچ او ایس وی ڈی بہت سے مطلوبہ مقاصد کے لیے بھی کافی اچھا حل فراہم کرے گا۔ ایپلی کیشنز HOSVD کا اطلاق عام طور پر ملٹی وے صفوں سے متعلقہ معلومات کو نکالنے کے لیے کیا جاتا ہے۔ 2000 کی دہائی کے اوائل میں، واسیلسکو نے ڈیٹا تجزیہ، شناخت اور ترکیب کے مسائل کو کثیر الجہتی ٹینسر کے مسائل کے طور پر دوبارہ ترتیب دے کر وجہ کے سوالات کو حل کیا۔ ٹینسر فریم ورک کی طاقت کو حرکت کی شناخت، چہرے کی شناخت-ٹینسر فیسز اور کمپیوٹر گرافکس-ٹینسر ٹیکسٹورز کے لیے ہیومن موشن سگنیچرز کے تناظر میں ڈیٹا تشکیل کے اس کے وجہ عوامل کے لحاظ سے کسی تصویر کو سڑ کر اور اس کی نمائندگی کرکے دکھایا گیا تھا۔ ایچ او ایس وی ڈی کو سگنل پروسیسنگ اور بگ ڈیٹا پر کامیابی سے لاگو کیا گیا ہے، مثال کے طور پر، جینومک سگنل پروسیسنگ میں۔ ان ایپلی کیشنز نے ایک اعلی درجے کے جی ایس وی ڈی (ایچ او جی ایس وی ڈی) اور ایک ٹینسر جی ایس وی ڈی کو بھی متاثر کیا۔ بیماری کی نگرانی میں پیچیدہ ڈیٹا اسٹریمز (جگہ اور وقت کے طول و عرض کے ساتھ ملٹی ویریٹ ڈیٹا) سے ریئل ٹائم ایونٹ کا پتہ لگانے کے لیے بھی ایچ او ایس وی ڈی اور ایس وی ڈی کا ایک مجموعہ استعمال کیا گیا ہے۔ یہ ٹینسر پروڈکٹ ماڈل ٹرانسفارمیشن پر مبنی کنٹرولر ڈیزائن میں بھی استعمال ہوتا ہے۔ ایچ او ایس وی ڈی کے تصور کو ٹی پی ماڈل کی تبدیلی کے ذریعے بارانی اور یام نے افعال تک پہنچایا۔ اس توسیع کی وجہ سے HOSVD پر مبنی ٹینسر پروڈکٹ افعال اور لکیری پیرامیٹر مختلف نظام ماڈلز کی کینونکل شکل کی تعریف ہوئی اور کنویکس ہل ہیرا پھیری پر مبنی کنٹرول آپٹیمائزیشن تھیوری، کنٹرول تھیوریز میں TP ماڈل کی تبدیلی دیکھیں۔ ایچ او ایس وی ڈی کو ملٹی ویو ڈیٹا تجزیہ پر لاگو کرنے کی تجویز پیش کی گئی تھی اور جین کے اظہار سے سلیکو منشیات کی دریافت پر کامیابی کے ساتھ لاگو کیا گیا تھا۔ مضبوط L1-نارم ورژن L1-ٹکر L1-نارم پر مبنی ٹکر سڑنے کا مضبوط ورژن ہے۔ ایل 1-ایچ او ایس وی ڈی ایل 1-ٹکر کے حل کے لیے ایچ او ایس وی ڈی کے مترادف ہے۔ حوالہ جات کثیر لکیری الجبرا ٹینسرز