陳熙 馮月華

摘 要 隨著大數(shù)據(jù)時代的到來，實際應(yīng)用中出現(xiàn)的張量規(guī)模也越來越大，因此求解張量的Tucker分解的算法效率有待提升。本研究基于隨機投影算法的技術(shù)以及高效的數(shù)據(jù)訪問要求，改進Tucker分解中最重要的矩陣奇異值分解，進而得到一種新的高效求解Tucker分解的算法。借助Matlab軟件實現(xiàn)新算法，數(shù)值實驗結(jié)果表明新算法在效率上具有顯著的提升優(yōu)勢。

關(guān)鍵詞 奇異值分解 隨機算法 張量近似 Tucker分解 低秩逼近

中圖分類號：TP311 文獻標識碼：A 文章編號：1007-0745（2021）09-0058-03

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

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

1 隨機算法

任意給定一個向量，Diag（x）表示對角元為向量x的對角矩陣。對于任意的矩陣，其SVD為：

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

2 張量近似問題

在這里回顧一些張量的基本符號和概念，這些符號將應(yīng)用于后面的數(shù)值實驗。關(guān)于張量性質(zhì)和應(yīng)用的更詳細討論見文獻[8]。張量是一個d維數(shù)組，通常用符號來表示，其元素為。

張量X按第n維展開用矩陣表示。由于這個張量有d維，所以一共有d種展開的可能性。張量的第n維展示與矩陣的乘積得到一個張量，即：

方程（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命令進行比較。對應(yīng)的算法分別命名為STHOSVD-LANSVD、STHOSVD-SVDS和STHOSVD-SPRSVD。本實驗通過下列方式構(gòu)造一個稀疏的張量：

其中：是具有非負元素的稀疏向量，符號“”表示向量外積。并通過使用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 ＼times 300 ＼times 300$稀疏張量上的相對近似誤差和運行時間，從結(jié)果中觀察到，這三種算法的誤差是可比的，但是在時間效率上STHOSVD-SPRSVD算法比另外兩種算法具有明顯的優(yōu)勢。

5 結(jié)論

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

參考文獻：

[1] 張曉飛.解張量分解問題的信賴域交替最小二乘法[D].南京：南京師范大學(xué)，2014.

[2] 楊立東，王晶，謝湘，匡鏡明.基于張量分解模型的語音信號特征提取方法[J].北京理工大學(xué)學(xué)報，2013（33）：1171–1175.

[3] Feng Y，Xiao J，Gu M.Flip-Flop Spectrum-Revealing QR Factorization and Its Applications on Singular Value Decomposition[J].Elec.Trans.Numer. Anal.， 2018（51）：469-494.

[4] Carroll J D， Chang J J.Analysis of individual differences in multidimensional scaling via an N-way generalization of “Eckart-Young” decomposition[J].Psychometrika， 1970（35）：283–319.

[5] Tucker L R. Some mathematical notes on three-mode factor analysis[J]. Psychometrika， 1966（31）：279–311.

[6] 周志華.機器學(xué)習(xí)[M].北京：清華大學(xué)出版社，2016.

[7] Halko N， Martinsson P G， Tropp J A.Finding structure with randomness： Probabilistic algorithms for constructing approximate matrix decompositions[J].SIAM Rev.，2011（53）：217–288.

[8] Kolda TG，Bader B W. Tensor decompositions and applications[J].SIAM Rev.，2009（51）：455–500.

[9] De Lathauwer L，De Moor B， Vandewalle J.A multilinear singular value decomposition[J].SIAM J.Matrix Anal. Appl.， 2000（21）：1253–1278.

[10] Andersson C A， Bro. R. Improving the speed of multi-way algorithms： Part I.Tucker3[J].Chemom. Intell.Lab.Syst.， 1998（42）：93–103.