作者 | HanQin Cai, Zehan Chao, Longxiu Huang 

編輯 | 王曄

本文是對(duì)發(fā)表于國(guó)際計(jì)算機(jī)視覺大會(huì)ICCV的Workshop論文“Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition” [1] 的介紹。

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

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

1

研究簡(jiǎn)介

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

2

研究背景

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

這個(gè)問題可以通過矩陣的截?cái)嗥娈愔捣纸猓╰runcated SVD）來完成。

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

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

張量（Tensor）是比矩陣更廣義的結(jié)構(gòu)，可以看作多維度版本的矩陣；同樣，矩陣可以定義為二維的張量。在各種關(guān)于數(shù)據(jù)科學(xué)的研究中，張量被認(rèn)為可以比矩陣更好地保存原數(shù)據(jù)的結(jié)構(gòu)，從而產(chǎn)生了各類對(duì)張量的研究。其中，張量的魯棒主成分分析，即魯棒分解問題，就是我們算法處理的主要問題。即：

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

3

方法介紹

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

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

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

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

其中，第5行的resample是可以在每個(gè)迭代中進(jìn)行也可以始終統(tǒng)一，進(jìn)而演化成了兩種算法，RTCUR-R與RTCUR-F。這兩種算法的區(qū)別在于，Resample的算法(RTCUR-R)在處理更密的離群值數(shù)據(jù)時(shí)比Fixed index算法(RTCUR-F)要穩(wěn)定一些，但RTCUR-F算法因?yàn)槊看蔚胁挥弥匦逻x擇張量中的數(shù)據(jù)，在運(yùn)行時(shí)間上稍有優(yōu)勢(shì)，以及RTCUR-F只需要取原張量中非常小的一部分?jǐn)?shù)據(jù)，從而對(duì)數(shù)據(jù)缺失有更高的容忍度。

4

實(shí)驗(yàn)結(jié)果

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

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

接著，我們生成了不同尺寸的低秩三維張量和隨機(jī)稀疏離群值來測(cè)試各種算法的運(yùn)行時(shí)間與結(jié)果準(zhǔn)確性。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，基本所有的算法對(duì)于 20%的離群值都可以準(zhǔn)確地分離出低秩部分與稀疏離群值部分。從時(shí)間對(duì)比圖上也可以看到處理張量魯棒分解問題時(shí)，RTCUR擁有巨大的時(shí)間優(yōu)勢(shì)：

     

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

當(dāng)然，不同算法的效果略有差異，但總體都成功的分離了背景與前景。在這之上，RTCUR算法對(duì)于真實(shí)數(shù)據(jù)同樣有明顯的時(shí)間優(yōu)勢(shì)（見Table 1）。

5

總結(jié)

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

期刊擴(kuò)展版會(huì)很快推出，歡迎大家關(guān)注我們后續(xù)的工作。      

參考文獻(xiàn)

[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拉你進(jìn)群。

雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。