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

陳熙 馮月華

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

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

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

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

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

1 隨機算法

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

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

2 張量近似問題

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

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

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

3 新算法STHOSVD-SPRSVD

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

4 數值實驗

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

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

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

5 結論

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

參考文獻：

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

[2] 楊立東，王晶，謝湘，匡鏡明.基于張量分解模型的語音信號特征提取方法[J].北京理工大學學報，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] 周志華.機器學習[M].北京：清華大學出版社，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.