關(guān)于高階張量的秩-(Lr,1,1)分解方法

尹 鳳, 雷曉軍, 黃光鑫

(1.四川輕化工大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，四川 自貢643000；2.成都理工大學(xué) 信息與計(jì)算科學(xué)系，成都610059)

近年來，張量分解得到了越來越多的關(guān)注，取得了大量研究成果。在矩陣的奇異值分解(SVD)向張量分解的擴(kuò)展過程中，Trucker分解或高階奇異值分解(HOSVD)[1]和CANDECOMP/PARAFAC分解(簡稱為CP分解)[2-3]是2種主要的張量分解方法。這2種張量分解方法對(duì)應(yīng)于2種不同的矩陣的秩。Trucker分解/HOSVD對(duì)應(yīng)于矩陣的模-n秩，而CP分解與矩陣或張量的擴(kuò)展所需的秩-1組件的最小數(shù)量對(duì)應(yīng)。Trucker分解是一種高階的主成分分析，其基本思想是：將一個(gè)張量分解為一個(gè)核心張量沿每一個(gè)模乘上一個(gè)矩陣；Trucker分解的優(yōu)點(diǎn)是：可以用一個(gè)張量的大部分有用信息來表示原張量；不足之處是：Trucker分解的唯一性不能保證。CP分解的基本思想是：將一個(gè)張量表示成有限個(gè)秩-1張量之和。其優(yōu)點(diǎn)是：能將張量進(jìn)行降維處理；不足之處是：求CP分解的秩是一個(gè)NP問題，實(shí)際中只能通過低秩逼近等近似方法確定。

本文研究的高階張量的秩-(Lr,1,1)分解方法受到了塊組件分解[4]方法的啟發(fā)，將高階張量進(jìn)行降維，即分解成一個(gè)矩陣與2個(gè)向量的組合，不同于其他張量分解方法。秩-(Lr,Lr,1)分解方法將張量分解成2個(gè)矩陣和一個(gè)向量的組合，秩-(L,M,N)分解方法將張量分解成3個(gè)矩陣的組合，秩-(L,M,·)分解方法則是將張量分解成2個(gè)矩陣的組合。本文在Trucker分解[1]和CP分解[2-3]的基礎(chǔ)上，提出了一種高階張量的秩-(Lr,1,1)分解，得到了一種交替最小二乘求解方法。

1 預(yù)備知識(shí)

本節(jié)是全文的基礎(chǔ)。我們首先引入幾個(gè)基本概念和符號(hào)，然后簡要地介紹3種近年來發(fā)展的塊分解方法，即秩-(Lr,Lr,1)分解、秩-(L,M,N)和秩-(L,M,·)分解。

1.1 基本概念和記號(hào)

R和C分別表示實(shí)數(shù)和復(fù)數(shù)域，有時(shí)我們也統(tǒng)一用K代替R或C。標(biāo)量用小寫字母a,b,…表示；向量用粗體小寫字母a,b,…表示；矩陣用粗體大寫字母A,B,…表示；張量用花體字母A，B,C,…表示。矩陣A中行標(biāo)為i、列標(biāo)為j的元素表示為aij=(A)ij，相應(yīng)地，aijk=(A)ijk。令A(yù)=[a1a2…]，其中ai是矩陣A的第i列。定義矩陣A與B的克羅內(nèi)克積為

(1)

設(shè)A=[A1A2…AR]，B=[B1B2…BR]是2個(gè)塊矩陣，則矩陣A與B的Khatri-Rao內(nèi)積[5]定義為

A⊙B=(A1?B1…AR?BR)

(2)

特別地，符號(hào)⊙c定義逐列的Khatri-Rao內(nèi)積，即：A⊙cB=(a1?b1…aR?bR)。上標(biāo)T和?分別定義為轉(zhuǎn)置、復(fù)共軛轉(zhuǎn)置、Moore-Penrose廣義逆。一個(gè)矩陣A的向量化定義為vec(A)=[a1Ta2T…]T。符號(hào)δij代表克羅內(nèi)克積函數(shù)，即當(dāng)i=j時(shí)，δij=1；否則δij=0。

定義1令T∈KI1×I2×I3，A∈KJ1×I1，B∈KJ2×I2，C∈KJ3×I3則Trucker模-1乘積T·1A，模-2乘積T·2B，和模-3乘積T·3C分別定義為

(3)

(4)

(5)

定義2一個(gè)張量T∈KI×J×K的F范數(shù)定義為

(6)

定義3[6]給定2個(gè)具有相同維度的張量A和B，定義A與B的內(nèi)積為

(A,B)=∑ijkaijkbijk

(7)

當(dāng)A=B時(shí)，對(duì)應(yīng)的張量范數(shù)是‖A‖=(A,A)1/2。

定義4張量A∈KI1×I2×…×IP和張量B∈KJ1×J2×…×JQ的外積A °B定義為

(A °B)i1i2…iPj1j2…jQ=ai1i2…iPbj1j2…jQ

(8)

