उच्च-क्रम एकवचन मूल्य अपघटन

बहुरेखीय बीजगणित में, टेंसर का उच्च-क्रम सिंगुलर मूल्य अपघटन (एचओएसवीडी) एक विशेष निर्देशीय टकर विघटन है। इसे एक प्रकार के आव्यूह सिंगुलर मूल्य विघटन के सामान्यीकरण के रूप में भी देखा जा सकता है। यह कंप्यूटर विजन, कंप्यूटर आरेख, यंत्र अधिगम, वैज्ञानिक कंप्यूटिंग, और संकेत प्रसंस्करण में अनुप्रयोगों के साथ उपयोग होता है।

कुछ पहलुओं का पता 1928 में एफ. एल. हिचकॉक से लगाया जा सकता है, परंतु यह एल. आर. टकर ही थे जिन्होंने 1960 के दशक में तीसरे क्रम के टेंसरों के लिए सामान्य टकर अपघटन विकसित किया था, आगे लिवेन डी लाथौवर एल द्वारा वकालत की गई। डी लाथौवर एट अल। उनके मल्टीलिनियर एसवीडी कार्य में जो पावर विधि को नियोजित करता है, या वासिलेस्कु और टेरज़ोपोलोस द्वारा समर्थित है जिसने एम-मोड एसवीडी को एक समानांतर कलन विधि विकसित किया है जो आव्यूह एसवीडी को नियोजित करता है।

उच्च क्रम सिंगुलर मूल्य अपघटन एचओएसवीडी शब्द डेलाथौवर के नाम से निर्मित किया गया था, परंतु साहित्य में सामान्यतः एचओएसवीडी के रूप में संदर्भित कलन विधि और टकर या डेलाथौवर को स्पष्टीकरणीय ठहराया गया था, जिसे वासिलेस्कु और टेरज़ोपोलोस द्वारा विकसित किया गया था। के प्रतिस्थानीय और L1-नॉर्म-आधारित विभिन्न प्रकार भी प्रस्तावित किए गए हैं।

परिभाषा

इस लेख के उद्देश्य के लिए, यह संक्षेपण टेंसर ${\mathcal {A}}$ को मान लिया जाता है कि इसे कुछ बेसिस के संदर्भ में निर्धारित नियोजित समय के साथ दिया गया है, जिसे एक M-वे सरणी भी कहा जाता है, जिसे ${\mathcal {A}}\in \mathbb {C} ^{I_{1}\times I_{2}\cdots \times \cdots I_{m}\cdots \times I_{M}}$ द्वारा भी दर्शाया जा सकता है, जहां M मोड्स और टेंसर का आदेश है। $\mathbb {C}$ वास्तविक संख्याएँ $\mathbb {R}$ और शुद्ध काल्पनिक संख्याएँ दोनों को सम्मिलित करता है।

यदि ${\mathcal {A}}$ का मानक मोड-m फ्लैटेनिंग ${\mathcal {A}}_{[m]}$ का बेसिस सम्मिलित होता है, जिसमें विशिष्ट बेसिस का एक इकाई आव्यूह ${\bf {U}}m\in \mathbb {C} ^{I_{m}\times R_{m}}$ होता है, जिसमें विद्यमान ${\mathcal {A}}{[m]}$ के बगल दिए गए विशिष्ट मोड स्थानिक गुणधर्म के आधार वक्र $\mathbf {u} _{j}$ के लिए ज्ञात होता है, जहां 'j' विशेष सबसे बड़े गुणधर्म के विशिष्ट स्तंभ ${\bf {u}}_{j}$ से मेल खाता है। ध्यान दें कि मोड/फैक्टर आव्यूह ${\bf {U}}_{m}$ विशेष मोड 'm' फ्लैटेनिंग के विशिष्ट परिभाषा पर नहीं निर्भर करती है। बहुरेखीय गुणन के गुणों से, हमारे पास है

