基于張量鏈分解的低秩張量補全研究

豆 蔻，吳云韜*，黃龍庭，陳 里

1.武漢工程大學計算機科學與工程學院，湖北 武漢430205；2.武漢理工大學信息學院，湖北 武漢430070；3.武漢工程大學郵電與信息工程學院，湖北 武漢430074

張量作為向量和矩陣的高階擴展，同時能夠保留數(shù)據(jù)的高維結構，適合用來表示自然中具有多維特征的數(shù)據(jù)。張量已經在許多領域得到了廣泛的應用，包括信號處理［1-2］、計算機視覺［3-4］、神經科學［5］和機器學習［6］。然而實際采集到的高維數(shù)據(jù)通常是遭到破壞或有部分缺失的，對于這種情況，可以根據(jù)已觀測到的部分數(shù)據(jù)來恢復其缺失部分，這就是張量補全研究。本文研究的低秩張量補全問題是通過張量分解獲得的潛在低秩表達與數(shù)據(jù)低秩的特性，利用數(shù)據(jù)空間中數(shù)據(jù)的低秩關聯(lián)結構更有效地預測缺失部分。

CANDECOMP/PARAFAC分解［7］和Tucker分解［8］是經典的張量分解方法，已經有許多基于它們的張量補全算法，例如CP分解加權法（CP-weighted optimization，CP-WOPT）［9］，完全貝葉斯處理（fully Bayesian CP factorization，F(xiàn)BCP）［10］以及張量同時分解和補全方法（simultaneous tensor decomposition and completion，STDC）［11］。但是，由于經典張量分解模型的局限性，僅在低維張量補全時才能達到較高的精度，并且容易因為維度太大參數(shù)過多而遭受“維度詛咒”。近來，已經提出了一種基于矩陣乘積狀態(tài)（matrix product state，MPS）模型的張量鏈分解［12］，張量鏈分解能夠將高階張量分解成一組三階張量，具有很高的數(shù)據(jù)壓縮能力和計算效率，本文將基于張量鏈分解研究低秩張量補全問題。

目前廣泛應用的低秩張量框架是將張量每個模展開矩陣的秩作為優(yōu)化目標，通過求解秩加權和最小化問題來低秩近似原始張量。由于張量低n-秩最小化模型是一個多項式的非確定性問題（non-deterministic polynomial，NP），需要對秩 函數(shù)進行凸松弛，通常的做法是轉換成獨立的模展開矩陣的核范數(shù)求解，這樣每次迭代都需要進行大量的奇異值分解（singular value decomposition，SVD）計算。盡管最近已經提出了許多基于張量鏈分解的張量補全方法，但是與它們對原始數(shù)據(jù)施加低秩約束不同，受Tucker分解核心張量核范數(shù)［13］的啟發(fā)，本文在張量鏈核心張量上引入最小化約束，這可以將大規(guī)模張量核范數(shù)問題轉換為小型核心張量核范數(shù)問題來解決，基于張量鏈分解的核心張量來解決低秩張量補全問題，并且給出了具體算法流程，最后運用交替方向乘子法（alternating direction of method of multipliers，ADMM）［14］求解，使其在迭代過程中具有穩(wěn)定性能并且計算高效。

1 張量鏈分解

采用通用的張量表示方法［15］，標量用大小寫字母表示，例如x，X，矢量和向量用加粗的小寫字母表示，例如x，矩陣由加粗的大寫字母表示，例如X，張量用手寫體表示，例如X。設I1,I2,...,IN表示各維度大小，張量X∈ ?I1×I2×…×IN表示一個大小為I1×I2×…×IN的N階張量。X(1),X(2),…,X(N)表示張量序列，其中X(n)表示序列中的第n個張量。張量個元 素 可 以 表 示 為xi1i2…iN或 者 X(i1,i2,…,iN)。表示張量X的模式-n矩陣展開，其反向操作是fold(n)(X)，表示將[X](n)恢復成張量X。

另外給出張量內積和Frobenius范數(shù)定義，兩個相同大小張量X，Y的內積定義如下：

張量X的Frobenius范數(shù)定義如下：

張量鏈分解［12］將高階張量分解為一組三階張量，這有助于從原始的高階張量獲得低階核心張量。張量X∈?I1×I2×…×IN的張量鏈分解形式可以表示為：

核心張量G(n)是大小為Rn?1×In×Rn的三階張量，中間階大小In為原始張量對應階的維數(shù)，剩余兩階的維數(shù)稱為張量鏈分解秩。序列(R0,R1,…,RN)定義為張量鏈分解表達的秩，為了最終乘積是一個標量，還需要秩約束為R0=RN=1的邊界條件。此外對張量中每個元素還有如下分解表達式：

其中G(n)(in)∈?Rn?1×Rn是核心張量的模-2切片矩陣，也可以定義為G(n)(:,in,:)。本文中用運算符Ψ表示核心張量生成近似張量的的過程，即X=Ψ[G(n)]。