定義5[7]一個(gè)張量T∈KI1×I2×I3的模-n向量是一個(gè)In維向量，通過變化指標(biāo)in保持其他指標(biāo)固定。其中In表示n階單位矩陣。

定義6一個(gè)三階張量是秩-(L,M,N)的，如果它的模-1秩、模-2秩和模-3秩分別是L，M和N。

一個(gè)秩-(1,1,1)張量簡稱為1-秩張量。此定義與下述是等價(jià)的。

定義7一個(gè)張量T的模-n秩是由它的模-n向量張成的子空間的維數(shù)。

定義8一個(gè)三階張量T是1-秩的，如果它等于3個(gè)向量的外積。

張量的秩定義如下：

定義9[8]張量T的秩是由1-秩張量的所有線性組合中的1-秩張量的最小個(gè)數(shù)。

由定義9，我們定義一個(gè)三階張量的標(biāo)準(zhǔn)矩陣或向量表示。

定義10[9]標(biāo)準(zhǔn)的JK×I矩陣表示(T )JK×I=(T)JK×I，KI×J表示(T )KI×J=(T)KI×J，IJ×K表示(T )IJ×K=(T)IJ×K，定義為

(TJK×I)(j-1)K+k,i=(T )ijk

(9)

(TKI×J)(k-1)I+i,j=(T )ijk

(10)

(TIJ×K)(i-1)J+j,k=(T )ijk

(11)

對(duì)所有角標(biāo)的所有值。

張量T的標(biāo)準(zhǔn)的IJK×1向量記為TIJK=tIJK,定義為

(tIJK)(i-1)JK+(j-1)K+k=(T )ijk

(12)

對(duì)所有角標(biāo)的所有值。

進(jìn)一步地，張量T∈RI×J×K的第i個(gè)J×K矩陣切片記為TJ×K,i；類似地，第j個(gè)K×I切片和第k個(gè)I×J矩陣切片分別記為TK×I,j和TI×J,k。

1.2 塊分解方法簡介

1.2.1 秩-(Lr,Lr,1)分解

定義11[7]張量T∈RI×J×K分解成秩-(Lr,Lr,1)組件，是一種如下形式的分解

(13)

其中矩陣Ar∈KI×Lr和矩陣Br∈KJ×Lr是秩-Lr，1≤r≤R,cr為矩陣C的第r個(gè)列向量。稱(13)式為張量T∈RI×J×K的秩-(Lr,Lr,1)分解。記A=[A1A2…AR],B=[B1B2…BR],C=[c1c2…cR]，用T的矩陣形式表示，(13)式可以寫成

TIJ×K=[(A1⊙cB1)lL1… (AR⊙cBR)lLR]·CT

(14)

TJK×I=(B⊙C)·AT

(15)

TKI×J=(C⊙A)·BT

(16)

1.2.2 秩-(L,M,N)分解

定義12[7]張量T∈RI×J×K分解成秩-(L,M,N)組件，是一種如下形式的分解

(17)

其中Dr∈KL×M×N是秩-(L,M,N)，Ar∈KI×L(L≤I)，Br∈KJ×M(M≤J)，Cr∈KK×N(N≤K)是列滿秩，1≤r≤R。稱(17)為張量T∈RI×J×K的秩-(L,M,N)分解。記塊矩陣A=[A1A2…AR]，B=[B1B2…BR]，C=[C1C2…CR]，用T的標(biāo)準(zhǔn)矩陣分解表示，(17)式可以寫成

TJK×I=(B⊙C)·bdiag((D1)MN×L,…,(DR)MN×L)·AT

(18)

TKI×J=(C⊙A)·bdiag((D1)NL×M,…,(DR)NL×M)·BT

(19)

TIJ×K=(A⊙B)·bdiag((D1)LM×N,…,(DR)LM×N)·CT

(20)

其中bdiag(A1A2…An)，表示一個(gè)主對(duì)角塊為A1A2…An的塊對(duì)角矩陣。

對(duì)于張量T的IJK×1向量表示，此分解能寫成

(21)

1.2.3 秩-(L,M,·)分解

定義13[7]張量T∈RI×J×K分解成秩-(L,M,·)組件，是一種如下形式的分解

(22)

其中：Cr∈KL×M×K,且Cr的模-1秩等于L，模-2秩等于M；Ar∈KI×L(I≥L)；Br∈KJ×M(J≥M)是列滿秩，1≤r≤R。稱(22)式為張量T∈RI×J×K的秩-(L,M,·)分解。記塊矩陣A=[A1A2…AR]和B=[B1B2…BR]，用張量T的標(biāo)準(zhǔn)矩陣表示，(22)式可以寫成

(23)

TJK×I=[(C1·2B1)JK×L… (CR·2BR)JK×L]AT

(24)

TKI×J=[(C1·1A1)KI×M… (CR·1AR)KI×M]BT

(25)

2 秩-(Lr,1,1)分解及其計(jì)算

2.1 (Lr,1,1) -秩分解及基本唯一性

定義14將張量T∈RI×J×K分解成秩-(Lr,1,1)組件(1≤r≤R)是一種如下形式的分解