$${\begin{array}{rcl}{\mathcal {A}}&=&{\mathcal {A}}\times ({\bf {I}},{\bf {I}},\ldots ,{\bf {I}})\\&=&{\mathcal {A}}\times ({\bf {U}}_{1}{\bf {U}}_{1}^{H},{\bf {U}}_{2}{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}{\bf {U}}_{M}^{H})\\&=&\left({\mathcal {A}}\times ({\bf {U}}_{1}^{H},{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}^{H})\right)\times ({\bf {U}}_{1},{\bf {U}}_{2},\ldots ,{\bf {U}}_{M}),\end{array}}$$

कहाँ $\cdot ^{H}$ संयुग्म स्थानान्तरण को दर्शाता है। दूसरी समानता इसलिए है क्योंकि ${\bf {U}}_{m}$'एकात्मक आव्यूह हैं। अब कोर टेंसर को परिभाषित करें

$${\mathcal {S}}:={\mathcal {A}}\times ({\bf {U}}_{1}^{H},{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}^{H}).$$

पुनः, एचओएसवीडीका विघटन ${\mathcal {A}}$ है

$${\mathcal {A}}={\mathcal {S}}\times ({\bf {U}}_{1},{\bf {U}}_{2},\ldots ,{\bf {U}}_{M}).$$

उपरोक्त निर्माण से पता चलता है कि प्रत्येक टेंसर में एक एचओएसवीडी होता है।

कॉम्पैक्ट एचओएसवीडी

जैसा कि एक आव्यूह के कॉम्पैक्ट सिंगुलर मूल्य अपघटन के स्थितियों में, एक कॉम्पैक्ट एचओएसवीडी पर विचार करना भी संभव है, जो अनुप्रयोगों में बहुत उपयोगी है।

मान लीजिए कि ${\bf {U}}m\in \mathbb {C} ^{I_{m}\times R_{m}}$ एक आव्यूह है जिसके स्तंभ इकाईवार होते हैं और जो मानक फैक्टर-m फ्लैटेनिंग ${\mathcal {A}}{[m]}$ के गैर-शून्य गुणधर्म के लिए एक बेसिस सम्मिलित करते हैं। यहां $r_{m}$ विशिष्ट स्तंभ ${\bf {u}}{r_{m}}$ को अभिलिखित किया जाए, जो मानक फैक्टर-m फ्लैटेनिंग ${\mathcal {A}}{[m]}$ के $r_{m}$वें सबसे बड़े गैर-शून्य गुणधर्म से मिलता है। ${\bf {U}}m$ के स्तंभ फैक्टर-m फ्लैटेनिंग ${\mathcal {A}}{[m]}$ के छवि के लिए एक बेसिस बनाते हैं, इससे हमें निम्नलिखित सम्बन्ध मिलता है:

$${\mathcal {A}}_{[m]}={\bf {U}}_{m}{\bf {U}}_{m}^{H}{\mathcal {A}}_{[m]}={\bigl (}{\mathcal {A}}\times _{m}({\bf {U}}_{m}{\bf {U}}_{m}^{H}){\bigr )}_{[m]},$$

जहां पहली समानता प्रक्षेपण के गुणों के कारण है और अंतिम समानता बहुरेखीय गुणन के गुणों के कारण है। चूँकि फ़्लैटनिंग विशेषणात्मक मानचित्र हैं और उपरोक्त सूत्र सभी के लिए मान्य है $m=1,2,\ldots ,m,\ldots ,M$, हम उससे पहले जैसा पाते हैं

$${\begin{array}{rcl}{\mathcal {A}}&=&{\mathcal {A}}\times ({\bf {U}}_{1}{\bf {U}}_{1}^{H},{\bf {U}}_{2}{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}{\bf {U}}_{M}^{H})\\&=&\left({\mathcal {A}}\times ({\bf {U}}_{1}^{H},{\bf {U}}_{2}^{H},\ldots ,{\bf {U}}_{M}^{H})\right)\times ({\bf {U}}_{1},{\bf {U}}_{2},\ldots ,{\bf {U}}_{M})\\&=&{\mathcal {S}}\times ({\bf {U}}_{1},{\bf {U}}_{2},\ldots ,{\bf {U}}_{M}),\end{array}}$$

