ऑर्थोगोनल प्रोक्रस्टेस समस्या

लाम्बिक प्रोक्रस्टेस समस्या रैखिक बीजगणित में आव्यूह सन्निकटन समस्या है। इसके चिरप्रतिष्ठित रूप में, एक को दो आव्यूह $A$ और $B$ दिए जाते हैं और एक लांबिक आव्यूह खोजने के लिए कहा जाता है, Ω\ओमेगा जो $A$ से $B$ तक सबसे सटीक से मानचित्र करता है। विशेष रूप से,

$R=\arg \min _{\Omega }\|\Omega A-B\|_{F}\quad \mathrm {subject\ to} \quad \Omega ^{T}\Omega =I,$

कहाँ $\|\cdot \|_{F}$ फ्रोबेनियस मानदंड को दर्शाता है। यह वहाबा की समस्या का एक विशेष मामला है (समान भार के साथ; दो आव्यूहों पर विचार करने के बजाय, वहाबा की समस्या में आव्यूहों के स्तंभों को अलग-अलग वैक्टर माना जाता है)। एक और अंतर यह है कि वाहबा की समस्या केवल एक ऑर्थोगोनल के बजाय एक उचित रोटेशन आव्यूहखोजने की कोशिश करती है।

प्रोक्रस्टेस नाम ग्रीक पौराणिक कथाओं के एक डाकू को संदर्भित करता है जो अपने पीड़ितों को या तो उनके अंगों को खींचकर या उन्हें काटकर अपने बिस्तर पर फिट कर देता था।

समाधान

इस समस्या को मूल रूप से पीटर शॉनमैन ने 1964 की थीसिस में हल किया था, और कुछ ही समय बाद साइकोमेट्रिका पत्रिका में छपी। यह समस्या किसी दिए गए आव्यूहके निकटतम ऑर्थोगोनल आव्यूहको खोजने के बराबर है $M=BA^{T}$, यानी निकटतम ऑर्थोगोनल सन्निकटन समस्या को हल करना

$\min _{R}\|R-M\|_{F}\quad \mathrm {subject\ to} \quad R^{T}R=I$.

आव्यूहखोजने के लिए $R$, एक एकल मूल्य अपघटन का उपयोग करता है (जिसके लिए की प्रविष्टियाँ $\Sigma$ गैर-नकारात्मक हैं)

$M=U\Sigma V^{T}\,\!$

लिखना

$R=UV^{T}.\,\!$

प्रमाण

एक प्रमाण फ्रोबेनियस आंतरिक उत्पाद के मूल गुणों पर निर्भर करता है जो फ्रोबेनियस मानदंड को प्रेरित करता है:

${\begin{aligned}R&=\arg \min _{\Omega }||\Omega A-B\|_{F}^{2}\\&=\arg \min _{\Omega }\langle \Omega A-B,\Omega A-B\rangle _{F}\\&=\arg \min _{\Omega }\|\Omega A\|_{F}^{2}+\|B\|_{F}^{2}-2\langle \Omega A,B\rangle _{F}\\&=\arg \min _{\Omega }\|A\|_{F}^{2}+\|B\|_{F}^{2}-2\langle \Omega A,B\rangle _{F}\\&=\arg \max _{\Omega }\langle \Omega ,BA^{T}\rangle _{F}\\&=\arg \max _{\Omega }\langle \Omega ,U\Sigma V^{T}\rangle _{F}\\&=\arg \max _{\Omega }\langle U^{T}\Omega V,\Sigma \rangle _{F}\\&=\arg \max _{\Omega }\langle S,\Sigma \rangle _{F}\quad {\text{where }}S=U^{T}\Omega V\\\end{aligned}}$

यह मात्रा $S$ एक ऑर्थोगोनल आव्यूहहै (क्योंकि यह ऑर्थोगोनल आव्यूहका एक उत्पाद है) और इस प्रकार अभिव्यक्ति अधिकतम हो जाती है जब $S$ पहचान आव्यूहके बराबर है $I$. इस प्रकार

${\begin{aligned}I&=U^{T}RV\\R&=UV^{T}\\\end{aligned}}$

कहाँ $R$ के इष्टतम मूल्य का समाधान है $\Omega$ जो मानक वर्ग को न्यूनतम करता है $||\Omega A-B\|_{F}^{2}$.

सामान्यीकृत/विवश प्रोक्रस्टेस समस्याएँ

शास्त्रीय ओर्थोगोनल प्रोक्रस्ट्स समस्या से संबंधित कई समस्याएं हैं। कोई इसे निकटतम आव्यूहकी तलाश करके सामान्यीकृत कर सकता है जिसमें कॉलम ऑर्थोगोनल हैं, लेकिन जरूरी नहीं कि ऑर्थोनॉर्मल हों। वैकल्पिक रूप से, कोई केवल रोटेशन आव्यूह(यानी निर्धारक 1 के साथ ऑर्थोगोनल मैट्रिक्स, जिसे ऑर्थोगोनल आव्यूहके रूप में भी जाना जाता है) की अनुमति देकर इसे बाधित कर सकता है। इस मामले में, कोई लिख सकता है (उपर्युक्त अपघटन का उपयोग करके $M=U\Sigma V^{T}$)

$R=U\Sigma 'V^{T},\,\!$

कहाँ $\Sigma '\,\!$ एक संशोधित है $\Sigma \,\!$, द्वारा प्रतिस्थापित सबसे छोटा एकवचन मान $\det(UV^{T})$ (+1 या -1), और अन्य एकवचन मानों को 1 से प्रतिस्थापित किया जाता है, ताकि आर के निर्धारक के सकारात्मक होने की गारंटी हो। अधिक जानकारी के लिए, काब्श एल्गोरिथम देखें।

यह भी देखें

• प्रोक्रस्टेस विश्लेषण
• प्रोक्रस्टेस परिवर्तन
• वहबा की समस्या
• काब्श एल्गोरिथम
• प्वाइंट सेट पंजीकरण