(26)

我們稱(26)式為張量T∈RI×J×K的秩-(Lr,1,1)分解。類似地，我們記A=[A1A2…AR]，B=[b1b2…bR]，C=[c1c2…cR]，則(26)式可以寫成

TIJ×K=(A⊙B)·CT

(27)

TJK×I=(B⊙cC)·AT

(28)

TKI×J=(C⊙A)·BT

(29)

利用T的矩陣切片，(26)式能寫成

TJ×K,i=B·bdiag{[(A1)i1… (A1)iL1]T, …,

[(AR)iR… (AR)iLR]T}·CT

(i=1,…,I)

(30)

TK×I,j=C·bdiag(bj1IL1×L1,…,bjRILR×LR)·AT

(j=1,…,J)

(31)

TI×J,k=A·bdiag(ck1IL1×L1,…,bkRILR×LR)·BT

(k=1,…,K)

(32)

注意：(26)式能任意前置不同的秩-(Lr,1,1)塊，而且，只要它們的乘積保持不變，同一個(gè)秩-(Lr,1,1)組件的因子能夠放縮。我們稱這種分解是基本唯一的。圖1給出了一個(gè)張量T∈RI×J×K的秩-(Lr,1,1)分解的示意圖。

以下定理給出了張量T∈RI×J×K的秩-(Lr,1,1)分解的基本唯一性。

圖1 張量的秩-(Lr,1,1)分解示意圖Fig.1 Sketch showing the rank-(Lr,1,1) decomposition of a tensor

定理1令(A,B,C)表示T的秩-(Lr,1,1)分解，1≤r≤R, 假定A是列滿秩，B和C沒有成比例的列，那么(A,B,C)是基本唯一的。

證明假設(shè)c21, …,c2R不為0，并且c11/c21, …,c1R/c2R兩兩不相同，否則，考慮矩陣切片的線性組合。由(32)式，我們有

TI×J,1=A·bdiag(c11IL1×L1,…,c1RILR×LR)·BT

(33)

TI×J,2=A·bdiag(c21IL1×L1,…,c2RILR×LR)·BT

(34)

(A?·TI×J,2)T=B·bdiag(c21IL1×L1,…,c2RILR×LR)

(35)

矩陣C最后由(27)式可得

C=[(A⊙B)?TIJ×K]T

(36)

2.2 交替最小二乘算法

給定B和C，更新A是一個(gè)線性最小二乘問題。同樣，當(dāng)給定A和C時(shí)可以更新B；當(dāng)給定A和B時(shí)可以更新C。詳細(xì)的更新規(guī)則如下： 記A=[A1A2…AR],B=[b1b2…bR],C=[c1c2…cR]，則(26)式可以寫成

TJK×I=(B⊙cC)·AT

(37)

TKI×J=(C⊙A)·BT

(38)

TIJ×K=(A⊙B)·CT

(39)

分別將(37)～(39)式進(jìn)行簡單地變換，我們可以得到算法1。

算法1給出了計(jì)算張量T∈RI×J×K的秩-(Lr,1,1)分解的交替最小二乘算法。注意，在實(shí)際計(jì)算中，矩陣B⊙cC,C⊙A和A⊙B必須具有至少與列一樣多的行，并且必須是列滿秩。如果A是列滿秩，B和C沒有成比例的向量，那么根據(jù)前面的證明過程，這個(gè)算法能通過廣義特征值進(jìn)行初始化，分解具有基本唯一性。

算法1交替最小二乘(ALS)算法計(jì)算秩-(Lr,1,1)分解

(1)初始化B,C,kmax

(2)fork=1,2,…,kmax直至收斂

①更新A:A←[(B⊙cC)?TJK×I]

(3)endfor

(4)輸出A、B和C。

3 數(shù)值實(shí)驗(yàn)

實(shí)例1

我們按照如下形式

(40)

圖2 不同算法的相對(duì)誤差與均方差之間的關(guān)系Fig.2 Relative error vs. negative logarithm of mean square variance of different methods

圖3 不同算法的CPU時(shí)間與均方差之間的關(guān)系Fig.3 CPU time vs. negative logarithm of mean square variance of different methods

從圖2可知，秩-(Lr,1,1)分解對(duì)應(yīng)的算法1產(chǎn)生了最低的相對(duì)誤差，效果最好。從圖3可以看出，秩-(Lr,1,1)分解方法所需CPU時(shí)間最短。

實(shí)例2

圖4 不同算法的相對(duì)誤差與均方差之間的關(guān)系Fig.4 Relative error vs negative logarithm of mean square variance of different methods

圖5 不同算法的CPU時(shí)間與均方差之間的關(guān)系Fig.5 CPU time vs negative logarithm of mean square variance of different methods

4 結(jié) 論

本文提出了一種新的張量塊分解方法，即秩-(Lr,1,1)分解，并提出了求解張量的秩-(Lr,1,1)分解的交替最小二乘法算法。實(shí)驗(yàn)結(jié)果說明了本文所提出的秩-(Lr,1,1)分解方法的有效性。