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

बहुरेखीय बीजगणित में, एक टेन्सर का उच्च-क्रम एकवचन मूल्य अपघटन (HOSVD) एक विशिष्ट ऑर्थोगोनल टकर अपघटन है। इसे मैट्रिक्स एकवचन मूल्य अपघटन के एक प्रकार के सामान्यीकरण के रूप में माना जा सकता है। इसमें कंप्यूटर दृष्टि, कंप्यूटर चित्रलेख , यंत्र अधिगम , वैज्ञानिक कंप्यूटिंग और संकेत आगे बढ़ाना में अनुप्रयोग हैं। कुछ पहलुओं का पता 1928 में एफ. एल. हिचकॉक से लगाया जा सकता है, लेकिन यह एल. आर. टकर ही थे जिन्होंने 1960 के दशक में तीसरे क्रम के टेंसरों के लिए सामान्य टकर अपघटन विकसित किया था, आगे लिवेन डी लाथौवर|एल द्वारा वकालत की गई। डी लाथौवर एट अल। उनके मल्टीलिनियर एसवीडी कार्य में जो पावर विधि को नियोजित करता है, या वासिलेस्कु और टेरज़ोपोलोस द्वारा समर्थित है जिसने एम-मोड एसवीडी को एक समानांतर एल्गोरिदम विकसित किया है जो मैट्रिक्स एसवीडी को नियोजित करता है।

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

परिभाषा

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

होने देना ${\bf {U}}_{m}\in \mathbb {C} ^{I_{m}\times R_{m}}$एक एकात्मक मैट्रिक्स बनें जिसमें टेन्सर रीशेपिंग के बाएँ एकवचन वैक्टर का आधार हो | मानक मोड-एम फ़्लैटनिंग ${\mathcal {A}}_{[m]}$ का ${\mathcal {A}}$ जैसे कि jth कॉलम $\mathbf {u} _{j}$ का ${\bf {U}}_{m}$ के jवें सबसे बड़े एकवचन मान से मेल खाता है ${\mathcal {A}}_{[m]}$. ध्यान दें कि मोड/कारक मैट्रिक्स ${\bf {U}}_{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}).$$

फिर, HOSVDका ${\mathcal {A}}$ विघटन है

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

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

कॉम्पैक्ट HOSVD

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

ये मान लीजिए ${\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}}$ अवश्य होल्ड करें।

कॉम्पैक्ट HOSVD इस अर्थ में एक रैंक-खुलासा विघटन है कि इसके कोर टेंसर के आयाम टेंसर के मल्टीलाइनर रैंक के घटकों के अनुरूप हैं।

व्याख्या

निम्नलिखित ज्यामितीय व्याख्या पूर्ण और कॉम्पैक्ट HOSVD दोनों के लिए मान्य है। होने देना $(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}$ एक उपसमुच्चय के रूप में.

क्लासिक गणना

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

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

• के लिए $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}$.

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

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

अनुमान

अनुप्रयोगों में, जैसे कि नीचे उल्लिखित हैं, एक सामान्य समस्या किसी दिए गए टेंसर का अनुमान लगाना है ${\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 को प्रतिस्थापित करके एक शास्त्रीय रूप से काट दिया गया HOSVD प्राप्त किया जाता है

• एक रैंक की गणना करें-${\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}}$;

जबकि क्रमिक रूप से काटे गए HOSVD (या क्रमिक रूप से काटे गए HOSVD) को इंटरलेस्ड गणना में चरण 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}}$. दुर्भाग्य से, ट्रंकेशन के परिणामस्वरूप सर्वोत्तम निम्न बहुरेखीय रैंक अनुकूलन समस्या का इष्टतम समाधान नहीं मिलता है, हालाँकि, शास्त्रीय और इंटरलीव्ड काटे गए HOSVD दोनों का परिणाम अर्ध-इष्टतम समाधान में होता है: अगर ${\mathcal {\bar {A}}}_{t}$ शास्त्रीय या क्रमिक रूप से काटे गए HOSVD को दर्शाता है ${\mathcal {\bar {A}}}^{*}$ तब, सर्वोत्तम निम्न बहुरेखीय रैंक सन्निकटन समस्या के इष्टतम समाधान को दर्शाता है
  $$\|{\mathcal {A}}-{\mathcal {\bar {A}}}_{t}\|_{F}\leq {\sqrt {M}}\|{\mathcal {A}}-{\mathcal {\bar {A}}}^{*}\|_{F};$$
  व्यवहार में इसका मतलब यह है कि यदि एक छोटी सी त्रुटि के साथ एक इष्टतम समाधान मौजूद है, तो कई इच्छित उद्देश्यों के लिए एक छोटा HOSVD भी पर्याप्त रूप से अच्छा समाधान देगा।

अनुप्रयोग

HOSVD का उपयोग आमतौर पर बहु-मार्गीय सरणियों से प्रासंगिक जानकारी निकालने के लिए किया जाता है।

2000 के दशक की शुरुआत में, वासिलेस्कु ने डेटा विश्लेषण, पहचान और संश्लेषण समस्याओं को मल्टीलाइनर टेंसर समस्याओं के रूप में पुनः परिभाषित करके कारण संबंधी प्रश्नों को संबोधित किया। गति पहचान के लिए ह्यूमन मोशन सिग्नेचर के संदर्भ में, डेटा निर्माण के कारण कारकों के संदर्भ में एक छवि को विघटित और प्रस्तुत करके टेंसर ढांचे की शक्ति का प्रदर्शन किया गया था। चेहरे की पहचान—TensorFaces और कंप्यूटर ग्राफ़िक्स—TensorTextures। HOSVD को सिग्नल प्रोसेसिंग और बड़े डेटा, जैसे जीनोमिक सिग्नल प्रोसेसिंग में सफलतापूर्वक लागू किया गया है। इन अनुप्रयोगों ने उच्च-क्रम वाले जीएसवीडी (एचओ जीएसवीडी) को भी प्रेरित किया। और एक टेंसर जीएसवीडी। रोग निगरानी में जटिल डेटा स्ट्रीम (स्थान और समय आयामों के साथ बहुभिन्नरूपी डेटा) से वास्तविक समय में घटना का पता लगाने के लिए HOSVD और SVD का संयोजन भी लागू किया गया है। इसका उपयोग टेंसर उत्पाद मॉडल परिवर्तन-आधारित नियंत्रक डिज़ाइन में भी किया जाता है। HOSVD की अवधारणा को टीपी मॉडल परिवर्तन के माध्यम से बरनी और यम द्वारा कार्यों में ले जाया गया था।इस विस्तार ने टेंसर उत्पाद फ़ंक्शंस और लीनियर पैरामीटर वेरिंग सिस्टम मॉडल के HOSVD-आधारित विहित रूप की परिभाषा को जन्म दिया। और उत्तल पतवार हेरफेर आधारित नियंत्रण अनुकूलन सिद्धांत के लिए, नियंत्रण सिद्धांतों में टीपी मॉडल परिवर्तन देखें।

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

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

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