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

लाम्बिक प्रोक्रस्टेस समस्या रैखिक बीजगणित में आव्यूह सन्निकटन समस्या है। इसके चिरप्रतिष्ठित रूप में, एक को दो आव्यूह $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 से प्रतिस्थापित किया जाता है, ताकि आर के निर्धारक के सकारात्मक होने की गारंटी हो। अधिक जानकारी के लिए, काब्श एल्गोरिथम देखें।

यह भी देखें

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