ICCV 2021 | UCLA提出：基于張量CUR的快速魯棒張量主成分分析算法

作者 | HanQin Cai, Zehan Chao, Longxiu Huang 

編輯 | 王曄

本文是對發表于國際計算機視覺大會ICCV的Workshop論文“Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition” [1] 的介紹。

該論文由UCLA大學數學系 HanQin Cai, Zehan Chao, Longxiu Huang, and Deanna Needell 共同完成。

論文arXiv鏈接：https://arxiv.org/abs/2108.10448

1

研究簡介

我們的研究主要是關于魯棒張量主成分分析的算法，也可以稱做魯棒張量分解算法。與傳統的高維奇異值分解算法(HOSVD)不同，我們的算法是基于【張量CUR分解】和【交替映射法】衍生出的關于張量分解的一套算法。解決同樣的張量問題有非常大的時間復雜度優勢，同時也不會受限于被稀疏離群值 (sparse outlier)破壞的數據。我們通過大量的模擬數據實驗與真實數據實驗來驗證了算法的可行性與魯棒性。

2

研究背景

主成分分析（PCA）是一種基礎的數學分析方法，為對多變量數據進行降維以便更好的分析及可視化。矩陣數據的PCA通常與矩陣分解密切相關，例如一種常見的PCA問題定義為獲得矩陣的低秩趨近：

這個問題可以通過矩陣的截斷奇異值分解（truncated SVD）來完成。

傳統的PCA存在一些公認的缺點，例如對于離群值非常敏感，少數幾個離群值會完全擾亂算法的輸出。因此在這之上一些研究轉向了魯棒主成分分析 (Robust PCA、RPCA)。RPCA在PCA的基礎上增加了對于稀疏離群值的容忍度：

此處，額外的稀疏矩陣S吸收原數據D的離群值，從而使得輸出結果L更加魯棒。

張量（Tensor）是比矩陣更廣義的結構，可以看作多維度版本的矩陣；同樣，矩陣可以定義為二維的張量。在各種關于數據科學的研究中，張量被認為可以比矩陣更好地保存原數據的結構，從而產生了各類對張量的研究。其中，張量的魯棒主成分分析，即魯棒分解問題，就是我們算法處理的主要問題。即：

注意，張量的秩存在多種不同的定義。在此文中，我們著重研究張量的多線性秩(multilinear rank)，也稱為塔克秩 (Tucker rank)。

3

方法介紹

最初的CUR分解屬于矩陣分解的一種，與LU分解，SVD分解類似：

其中，C指的是原矩陣提取的列，R指的是原矩陣提取的行，U 是 C和R的交叉部分。CUR分解總是成立的當U的秩等于A的秩（詳細內容可參考論文[2]）。

將這個概念拓展到高維張量里，我們就有了張量版本的CUR分解（張量CUR有Chidori CUR和 Fiber CUR兩個版本，本文使用Fiber CUR。詳細內容可參考論文[3]）

在此之上，結合交替映射算法的概念，我們開發了稱之為魯棒張量CUR (Robust Tensor CUR、RTCUR)的算法：

其中，第5行的resample是可以在每個迭代中進行也可以始終統一，進而演化成了兩種算法，RTCUR-R與RTCUR-F。這兩種算法的區別在于，Resample的算法(RTCUR-R)在處理更密的離群值數據時比Fixed index算法(RTCUR-F)要穩定一些，但RTCUR-F算法因為每次迭代中不用重新選擇張量中的數據，在運行時間上稍有優勢，以及RTCUR-F只需要取原張量中非常小的一部分數據，從而對數據缺失有更高的容忍度。

4

實驗結果

首先，我們研究RTCUR算法的采樣系數（Sampling Constant）與離群值密度的相變圖。我們生成固定秩的三維張量，然后加入不同密度的離群值，運行不同采樣系數RTCUR算法進行檢測。從而根據RTCUR算法是否可以準確恢復原低秩張量L來畫出如下相變圖：

從相變圖中可以看到，在采樣系數取在3~5之間時，我們可以獲得較高的離群值容忍度同時保持算法的較快運行。

接著，我們生成了不同尺寸的低秩三維張量和隨機稀疏離群值來測試各種算法的運行時間與結果準確性。實驗結果發現，基本所有的算法對于 20%的離群值都可以準確地分離出低秩部分與稀疏離群值部分。從時間對比圖上也可以看到處理張量魯棒分解問題時，RTCUR擁有巨大的時間優勢：

     

我們又測試了不同的真實數據集，其中一項任務是彩色視頻的背景分離。比如在一段行人走在街上的視頻，彩色的低秩背景街道可以視為張量， 而移動中的行人則可視為離群值。通過幾段不同的視頻測試，我們的RTCUR算法都可以獲得很好的分離效果：

當然，不同算法的效果略有差異，但總體都成功的分離了背景與前景。在這之上，RTCUR算法對于真實數據同樣有明顯的時間優勢（見Table 1）。

5

總結

本文針對張量魯棒主成分分析問題提出了一個基于張量CUR的快速算法。從模擬數據和真實數據來看，我們的算法在準確有效的同時極大地提升了速度。我們未來會在算法的理論方面探討一些思路和可能性。

期刊擴展版會很快推出，歡迎大家關注我們后續的工作。      

參考文獻

[1] H.Q. Cai, Z. Chao, L. Huang, and D. Needell. Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition. International Conference on Computer Vision (ICCV) Workshop on Robust Subspace Learning and Applications in Computer Vision, 2021.

[2] K. Hamm and L. Huang. Perspectives on CUR decompositions. Applied and Computational Harmonic Analysis (ACHA), 48(3): 1088-1099, 2020.

[3] H.Q. Cai, K. Hamm, L. Huang, and D. Needell. Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions. Journal of Machine Learning Research (JMLR), 22(185):1-36, 2021.

[4] C. Lu, J. Feng, Y. Chen, W. Liu, Z. Lin, and S. Yan, Tensor robust principal component analysis with a new tensor nuclear norm, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 42(4): 925–938, 2019.

[5] H.Q. Cai, J. Cai, and K. Wei. Accelerated Alternating Projections for Robust Principal Component Analysis. Journal of Machine Learning Research (JMLR), 20(20): 1-33, 2019.

[6] H.Q. Cai, K. Hamm, L. Huang, J. Li and T. Wang. Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation. IEEE Signal Processing Letters (IEEE SPL), 28: 116-120, 2020.

掃碼添加小助手微信（AIyanxishe3），備注ICCV2021拉你進群。

雷鋒網雷鋒網雷鋒網

雷峰網版權文章，未經授權禁止轉載。詳情見轉載須知。