2 張量鏈核心張量核范數(shù)最小化方法

根據(jù)核心張量與原始張量之間的維度大小對應關系，可以得出張量的秩受到其核心張量的秩的約束，意味著如果對核心張量施加低秩約束的同時也對張量自身進行了低秩約束，考慮到核心張量較之原始張量有更低的維度，本算法選擇直接把核心張量的秩函數(shù)作為優(yōu)化目標，因此提出基于張量鏈核心張量的低秩張量補全問題，表達式為：

其中X表示經過補全算法得到低秩張量，Ω表示所有已知元素的集合，T表示張量中可以觀測到的部分，Ψ[G(n)]表示核心張量生成近似張量的運算。

然而上述秩函數(shù)問題是一個NP難問題，需要用核心張量的核范數(shù)代替秩正則化進行凸松弛。根據(jù)張量核范數(shù)的定義，又考慮到每個三階的核心張量分別有3種模展開方式，結合這3種模展開矩陣，可以得到核心張量的核范數(shù)定義如下：

其中||·||?表示核范數(shù)計算，即矩陣所有奇異值 的 和并且αn＞0表示各模式矩陣核范數(shù)的加權。結合核心張量核范數(shù)的定義以及式（5）的補全模型，將條件中的等式約束轉換為用來約束恢復的張量X與核心張量生成的張量Ψ[G(n)]的近似性，λ是一個用來平衡低秩約束項與近似約束項的參數(shù)，由此得到式（5）的松弛模型，如式（7）所示：

式（7）稱為基于張量鏈分解的核心張量核范數(shù)的低秩張量補全模型（low-rank tensor-train core tensor nuclear norm minimization，LTTCTNNm），接下來展示算法的具體求解方法。

由于優(yōu)化問題中的變量是相互依賴的，引入輔助張量Mn,i,n=1,…,N,i=1,2,3來使變量分離，從而轉化為如式（8）的問題：

通過將等式約束合并到拉格朗日函數(shù)中，得到式（8）的增廣拉格朗日函數(shù)為：

其中Yn是拉格朗日乘子張量，運用交替方向乘子法［14］，按以下方法迭代更新G(n)，Mn,i，X，Yn：

對于每個G(n),k+1,n=1,…,N，只保留有關的項之后，有如下優(yōu)化子問題，如式（10）所示：

對式（10）求導，取倒數(shù)為零的極值點可得式（11）：

上述形式是一個經典矩陣核范數(shù)最小化問題，可以直接通過奇異值閾值（singular value thresholding，SVT）得到閉式解［16］，如式（13）所示：

更新恢復的張量X：

得到如下解：

張量X包括已經觀測到的部分以及由迭代更新的核心張量生成的缺失部分張量表示。

同時隨著迭代過程自動更新ρ，設置步長t，ρ=max{tρ,ρmax}。

3 實驗部分

通過進行仿真實驗來驗證提出算法的性能與并于另外3種算法進行對比，對比算法包括高精度低秩張量補全算法（high accuracy low rank tensor completion，HaLRTC）［17］，以及另外兩種同樣基于張量鏈分解進行的張量補全算法：張量鏈分解加權 優(yōu) 化 法（tensor train weighted optimization，TTWOPT）［18］，張 量 鏈 分 解 隨 機 梯 度 下 降 法（tensor train stochastic gradientdescent，TTSGD）［19］。本文算法以及對比算法的參數(shù)設置如下：權重參數(shù)αn均 為10?1，ρ=max{tρ,ρmax}，ρmax=100，t∈[1.1,1.2]尋最優(yōu)，對比算法的參數(shù)設置為程序默認值。另外設置了兩個終止條件，停止誤差設置為||Xk+1?Xk||/||Xk+1||＜10?6，最大迭代次數(shù)maxiter=500。但是根據(jù)TTSGD算法的特點以及其算法默認參數(shù)設置，可以了解到TTSGD至少迭代105次才能達到與其他算法相近的精確度，為了使實驗看上去具有可對比性，所以將TTSGD迭代次數(shù)設置為105。實驗主要分為兩個部分：實際圖像恢復效果和合成數(shù)據(jù)仿真實驗。

3.1 實際圖像數(shù)據(jù)

主要進行自然彩色圖像的丟失數(shù)據(jù)估計的應用，并將實際圖像用于提出算法與對比算法進行收斂性與運行時間的對比。對圖像估計恢復效果的評估主要依據(jù)兩個評估標準：相對平方誤差（relative squared error，RSE）和峰值信噪比（peak signal to noise ratio，PSNR），分別用E和P表示。E=||T?X||F/||T||，X是恢復后的張量，T是原始張量，RSE越小證明恢復效果越好。P=10log10(2552/S)，其 中S=||Treal?X||2F/u(Treal)，u(Treal)表示張量中所有元素的數(shù)量，PSNR越大證明實驗恢復效果越好。圖1為實驗測試的RGB圖像，均為三階張量數(shù)據(jù)。第1個實驗在這4個圖像數(shù)據(jù)上進行，設定缺失率為80%，比較4個算法的實際圖像恢復效果，圖2每行是不同的圖像，由左到右每列分別是圖像80%缺失效果和本文算法、HaLRTC、TTSGD、TTWOPT算法補全結果，可以直觀的看到各個算法在實際圖像中補全效果上的差異，可以看出在缺失率較高的時候，肉眼已經很難看出原圖的樣子，幾種算法基本都能恢復出大致的輪廓，但是本文算法與TTWOPT算法明顯視覺效果強于另外兩種算法。從Lena圖中臉部細節(jié)和House圖中煙囪細節(jié)來看，本文算法比TTWOPT局部更加清晰。

