張量分解與低秩張量補(bǔ)全算法綜述目錄TOC\o"1-3"\h\u17710張量分解與低秩張量補(bǔ)全算法綜述 1315611.1張量數(shù)學(xué)基礎(chǔ) 1306291.2張量分解算法 494641.3低秩張量補(bǔ)全算法 6張量數(shù)學(xué)基礎(chǔ)本文采用通用的張量符號(hào)定義ADDINEN.CITE<EndNote><Cite><Author>Kolda</Author><Year>2009</Year><RecNum>6</RecNum><DisplayText><styleface="superscript">[10]</style></DisplayText><record><rec-number>6</rec-number><foreign-keys><keyapp="EN"db-id="ep09pswxdx9eeoe9epe5srru9spet9w5ffea"timestamp="1587276844">6</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>Kolda,TamaraG</author><author>Bader,BrettW</author></authors></contributors><titles><title>Tensordecompositionsandapplications</title><secondary-title>SIAMreview</secondary-title></titles><periodical><full-title>SIAMreview</full-title></periodical><pages>455-500</pages><volume>51</volume><number>3</number><dates><year>2009</year></dates><isbn>0036-1445</isbn><urls></urls></record></Cite></EndNote>[10]。標(biāo)量用大小寫字母表示，例如，矢量和向量用加粗的小寫字母表示，例如，矩陣由加粗的大寫字母表示，例如，張量用加粗手寫體表示，例如。張量是一個(gè)多維矩陣或者說(shuō)是多維數(shù)組，向量和矩陣實(shí)際上也可以分別看作是一維張量和二維張量，我們常說(shuō)的張量的維數(shù)也是張量的階數(shù)，表示一個(gè)張量在空間中具有多少個(gè)維度。設(shè)表示各維度大小，表示一個(gè)大小為的階張量，它的元素可以表示為：，其中。圖2.1是以三階張量為例的張量示意圖。圖2.1三階張量示意圖張量的纖維，類似于矩陣的行和列，定義為：固定除一個(gè)模式外的其他所有模式。以一個(gè)三階張量為例，它有三個(gè)模態(tài)的纖維，分別是行纖維、列纖維、管纖維，記為，，。高階張量也可以用矩陣的集合表示，三階張量的水平切片、側(cè)向切片、正面切片分別使用矩陣符號(hào)，，表示。（1）張量模-n展開：張量的模-n展開是將張量轉(zhuǎn)換成矩陣，其中模-n纖維作為矩陣的列向量排列，記為。張量的元素映射到矩陣元素中，其中變量如式（2-1）：（2-1）（2）張量模-n矩陣乘積：張量和矩陣的乘積表示為，且大小為。定義如式（2-2）所示：（2-2）其表示成沿模-n展開的形式為：。并且張量-矩陣乘積具有可連乘，可交換的性質(zhì)如式（2-3）所示：（2-3）（3）張量的內(nèi)積：兩個(gè)階數(shù)相同的張量的內(nèi)積是所有元素逐個(gè)相乘的累加求和，定義如式（2-4）所示：（2-4）（4）張量的外積：外積用運(yùn)算符號(hào)表示，對(duì)張量和張量的外積定義如式（2-5）所示：（2-5）（5）張量Frobenius范數(shù)：張量的Frobenius范數(shù)定義如式（2-6）所示：（2-6）（6）秩1張量：一個(gè)N階張量可以表示為N個(gè)非零列向量的外積，則可以稱為秩1張量，形式如式（2-7）所示：（2-7）其中。中的元素也可以表示為式（2-8）：（2-8）如圖2.2中表示的是一個(gè)三階秩1張量。圖2.2三階秩一張量（7）張量的秩：張量的秩定義為定義為分解成秩1張量線性組合的最小數(shù)目。（8）張量的模-n秩，其定義如式（2-9）所示：（2-9）（9）張量核范數(shù)：張量的核范數(shù)可以看作由張量按各模展開得到的矩陣的核范數(shù)加權(quán)求和得到，定義如式（2-10）所示：（2-10）其中滿足且，是張量按模-n展開矩陣的核范數(shù)。對(duì)一個(gè)矩陣，核范數(shù)是矩陣奇異值之和，具有如式（2-11）的性質(zhì)：（2-11）其中，是矩陣中第i個(gè)最大奇異值。（10）張量的t-乘積（t-product）：對(duì)兩個(gè)三階張量和的t-乘積記作，令，定義如式（2-12）所示：（2-12）其中的*表示卷積運(yùn)算，表示對(duì)張量的模態(tài)纖維提取。（11）張量中表示將張量的模-n展開矩陣重新合成張量，即是張量矩陣化的反向操作。（12）單位張量：以三階張量為例，如果是單位張量，則滿足式（2-13）：（2-13）（13）正交張量：如果張量滿足，則稱之為正交張量。張量分解算法張量分解是張量分析中的重要研究?jī)?nèi)容，本文也是通過(guò)對(duì)張量分解的研究來(lái)進(jìn)行低秩張量補(bǔ)全問(wèn)題的研究。張量分解可以得到高階數(shù)據(jù)的低維表達(dá)，并且保留了數(shù)據(jù)中的高階結(jié)構(gòu)特征。本節(jié)主要介紹了1.2.1節(jié)中提及的經(jīng)典CP分解、Tucker分解、t-SVD分解和本文應(yīng)用的張量Tensor-train分解等。（1）CANDECOMP/PARFAC(CP)分解ADDINEN.CITE<EndNote><Cite><Author>Kiers</Author><Year>2000</Year><RecNum>138</RecNum><DisplayText><styleface="superscript">[4]</style></DisplayText><record><rec-number>138</rec-number><foreign-keys><keyapp="EN"db-id="ep09pswxdx9eeoe9epe5srru9spet9w5ffea"timestamp="1615634299">138</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>Kiers,HenkAL</author></authors></contributors><titles><title>Towardsastandardizednotationandterminologyinmultiwayanalysis</title><secondary-title>JournalofChemometrics:AJournaloftheChemometricsSociety</secondary-title></titles><periodical><full-title>JournalofChemometrics:AJournaloftheChemometricsSociety</full-title></periodical><pages>105-122</pages><volume>14</volume><number>3</number><dates><year>2000</year></dates><isbn>0886-9383</isbn><urls></urls></record></Cite></EndNote>[4]：CP分解是將一個(gè)N階張量分解成若干個(gè)秩1張量的和的形式，即如式（2-14）所示：（2-14）其中，若式（2-14）中約等號(hào)變成等號(hào)成立，則說(shuō)明張量能分解成R個(gè)秩1張量的和，滿足條件的最小R是張量的CP秩。圖2.3是一個(gè)三階張量的CP分解示意圖。圖2.3三階張量的CP分解示意圖（2）Tucker分解ADDINEN.CITE<EndNote><Cite><Author>Tucker</Author><Year>1963</Year><RecNum>128</RecNum><DisplayText><styleface="superscript">[5]</style></DisplayText><record><rec-number>128</rec-number><foreign-keys><keyapp="EN"db-id="ep09pswxdx9eeoe9epe5srru9spet9w5ffea"timestamp="1615269026">128</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>L.R.Tucker</author></authors></contributors><titles><title>Implicationsoffactoranalysisofthree-waymatricesformeasurementofchange</title><secondary-title>ProblemsinMeasuringChange,C.W.Harris,ed.,UniversityofWisconsinPress</secondary-title></titles><periodical><full-title>ProblemsinMeasuringChange,C.W.Harris,ed.,UniversityofWisconsinPress</full-title></periodical><pages>122–137</pages><dates><year>1963</year></dates><urls></urls></record></Cite></EndNote>[5]：Tucker分解是將一個(gè)N階張量分解成一個(gè)核心張量和因子矩陣在每個(gè)模的乘積，是一種高階主成分分析（PCA），分解定義如式（2-15）所示：（2-15）其中因子矩陣通常是正交的，可以看作每個(gè)模的主成分，張量中的每一個(gè)元素如式（2-16）：（2-16）Tucker分解的矩陣形式如（2-17）所示：（2-17）圖2.4是一個(gè)三階張量的Tucker分解情況示意圖。圖2.4三階張量的Tucker分解示意圖（3）t-SVD分解ADDINEN.CITE<EndNote><Cite><Author>Kilmer</Author><Year>2013</Year><RecNum>141</RecNum><DisplayText><styleface="superscript">[6]</style></DisplayText><record><rec-number>141</rec-number><foreign-keys><keyapp="EN"db-id="ep09pswxdx9eeoe9epe5srru9spet9w5ffea"timestamp="1615637590">141</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>Kilmer,MishaE</author><author>Braman,Karen</author><author>Hao,Ning</author><author>Hoover,RandyC</author></authors></contributors><titles><title>Third-ordertensorsasoperatorsonmatrices:Atheoreticalandcomputationalframeworkwithapplicationsinimaging</title><secondary-title>SIAMJournalonMatrixAnalysisApplications</secondary-title></titles><periodical><full-title>SIAMJournalonMatrixAnalysisApplications</full-title></periodical><pages>148-172</pages><volume>34</volume><number>1</number><dates><year>2013</year></dates><isbn>0895-4798</isbn><urls></urls></record></Cite></EndNote>[6]：對(duì)于一個(gè)給定的三階張量，t-SVD分解定義如式（2-18）所示：（2-18）其中和是正交張量，是對(duì)角張量。張量的管道秩（tubalrank）定義為張量模-3展開的向量個(gè)數(shù)。（4）Tensor-train分解ADDINEN.CITE<EndNote><Cite><Author>Oseledets</Author><Year>2011</Year><RecNum>5</RecNum><DisplayText><styleface="superscript">[17]</style></DisplayText><record><rec-number>5</rec-number><foreign-keys><keyapp="EN"db-id="ep09pswxdx9eeoe9epe5srru9spet9w5ffea"timestamp="1587119006">5</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>Oseledets,IvanV</author></authors></contributors><titles><title>Tensor-traindecomposition</title><secondary-title>SIAMJournalonScientificComputing</secondary-title></titles><periodical><full-title>SIAMJournalonScientificComputing</full-title></periodical><pages>2295-2317</pages><volume>33</volume><number>5</number><dates><year>2011</year></dates><isbn>1064-8275</isbn><urls></urls></record></Cite></EndNote>[17]：張量Tensor-train分解是將一個(gè)高階張量分解成一組三階核心張量的方式，以下用TT指代，給定張量的TT分解形式用元素表達(dá)如式（2-19）：（2-19）其中表示核心張量的第個(gè)側(cè)面切片矩陣，即大小為的矩陣。為了使切片矩陣的最終乘積是一個(gè)標(biāo)量，邊界條件需是。因此每個(gè)核心張量是大小為的三階張量，其中中間階大小為，表示原始張量對(duì)應(yīng)階的維數(shù)，另外兩階的維數(shù)稱為TT秩，相鄰的核心張量之間由相同的秩相連。因此也可以寫成如式（2-20）的索引形式：（2-20）對(duì)于TT秩的定義，首先需要介紹一種矩陣化展開方式ADDINEN.CITE<EndNote><Cite><Author>Bengua</Author><Year>2017</Year><RecNum>11</RecNum><DisplayText><styleface="superscript">[43]</style></DisplayText><record><rec-number>11</rec-number><foreign-keys><keyapp="EN"db-id="ep09pswxdx9eeoe9epe5srru9spet9w5ffea"timestamp="1587361700">11</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>Bengua,JohannA</author><author>Phien,HoN</author><author>Tuan,HoangDuong</author><author>Do,MinhN</author></authors></contributors><titles><title>Efficienttensorcompletionforcolorimageandvideorecovery:Low-ranktensortrain</title><secondary-title>IEEETransactionsonImageProcessing</secondary-title></titles><periodical><full-title>IEEETransactionsonImageProcessing</full-title></periodical><pages>2466-2479</pages><volume>26</volume><number>5</number><dates><year>2017</year></dates><isbn>1057-7149</isbn><urls><related-urls><url>/document/7859390/</url></related-urls></urls></record></Cite></EndNote>[43]，對(duì)給定張量，定義矩陣分解為（，），即沿k模矩陣化，在MATLAB中這點(diǎn)可用reshape函數(shù)實(shí)現(xiàn)。TT秩（）分別是對(duì)應(yīng)矩陣的秩，。本文用運(yùn)算符表示核心張量生成近似張量的過(guò)程，即。低秩張量補(bǔ)全算法本節(jié)先介紹了低秩張量補(bǔ)全的基礎(chǔ)模型，并從1.2.2節(jié)中提及的幾個(gè)經(jīng)典低秩張量補(bǔ)全問(wèn)題中選取幾個(gè)常用方法作為代表進(jìn)行較為詳細(xì)的描述，還介紹了常用的優(yōu)化求解方法，為接下來(lái)本文提出的低秩張量補(bǔ)全算法模型作理論鋪墊。根據(jù)低秩矩陣補(bǔ)全的秩最小化模型可以擴(kuò)展得到對(duì)低秩張量補(bǔ)全問(wèn)題的秩最小化模型，即對(duì)于給定的張量，根據(jù)張量的已知部分集合Ω，用以下秩最小化模型得到恢復(fù)的張量，可得式（2-21）：（2-21）（1）低秩張量補(bǔ)全（LowRankTensorCompletion，LRTC）：由LiuADDINEN.CITE<EndNote><Cite><Author>Liu</Author><Year>2012</Year><RecNum>160</RecNum><DisplayText><styleface="superscript">[19]</style></DisplayText><record><rec-number>160</rec-number><foreign-keys><keyapp="EN"db-id="ep09pswxdx9eeoe9epe5srru9spet9w5ffea"timestamp="1616247283">160</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>Liu,Ji</author><author>Musialski,Przemyslaw</author><author>Wonka,Peter</author><author>Ye,Jieping</author></authors></contributors><titles><title>Tensorcompletionforestimatingmissingvaluesinvisualdata</title><secondary-title>IEEEtransactionsonpatternanalysismachineintelligence</secondary-title></titles><periodical><full-title>IEEEtransactionsonpatternanalysismachineintelligence</full-title></periodical><pages>208-220</pages><volume>35</volume><number>1</number><dates><year>2012</year></dates><isbn>0162-8828</isbn><urls></urls></record></Cite></EndNote>[19]等人提出了以下的低n-秩最小化張量補(bǔ)全模型，如式（2-22）所示：（2-22）其中是給定的權(quán)重，且，是補(bǔ)全張量的模-n矩陣化，由張量沿著每個(gè)模展開的矩陣的加權(quán)秩最小化來(lái)表示張量秩最小化。與低秩矩陣補(bǔ)全問(wèn)題相似，該低n-秩最小化張量補(bǔ)全模型是NP難問(wèn)題，而核范數(shù)最小化問(wèn)題作為秩最小化問(wèn)題的凸松馳形式，更便于求解，同時(shí)他們也給出了張量核范數(shù)的定義，如式（2-23）所示：（2-23）通過(guò)張量核范數(shù)的定義，式（2-22）可以寫成如式（2-24）的形式：（2-24）對(duì)以上問(wèn)題，還提出了三種不同的優(yōu)化方法：SiLRTC，F(xiàn)aLRTC，HaLRTC，其中HaLRTC使用的是交替方向乘子法（ADMM），由于本文也采用了這種經(jīng)典的優(yōu)化方法，在此以HaLRTC算法為例對(duì)張量補(bǔ)全問(wèn)題中ADMM方法進(jìn)行簡(jiǎn)單的介紹。對(duì)優(yōu)化目標(biāo)的式（2-24）引入n個(gè)輔助矩陣，得到式（2-25）：（2-25）使用ADMM方法可以得到增廣拉格朗日函數(shù)，如式（2-26）所示：（2-26）其中,是乘子，接著對(duì)其中元素進(jìn)行迭代更新，可得式（2-27）、式（2-28）以及式（2-29）：（2-27）（2-28）（2-29）其中還有一些優(yōu)化子問(wèn)題也可以求得顯式解，經(jīng)過(guò)多次迭代逐漸更新求解，最終得到的解即使近似低秩張量。（2）低秩張量固定點(diǎn)補(bǔ)全算法（FPTC）ADDINEN.CITE<EndNote><Cite><Author>Yang</Author><Year>2013</Year><RecNum>132</RecNum><DisplayText><styleface="superscript">[20]</style></DisplayText><record><rec-number>132</rec-number><foreign-keys><keyapp="EN"db-id="ep09pswxdx9eeoe9epe5srru9spet9w5ffea"timestamp="1615553126">132</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>Yang,Lei</author><author>Huang,Zheng-Hai</author><author>Shi,Xianjun</author></authors></contributors><titles><title>Afixedpointiterativemethodforlown-ranktensorpursuit</title><secondary-title>IEEETransactionsonSignalProcessing</secondary-title></titles><periodical><full-title>IEEETransactionsonSignalProcessing</full-title></periodical><pages>2952-2962</pages><volume>61</volume><number>11</number><dates><year>2013</year></dates><isbn>1053-587X</isbn><urls></urls></record></Cite></EndNote>[20]：作為固定點(diǎn)連續(xù)奇異值分解（FPCA）到張量補(bǔ)全的擴(kuò)展，該方法的模型如式（2-30）：（2-30）其中是線性投影，，并且給定向量。令，。通過(guò)算子分裂方法，引入輔助變量矩陣，即，由此上式可以轉(zhuǎn)換成式（2-31）：（2-31）通過(guò)固定點(diǎn)迭代按式（2-32）方法求解式（2-31）：（2-32）其中folding運(yùn)算是將模-n展開的矩陣重新張量化恢復(fù)得到的張量形式。（3）張量補(bǔ)全的矩陣分解方法（MFTC）ADDINEN.CITE<EndNote><Cite><Author>Liu</Author><Year>2013</Year><RecNum>135</RecNum><DisplayText><styleface="superscript">[21]</style></DisplayText><record><rec-number>135</rec-number><foreign-keys><keyapp="EN"db-id="ep09pswxdx9eeoe9epe5srru9spet9w5ffea"timestamp="1615617875">135</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>Liu,Yuanyuan</author><author>Shang,Fanhua</author></authors></contributors><titles><title>Anefficientmatrixfactorizationmethodfortensorcompletion</title><secondary-title>IEEESignalProcessingLetters</secondary-title></titles><periodical><full-title>IEEESignalProcessingLetters</full-title></periodical><pages>307-310</pages><volume>20</volume><number>4</number><dates><year>2013</year></dates><isbn>1070-9908</isbn><urls></urls></record></Cite></EndNote>[21]：由于矩陣核范數(shù)在正交變換中是固定不變的，因此可以得到式（2-33）：（2-33）其中，，，表示Stiefel流形是所有按列正交的矩陣集合，從中可以看出遠(yuǎn)比小。為了降低SVD計(jì)算的復(fù)雜度，該方法考慮用替換，因此提出張量補(bǔ)全的矩陣分解方法，于是式（2-33）可以寫成如式（2-34）的形式：（2-34）再對(duì)上式松弛得到式（2-35）：（2-35）求解可得式（2-36）：（2-36）其中，QR是QR分解的運(yùn)算符。（4）張量同時(shí)分解和補(bǔ)全方法（STDC）ADDINEN.CITE<EndNote><Cite><Author>Chen</Author><Year>2013</Year><RecNum>134</RecNum><DisplayText><styleface="superscript">[23]</style></DisplayText><record><rec-number>134</rec-number><foreign-keys><keyapp="EN"db-id="ep09pswxdx9eeoe9epe5srru9spet9w5ffea"timestamp="1615616505">134</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>Chen,Yi-Lei</author><author>Hsu,Chiou-Ting</author><author>Liao,Hong-YuanMark</author></authors></contributors><titles><title>Simultaneoustensordecompositionandcompletionusingfactorpriors</title><secondary-title>IEEEtransactionsonpatternanalysismachineintelligence</secondary-title></titles><periodical><full-title>IEEEtransactionsonpatternanalysismachineintelligence</full-title></periodical><pages>577-591</pages><volume>36</volume><number>3</number><dates><year>2013</year></dates><isbn>0162-8828</isbn><urls></urls></record></Cite></EndNote>[23]：張量同時(shí)分解和補(bǔ)全方法是結(jié)合秩最小化與Tucker分解提出的一種方法，其中還考慮了Tucker因子先驗(yàn)?zāi)Ｐ?，具體如式（2-37）所示：（2-37）其中，是對(duì)角線元素為的對(duì)角矩陣，是因子先驗(yàn)?zāi)Ｐ偷妮o助信息矩陣。上式的拉格朗日形式如式（2-38）所示：（2-38）利用不精確的增強(qiáng)拉格朗日乘數(shù)（IALM）方法求解上式。（5）張量分解與補(bǔ)全的高階正交迭代法（HOOI）ADDINEN.CITE<EndNote><Cite><Author>Liu</Author><Year>2014</Year><RecNum>133</RecNum><DisplayText><styleface="superscript">[22]</style></DisplayText><record><rec-number>133</rec-number><foreign-keys><keyapp="EN"db-id="ep09pswxdx9eeoe9epe5srru9spet9w5ffea"timestamp="1615556819">133</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>Liu,Y.</author><author>Shang,F.</author><author>Fan,W.</author><author>Cheng,J.</author><author>Cheng,H.</author></authors></contributors><titles><title>GeneralizedHigher-OrderOrthogonalIterationforTensorDecompositionandCompletion</title><secondary-title>AdvancesinNeuralInformationProcessingSystems</secondary-title></titles><periodical><full-title>AdvancesinNeuralInformationProcessingSystems</full-title></periodical><pages>1763-1771</pages><volume>2</volume><dates><year>2014</year></dates><urls></urls></record></Cite></EndNote>[22]：由Tucker分解可知核心張量遠(yuǎn)小于原始張量的大小，該方法提出高階正交迭代方法解決核心張量的模-n展開矩陣的核范數(shù)最小化問(wèn)題，式（2-39）是Tucker分解與核心核范數(shù)的新形式：（2-39）引入輔助變量，上式可以轉(zhuǎn)換成式（2-40）的形式：（2-40）然后可以運(yùn)用交替方向乘子法（ADMM）求解。（6）Tesnor-train交替最小化法（TCAM-TT）ADDINEN.CITE<EndNote><Cite><Author>Wang</Author><Year>2016</Year><RecNum>39</RecNum><DisplayText><styleface="superscript">[27]</style></DisplayText><record><rec-number>39</rec-number><foreign-keys><keyapp="EN"db-id=