陳 熙 馮月華

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

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

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

2 張量近似問題

在這里回顧一些張量的基本符號和概念，這些符號將應用于后面的數(shù)值實驗。關于張量性質和應用的更詳細討論見文獻[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。本實驗通過下列方式構造一個稀疏的張量 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ù)。

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

5 結論

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