隨機低秩逼近算法在張量近似中的應用

陳 熙 馮月華

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

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

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

1 隨機算法

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

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

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

2 張量近似問題

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

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

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

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

3 新算法STHOSVD-SPRSVD

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

4 數(shù)值實驗

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

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

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

5 結(jié)論

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