जहां कोर टेंसर ${\mathcal {S}}$ अब $R_{1}\times R_{2}\times \cdots \times R_{M}$आकार का है

मल्टिलिनियर रैंक

टेंसर ${\mathcal {A}}$ का मल्टिलिनियर रैंक रैंक-$(R_{1},R_{2},\ldots ,R_{M})$ के रूप में दर्शाया जाता है। मल्टिलिनियर रैंक एक $\mathbb {N} ^{M}$ में एक ट्यूपल है, जहां $R_{m}:=\mathrm {rank} ({\mathcal {A}}{[m]})$ है। सभी ट्यूपल $\mathbb {N} ^{M}$ में मल्टिलिनियर रैंक नहीं होते हैं। मल्टिलिनियर रैंक $1\leq R_{m}\leq I_{m}$ द्वारा सीमित होते हैं और यह शर्त ${\textstyle R_{m}\leq \prod {i\neq m}R_{i}}$ को पूरा करते हैं।

कॉम्पैक्ट एचओएसवीडी उस संदर्भ में एक रैंक-प्रकटक विघटन है जिसमें इसके कोर टेंसर के आयाम टेंसर के मल्टिलिनियर रैंक के अंशों के साथ मेल खाते हैं।

व्याख्या

निम्नलिखित ज्यामितीय व्याख्या पूर्ण और कॉम्पैक्ट एचओएसवीडी दोनों के लिए मान्य है। यदि $(R_{1},R_{2},\ldots ,R_{M})$ टेंसर की मल्टिलिनियर रैंक ${\mathcal {A}}$ बनें तब यह ${\mathcal {S}}\in {\mathbb {C} }^{R_{1}\times R_{2}\times \cdots \times R_{M}}$ एक बहुआयामी सरणी है, हम इसे निम्नानुसार विस्तारित कर सकते हैं

$${\mathcal {S}}=\sum _{r_{1}=1}^{R_{1}}\sum _{r_{2}=1}^{R_{2}}\cdots \sum _{r_{M}=1}^{R_{M}}s_{r_{1},r_{2},\ldots ,r_{M}}\mathbf {e} _{r_{1}}\otimes \mathbf {e} _{r_{2}}\otimes \cdots \otimes \mathbf {e} _{r_{M}},$$

यहाँ $\mathbf {e} _{r_{m}}$ वह $r_{m}$का ${\mathbb {C} }^{I_{m}}$वां मानक आधार वेक्टर है।. मल्टिलिनियर गुणन की परिभाषा के अनुसार, यह सत्य होता है कि:

$${\mathcal {A}}=\sum _{r_{1}=1}^{R_{1}}\sum _{r_{2}=1}^{R_{2}}\cdots \sum _{r_{M}=1}^{R_{M}}s_{r_{1},r_{2},\ldots ,r_{M}}\mathbf {u} _{r_{1}}\otimes \mathbf {u} _{r_{2}}\otimes \cdots \otimes \mathbf {u} _{r_{M}},$$

,यहाँ $\mathbf {u} {r_{m}}$ वे स्तंभ हैं जो ${\bf {U}}m\in {\mathbb {C} }^{I_{m}\times R_{m}}$ के हैं। आसानी से सत्यापित किया जा सकता है कि $B={\mathbf {u} {r_{1}}\otimes \mathbf {u} {r_{2}}\otimes \cdots \otimes \mathbf {u} {r_{M}}}{r_{1},r_{2},\ldots ,r_{M}}$ एक अधार निर्धारित टेंसरों का एक अधार निर्धारित समूह है। इसका मतलब है कि एचओएसवीडी टेंसर ${\mathcal {A}}$ को एक विशेष चुने गए अधार निर्धारित अधार $B$ के संदर्भ में व्यक्त करने का एक विधि है, जिसमें गुणकों को मल्टिलिनियर सारणी ${\mathcal {S}}$ के रूप में दिया जाता है।

