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

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

यह भी देखें

• प्रोक्रस्टेस विश्लेषण
• प्रोक्रस्टेस रूपांतरण
• वहबा की समस्या
• काब्श कलनविधि
• बिन्दु समुच्चय पंजीयन