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

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

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

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

परिभाषा

इस लेख के उद्देश्य के लिए, यह संक्षेपण टेंसर ${\mathcal {A}}$ को मान लिया जाता है कि इसे कुछ बेसिस के संदर्भ में निर्धारित नियोजित समय के साथ दिया गया है, जिसे एक एम-रास्ता ऍरे भी कहा जाता है, जिसे ${\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}}$ एकात्मक स्तंभों वाला एक आव्यूह है जिसमें मानक कारक-एम फ़्लैटनिंग के गैर-शून्य एकवचन मानों के अनुरूप बाएं एकवचन वैक्टर का आधार होता है ${\mathcal {A}}_{[m]}$ का ${\mathcal {A}}$. के कॉलम दें ${\bf {U}}_{m}$ इस प्रकार क्रमबद्ध किया जाए कि $r_{m}$ वां स्तंभ ${\bf {u}}_{r_{m}}$ का ${\bf {U}}_{m}$ से मेल खाता है$r_{m}$का सबसे बड़ा गैर शून्य एकवचन मान ${\mathcal {A}}_{[m]}$. के कॉलम के बाद से ${\bf {U}}_{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}$ एक उपसमुच्चय के रूप में.

क्लासिक गणना

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

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

• के लिए $m=0,1,\ldots ,M$, निम्न कार्य करें:

1. मोड-एम फ़्लैटनिंग का निर्माण करें ${\mathcal {A}}_{[m]}$;
2. (कॉम्पैक्ट) एकवचन मूल्य अपघटन की गणना करें ${\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-टकर के समाधान के लिए एचओएसवीडी के समान है।