गणना

एक टेंसर ${\mathcal {A}}\in {\mathbb {C} }^{I_{1}\times I_{2}\times \cdots \times I_{M}}$ है, जिसमें रैंक-$(R_{1},R_{2},\ldots ,R_{M})$ है, जहां $\mathbb {C}$ में वास्तविक संख्याएँ $\mathbb {R}$ को एक उपसमूह के रूप में सम्मिलित हैं।

पारंपरिक गणना

मल्टिलिनियर एसडब्ल्यूडी और M-मोड एसडब्ल्यूडी की गणना के लिए 1960 के दशक में एल. आर. टकर ने प्रस्तुत किया था, जो बाद में एल डी लाथौवर आदि ने समर्थित किया, और वासिलेस्कु और टेरज़ोपुलस ने भी समर्थित किया। टर्म एचओएसडब्ल्यूडी को लिवेन डी लाथौवर ने बनाया था, लेकिन सामान्यतः साहित्य में एचओएसडब्ल्यूडी के लिए उपयोग किया जाने वाला कलन विधि वासिलेस्कु और टेरज़ोपोलोस ने प्रस्तुत किया था, जिसे M-मोड एसडब्ल्यूडी के नाम से भी जाना जाता है। यह एक पैरलेल गणना है जो मैट्रिक्स एसडब्ल्यूडी का उपयोग करती है जिससे अधार-उपसर्गी मोड आव्यूहो की गणना की जा सके।

एम-मोड एसवीडी:

मोड-m फ्लैटेनिंग ${\mathcal {A}}_{[m]}$ का निर्माण करें। सिंगुलर मूल्य विघटन ${\mathcal {A}}_{[m]}={\bf {U}}_{m}{\bf {\Sigma }}_{m}{\bf {V}}_{m}^{T}$ की गणना करें, और बाएँ सिंगुलर वेक्टर ${\bf {U}}\in \mathbb {C} ^{I_{m}\times R_{m}}$ को स्टोर करें।

इसके बाद मल्टिलिनियर गुणन के द्वारा मध्य टेंसर ${\mathcal {S}}$ की गणना करें: ${\mathcal {S}}={\mathcal {A}}\times _{0}{\bf {U}}_{0}^{H}\times _{1}{\bf {U}}_{1}^{H}\times _{2}{\bf {U}}_{2}^{H}\ldots \times _{m}{\bf {U}}_{m}^{H}\ldots \times _{M}{\bf {U}}_{M}^{H}$

इंटरलेसिंग गणना

जब कुछ या सभी $r_{k}\ll n_{k}$ हों, तो एक रणनीति जिसमें मध्य टेंसर और कारक आव्यूह की गणना को निम्नानुसार सम्मिलित किया गया है,जो निम्नलिखित रूप से होता है

• यदि ${\mathcal {A}}^{0}={\mathcal {A}}$;
• के लिए $m=0,1,2\ldots ,M$ निम्नलिखित कार्य करें:
  1. मानक मोड-एम फ़्लैटनिंग ${\mathcal {A}}_{[m]}^{m-1}$ का निर्माण करें ;
  2. कॉम्पैक्ट सिंगुलर मूल्य विघटन की गणना करें ${\mathcal {A}}_{[m]}^{m-1}=U_{m}\Sigma _{m}V_{m}^{T}$, और बाएँ सिंगुलर वैक्टर $U_{m}\in F^{I_{m}\times R_{m}}$को संग्रहीत करें :
  3. यदि ${\mathcal {A}}^{m}=U_{m}^{H}\times _{m}{\mathcal {A}}^{m-1}$, या, समकक्ष, ${\mathcal {A}}_{[m]}^{m}=\Sigma _{m}V_{m}^{T}$.

इन-प्लेस गणना