圖1 實驗RGB圖像Fig.1 Experimental RGB images

圖2 每行的不同圖像在80%缺失率時各算法的補全結果Fig.2 Completion results of each algorithm in case of 80%missing rate of different images

第二個實驗選取實驗大小為256×256×3圖像Lena作為對象，進行了多個對比實驗，包括不同算法的相對平方誤差以及峰值信噪比隨采樣率從低到高變化的情況（圖3），不同算法達到相同誤差精度10?6需要的迭代次數(shù)以及整個算法運行需要的時間隨采樣率變化的情況［圖4（a，b）］。

圖3 算法的RSE和PSNR隨采樣率變化的對比：（a）RSE，（b）PSNRFig.3 Comparison of RSE and PSNR of algorithms with different sampling rates：（a）RSE，（b）PSNR

由圖3可以看出，提出的算法除了在采樣率極低（低于20%）的情況下評估標準RSE和PSNR結果都是優(yōu)于其余3種算法。接下來為了保證迭代次數(shù)實驗和運行時間實驗的準確性，根據(jù)TTSGD算法的已知參數(shù)設置，可以明顯確認該算法的在相同的誤差停止條件下，在運行時間和迭代次數(shù)兩方面都是遠遠超過其他3種算法的，無需再進行這兩方面的對比，因此排除對比算法TTSGD，僅對比本文算法與HaLRTC和TTWOPT3種算法。

圖4（a）顯示了本文算法與對比算法在收斂性方面的性能對比，在實驗結果中，橫坐標為各種算法的迭代次數(shù)，縱坐標顯示每步迭代結果的相對變化值。由此可以看出本文算法迭代速度很快，一般在50次以內就收斂了，但是相同條件下也是基于張量鏈分解的TTWOPT算法收斂迭代次數(shù)將近300次。圖4（b）對比了3種算法在不同采樣率下的運行時間，從運行效率的角度看，整體上是采樣率越高耗時越短，計算相對簡單的HaLRTC需要的時間并不長，采樣率較高時本文算法略快于HaLRTC，整體說來差距并不明顯。但是對比運算同樣較復雜的TTWOPT算法，本文算法在運行時間實驗上表現(xiàn)的性能明顯優(yōu)于TTWOPT算法。

圖4 （a）圖像缺失率50%時各算法收斂性分析對比，（b）算法運行時間隨采樣率變化的對比Fig.4（a）Convergence analysiscomparison of algorithms at 50%missing rate，（b）comparison of algorithms running time with different sampling rates

3.2 合成數(shù)據(jù)

考慮用人工合成數(shù)據(jù)驗證該算法的有效性，首先通過張量鏈分解的方式分別生成四階和三階的2個實驗張量 X∈?50×50×50×50和 Y∈?80×80×80，其中核心張量都獨立服從標準正態(tài)高斯分布，通過對核心張量的運算Ψ[G(n)]得到實驗張量，對合成數(shù)據(jù)采用RSE作為性能評估標準?？紤]到實驗的隨機性，每個實驗數(shù)據(jù)的結果都是取10次實驗的平均結果。由圖5（a）和（b）分別給出了算法在四階和三階張量情況下的對比實驗結果，結果表明，本文算法除了在采樣率極低的情況（20%以下）性能一般，除此以外表現(xiàn)穩(wěn)定，恢復精度明顯高于其他3種算法。而較其他3種算法需要千倍以上迭代次數(shù)的TTSGD，由于在本次對比實驗中需要的迭代次數(shù)太多而被提前終止，表現(xiàn)得極其不穩(wěn)定并且精度較差。

圖5 合成張量數(shù)據(jù)上各算法的RSE隨采樣率變化的對比：（a）四階張量，（b）三階張量Fig.5 Comparison of RSE of each algorithm on synthetic tensors with different sampling rates：（a）fourth-order tensor，（b）third-order tensor

4 結 論

以上對基于張量鏈分解對缺失張量進行了低秩張量補全的研究，該算法在張量鏈分解的核心張量上采用了低秩約束方法，并通過凸松弛轉換為核心張量核范數(shù)最小化求解，這樣能夠有效降低高階張量的計算規(guī)模。實驗表明，本文方法運行時間更短，迭代收斂更快，補全結果也比較好，綜合各方面性能均優(yōu)于對比算法。