隨機(jī)低秩逼近算法在張量近似中的應(yīng)用

陳 熙 馮月華

（1.上海工程技術(shù)大學(xué) 機(jī)械與汽車工程學(xué)院，上海 201620；2.上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計(jì)學(xué)院，上海 201620）

張量是一個(gè)多維數(shù)組。一階張量是向量，二階張量是矩陣，三階或更高階的張量稱為高階張量。高階張量的分解在信號(hào)處理、數(shù)值線性代數(shù)、計(jì)算機(jī)視覺等領(lǐng)域都有大量的應(yīng)用[1-3]。張量分解可以被認(rèn)為是矩陣奇異值分解的高階擴(kuò)展。常用的兩類分解分別是CANDECOMP/PARAFAC（CP）分 解[4]和Tucker 分解[5]，前者將張量分解為一階張量的總和，而后者是矩陣奇異值分解（SVD）的高階形式，本文主要研究的是Tucker 分解。

在計(jì)算 Tucker 分解的各種算法中，一個(gè)關(guān)鍵步驟是計(jì)算張量的每種可能模式展開的精確或近似的奇異值分解，這將在后面定義。為了有效地計(jì)算給定張量的可靠Tucker分解，本文基于隨機(jī)算法策略以及高效數(shù)據(jù)訪問的要求，提出一種新的高效算法求解Tucker 分解，并用Matlab 軟件實(shí)現(xiàn)該算法。

1 隨機(jī)算法

任意給定一個(gè)向量x∈Rn，Diag(x)表示對(duì)角元為向量x的對(duì)角矩陣。對(duì)于任意的矩陣A∈Rm×n(m≥n)，其SVD為：

其中U=(u1,u2,…um)∈Rm×m和V=(v1,v2,…vn)∈Rn×n是正交矩陣，∑=Diag(…)且1≥≥…m≥0。對(duì)于1≤k≤n，令A(yù)的秩k 截?cái)郤 VD為：

在大數(shù)據(jù)分析和機(jī)器學(xué)習(xí)中，SVD 已成為一種關(guān)鍵的分 析工具[6]。但是這些經(jīng)典算法需要高內(nèi)存消耗且計(jì)算復(fù)雜度高，已經(jīng)無法滿足時(shí)代發(fā)展的需求。近年來隨機(jī)算法的出現(xiàn)為構(gòu)造近似SVD 算法提供了強(qiáng)有力的支撐。與古典數(shù)值算法比較，隨機(jī)算法具有簡單易實(shí)現(xiàn)，更高運(yùn)行效率，更具魯棒性，更少內(nèi)存空間等優(yōu)點(diǎn)。Tro pp 等人[7]基于隨機(jī)投影策略提出了單步隨機(jī)奇異值分解（SPRSVD）得到給定矩陣的近似SVD，具體內(nèi)容見算法1。由于原始數(shù)據(jù)集只在算法最開始的時(shí)候用到，因此算法具有高效率。

2 張量近似問題

在這里回顧一些張量的基本符號(hào)和概念，這些符號(hào)將應(yīng)用于后面的數(shù)值實(shí)驗(yàn)。關(guān)于張量性質(zhì)和應(yīng)用的更詳細(xì)討論見文獻(xiàn)[8]。張量是一個(gè)d 維數(shù)組，通常用符號(hào)X∈RI1×…×Id來表示，其元素為xj1,…,jd,1≤j1≤I1,…,1≤j d≤Id。

張量X 按第n 維展開用矩陣X∈RIn×(∏j≠nIj)表示。由于這個(gè)張量有d 維，所以一共有d 種(n展)開的可能性。張量X∈RI1×…×Id的第n 維展示與矩陣U∈Rk×In的乘積得到一個(gè)張量Y∈RI1×…×In-1×k×In+1×…×Id，即：

通過張量乘法和張量展開的定義，基于Tucker 分解的高階SVD（HOSVD）。算法[9]生成一個(gè)秩為（k1,...,kd）的近似張量。HOSVD算法得到核心張量G∈Rk1×…×kd和一組酉矩陣Uj∈RIj×kj(j=1,...,d)，即：

方程（1）稱為Tucker 分解。HOSVD 的計(jì)算成本和內(nèi)存消耗對(duì)于大規(guī)模問題令人望而卻步，因此順序截?cái)嗟腍OSVD（ST-HOSVD）算法被用來提高HOSVD 的 效率[10]，該算法保留了截?cái)郒OSVD 算法的幾個(gè)有利特性，同時(shí)降低了計(jì)算分解的計(jì)算成本。STHOSVD 算法的偽代碼包含在算法2 中。

3 新算法STHOSVD-SPRSVD

隨著實(shí)際問題中張量問題的越來越大，對(duì)分解算法的效率要求也越來越高。算法2 中計(jì)算代價(jià)最大的是每個(gè)張量展開需要計(jì)算SVD，因此算法2 中的SVD 分解將采用單步隨機(jī)奇異值分解實(shí)現(xiàn)，進(jìn)而得到更高效的Tucker 分解，并將此算法命名為STHOSVD-SPRSVD，具體細(xì)節(jié)見算法3。

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

本節(jié)通過幾個(gè)數(shù)值實(shí)驗(yàn)驗(yàn)證新算法STHOSVD-SPRSVD，并與propack 包中LANSVD 方法以及Matlab 自帶的svds 命令進(jìn)行比較。對(duì)應(yīng)的算法分別命名為STHOSVD-LANSVD、STHOSVD-SVDS 和STHOSVD-SPRSVD。本實(shí)驗(yàn)通過下列方式構(gòu)造一個(gè)稀疏的張量 X ∈Rn×n×n：

其中：x j,y j,zj∈Rn是具有非負(fù)元素的稀疏向量，符號(hào)“?”表示向量外積。并通過使用STHOSVD-LANSVD、STHOSVD-SVDS 和STHOSVD-SPRSVD 這三種算法分別得到一個(gè)具有秩（k,k,k）的Tucker 分解[G;U1,U2,U3]。相對(duì)近似誤差使用，其中,│││.│F表示矩陣的Frobenius 范數(shù)。

實(shí)驗(yàn)結(jié)果顯示了STHOSVD-LANSVD、STHOSVD-SVDS和STHOSVD-SPRSVD 算法運(yùn)行在$300 imes 300 imes 300$稀疏張量上的相對(duì)近似誤差和運(yùn)行時(shí)間，從結(jié)果中觀察到，這三種算法的誤差是可比的，但是在時(shí)間效率上STHOSVD-SPRSVD 算法比另外兩種算法具有明顯的優(yōu)勢(shì)。

5 結(jié)論

本文基于隨機(jī)算法提出了STHOSVD-SPRSVD 算法得到Tucker 分解，數(shù)值實(shí)驗(yàn)表明STHOSVD-SPRSVD 算法在達(dá)到所要求的精度上具有更少的計(jì)算代價(jià)。由于單步的近似SVD 存在效率與精度的權(quán)衡，本文將基于現(xiàn)有的基礎(chǔ)，在接下來的工作中研究具有更高精度和更高效率的算法。