एचओएसवीडी की गणना फ़्यूज्ड इन-प्लेस अनुक्रमिक रूप से उच्च क्रम सिंगुलर कलन विधि के माध्यम से प्लेस में गणना कर सकते हैं जिसमें मूल टेंसर को एचओएसवीडी कोर टेंसर से ओवरराइट किया जाता है, जिससे एचओएसवीडी की गणना में मेमोरी का उपयोग बहुत कम हो जाता है।

अनुमान

एप्लिकेशन में, निम्नलिखित जैसे कई समस्याएं होती हैं, जिनमें एक दिए गए टेंसर ${\mathcal {A}}\in \mathbb {C} ^{I_{1}\times I_{2}\times \cdots \times I_{m}\cdots \times I_{M}}$ को एक कम मल्टिलिनियर रैंक वाले टेंसर से अनुमानित करने की सामान्य समस्या होती है। यथार्थरूप से, यदि ${\mathcal {A}}$ का मल्टिलिनियर रैंक $\mathrm {rank-} (R_{1},R_{2},\ldots ,R_{m},\ldots ,R_{M})$ द्वारा दर्शाया जाता है, तो एक दिए गए घटित $\mathrm {rank-} ({\bar {R}}_{1},{\bar {R}}_{2},\ldots ,{\bar {R}}_{m},\ldots ,{\bar {R}}_{M})$ के लिए ${\mathcal {A}}$ को अनुमानित करने के लिए सबसे अच्छा ${\mathcal {\bar {A}}}$ गणना एक गैर-समतल गैर-विसंक्लिष $\ell _{2}$-अनुकूलन समस्या होती है।

$$\min _{{\mathcal {\bar {A}}}\in \mathbb {C} ^{I_{1}\times I_{2}\times \cdots \times I_{M}}}{\frac {1}{2}}|{\mathcal {A}}-{\mathcal {\bar {A}}}|_{F}^{2}\quad {\text{s.t.}}\quad \mathrm {rank-} ({\bar {R}}_{1},{\bar {R}}_{2},\ldots ,{\bar {R}}_{M}),$$

जहां $({\bar {R}}_{1},{\bar {R}}_{2},\ldots ,{\bar {R}}_{M})\in \mathbb {N} ^{M}$ कम मल्टिलिनियर रैंक है जिसमें $1\leq {\bar {R}}_{m}<R_{m}\leq I_{m}$ है, और नॉर्म $|.|_{F}$ फ्रोबेनियस नॉर्म है।

इस अनुकूलन समस्या को हल करने का प्रयास करने का एक सरल विचार पारंपरिक या इंटरलेस्ड गणना के चरण 2 में एसवीडी को छोटा करना है। पारंपरिक गणना में चरण 2 को प्रतिस्थापित करके एक पारंपरिक रूप से ट्रंकेशन किया दिया गया एचओएसवीडी प्राप्त किया जाता है

• संख्या ${\bar {R}}_{m}$ के लिए एक संक्षेपित SVD ${\mathcal {A}}_{[m]}\approx U_{m}\Sigma _{m}V_{m}^{T}$ गणना करें, और शीघ्र चलनेवाले ${\bar {R}}_{m}$ बाएँ सिंगुलर वेक्टर $U_{m}\in F^{I_{m}\times {\bar {R}}_{m}}$ को संग्रहीत करें; जबकि एक क्रमिक रूप से ट्रंकेशन गई एचओएसवीडी उन्हें अंतर्विष्ट गणना के स्टेप 2 में निम्नलिखित रूप से प्राप्त की जाती है:
• गणना करें ${\bar {R}}_{m}$ के लिए एक संक्षेपित रैंक SVD ${\mathcal {A}}_{[m]}^{m-1}\approx U_{m}\Sigma _{m}V_{m}^{T}$, और ऊपरी ${\bar {R}}_{m}$ बाएँ सिंगुलर वेक्टर $U_{m}\in F^{I_{m}\times {\bar {R}}_{m}}$ को संग्रहीत करें। सामान्यतः, ट्रंकेशन का परिणाम एक सर्वोत्तम समान्तरिक रैंक अनुकूलन समस्या के लिए एक आदर्श समाधान नहीं होता है। यद्यपि, परंपरिक रूप से और अंतर्विष्ट किए गए कटाई गई एचओएसवीडी दोनों ही क्वासी-आदर्श समाधान प्रदान करते हैं: यदि ${\mathcal {\bar {A}}}_{t}$ को पारंपरिक या क्रमिक रूप से ट्रंकेशन की गई एचओएसवीडी और ${\mathcal {\bar {A}}}^{*}$ को सर्वोत्तम समान्तरिक रैंक अनुकूलन समस्या के लिए आदर्श समाधान दिखाता है, तो
  $$|{\mathcal {A}}-{\mathcal {\bar {A}}}_{t}|_{F}\leq {\sqrt {M}}|{\mathcal {A}}-{\mathcal {\bar {A}}}^{*}|_{F};$$
  व्यावहारिक रूप से इसका अर्थ है कि यदि एक छोटी त्रुटि वाले आदर्श समाधान है, तो बहुत सारे उद्देश्यों के लिए ट्रंकेशन गई एचओएसवीडी भी एक पर्याप्त अच्छा समाधान देगी।

