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

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

कुछ पहलुओं का पता 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}}$ एक अधार निर्धारित टेंसरों का एक अधार निर्धारित समूह है। इसका मतलब है कि HOSVD टेंसर ${\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}$ को एक उपसमूह के रूप में सम्मिलित हैं।

क्लासिक गणना

बहुधिमीय SVD और M-मोड SVD की गणना के लिए रणनीति को 1960 के दशक में L. R. Tucker ने प्रस्तुत किया था, जो बाद में L. De Lathauwer आदि ने समर्थित किया, और Vasilescu और Terzopulous ने भी समर्थित किया। टर्म HOSVD को Lieven De Lathauwer ने बनाया था, लेकिन सामान्यतः साहित्य में HOSVD के लिए उपयोग किया जाने वाला एल्गोरिदम Vasilescu और Terzopoulos ने प्रस्तुत किया था, जिसे M-मोड SVD के नाम से भी जाना जाता है। यह एक पैरलेल गणना है जो मैट्रिक्स SVD का उपयोग करती है ताकि अधार-उपसर्गी मोड मैट्रिक्सों की गणना की जा सके।

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

$m=0,1,\ldots ,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}$.

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

एचओएसवीडी की गणना फ़्यूज्ड इन-प्लेस सीक्वेंशियली ट्रंकेटेड हायर ऑर्डर सिंगुलर वैल्यू डीकंपोजिशन (FIST-एचओएसवीडी) के माध्यम से की जा सकती है। एचओएसवीडी कोर टेंसर द्वारा मूल टेंसर को ओवरराइट करके कलन विधि , एचओएसवीडी की गणना करने की मेमोरी खपत को काफी कम कर देता है।

अनुमान

अनुप्रयोगों में, जैसे कि नीचे उल्लिखित हैं, एक सामान्य समस्या किसी दिए गए टेंसर का अनुमान लगाना है ${\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})$, फिर इष्टतम की गणना करें ${\mathcal {\bar {A}}}$ वह अनुमानित है ${\mathcal {A}}$ किसी दिए गए कम के लिए $\mathrm {rank-} ({\bar {R}}_{1},{\bar {R}}_{2},\ldots ,{\bar {R}}_{m},\ldots ,{\bar {R}}_{M})$ एक अरैखिक गैर-उत्तल है $\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}$ छोटा किया गया एसवीडी ${\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}$ छोटा किया गया एसवीडी ${\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 के दशक की शुरुआत में, वासिलेस्कु ने डेटा विश्लेषण, पहचान और संश्लेषण समस्याओं को मल्टीलाइनर टेंसर समस्याओं के रूप में पुनः परिभाषित करके कारण संबंधी प्रश्नों को संबोधित किया। गति पहचान के लिए ह्यूमन मोशन सिग्नेचर के संदर्भ में, डेटा निर्माण के कारण कारकों के संदर्भ में एक छवि को विघटित और प्रस्तुत करके टेंसर ढांचे की शक्ति का प्रदर्शन किया गया था। चेहरे की पहचान—TensorFaces और कंप्यूटर ग्राफ़िक्स—TensorTextures। एचओएसवीडी को सिग्नल प्रोसेसिंग और बड़े डेटा, जैसे जीनोमिक सिग्नल प्रोसेसिंग में सफलतापूर्वक लागू किया गया है। इन अनुप्रयोगों ने उच्च-क्रम वाले जीएसवीडी (एचओ जीएसवीडी) को भी प्रेरित किया। और एक टेंसर जीएसवीडी। रोग निगरानी में जटिल डेटा स्ट्रीम (स्थान और समय आयामों के साथ बहुभिन्नरूपी डेटा) से वास्तविक समय में घटना का पता लगाने के लिए एचओएसवीडी और SVD का संयोजन भी लागू किया गया है। इसका उपयोग टेंसर उत्पाद मॉडल परिवर्तन-आधारित नियंत्रक डिज़ाइन में भी किया जाता है। एचओएसवीडी की अवधारणा को टीपी मॉडल परिवर्तन के माध्यम से बरनी और यम द्वारा कार्यों में ले जाया गया था।इस विस्तार ने टेंसर उत्पाद फ़ंक्शंस और लीनियर पैरामीटर वेरिंग सिस्टम मॉडल के एचओएसवीडी-आधारित विहित रूप की परिभाषा को जन्म दिया। और उत्तल पतवार हेरफेर आधारित नियंत्रण अनुकूलन सिद्धांत के लिए, नियंत्रण सिद्धांतों में टीपी मॉडल परिवर्तन देखें।

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

मजबूत एल1-मानक संस्करण

L1-टकर टकर अपघटन का Lp_space|L1-मानदंड-आधारित, मजबूत_सांख्यिकी संस्करण है।L1-एचओएसवीडी, L1-टकर के समाधान के लिए एचओएसवीडी के समान है।