अनुप्रयोग

एचओएसवीडी का सबसे सामान्य रूप से उपयोग बहुदिशीय सारणी से संबंधित महत्वपूर्ण जानकारी को निकालने में किया जाता है।

2000 के प्रारंभिक दशक से प्रारंभ करके, वासिलेस्कू ने कारण संबंधी प्रश्नों का समाधान करने के लिए डेटा विश्लेषण, पहचान और संश्लेषण समस्याओं को बहुदिशीय टेंसर समस्याओं के रूप में फिर से तैयार किया। गति पहचान के लिए ह्यूमन मोशन सिग्नेचर के संदर्भ में, डेटा निर्माण के कारण कारकों के संदर्भ में एक छवि को विघटित और प्रस्तुत करके टेंसर ढांचे की शक्ति का प्रदर्शन किया गया था। जैसे, चेहरे की पहचान—टेंसरफेसेस और कंप्यूटर ग्राफ़िक्स—टेंसर टेक्सचर।

एचओएसवीडी को सिग्नल प्रोसेसिंग और बड़े डेटा, जैसे जीनोमिक सिग्नल प्रोसेसिंग में सफलतापूर्वक लागू किया गया है। इन अनुप्रयोगों ने उच्च-क्रम वाले जीएसवीडी को भी प्रेरित किया। और एक टेंसर जीएसवीडी।रोग निगरानी में जटिल डेटा स्ट्रीम से वास्तविक समय में घटना का पता लगाने के लिए एचओएसवीडी और एसडब्ल्यूडी का संयोजन भी लागू किया गया है।

इसका उपयोग टेंसर उत्पाद मॉडल परिवर्तन-आधारित नियंत्रक डिज़ाइन में भी किया जाता है। एचओएसवीडी की अवधारणा को टीपी मॉडल परिवर्तन के माध्यम से बरनी और m द्वारा कार्यों में ले जाया गया था।

इस विस्तार से टेंसर प्रोडक्ट फंक्शन्स और लीनियर पैरामीटर वैरिंग सिस्टम मॉडलों के आधार पर एचओएसवीडी आधारित कैनोनिकल रूप की परिभाषा का उदय हुआ। इससे अवकलन परिचालन सिद्धांत आधारित नियंत्रण अनुकूलन सिद्धांत का विकास हुआ।

एचओएसवीडी को बहु-दृश्य डेटा विश्लेषण पर लागू करने का प्रस्ताव दिया गया था और जीन अभिव्यक्ति से सिलिको दवा की खोज में इसे सफलतापूर्वक लागू किया गया।

सुदृढ़ L1-मानक संस्करण

L1-टकर टकर अपघटन का L1-मानक-आधारित, सुदृढ़ सांख्यिकी संस्करण है।L1-एचओएसवीडी, L1-टकर के समाधान के लिए एचओएसवीडी के समान है।