卷積魯棒主成分分析

王 心，朱浩華，劉光燦

（南京信息工程大學自動化學院，南京 210044）

（*通信作者電子郵箱xinwang@nuist.edu.cn）

0 引言

隨著大數(shù)據(jù)技術的發(fā)展，大量的數(shù)據(jù)資源不斷涌現(xiàn)，但由于目前數(shù)據(jù)的獲取沒有約束，所以獲得的可觀測數(shù)據(jù)帶有大量噪聲，例如數(shù)據(jù)遭到嚴重腐蝕或者數(shù)據(jù)含有離群點。總的來說，這些誤差會顯著降低數(shù)據(jù)樣本的代表性，從而嚴重扭曲數(shù)據(jù)分析，因此如何恢復目標數(shù)據(jù)成為了一個十分重要的問題，也帶來了很大挑戰(zhàn)。Candès 等［1］和Zhang 等［2］提出了魯棒主成分分析（Robust Principal Component Analysis，RPCA）算法，它又稱作主成分追求（Principal Component Pursuit，PCP）。假設通過可觀察的數(shù)據(jù)矩陣M獲得先驗的相關信息，然后根據(jù)先驗信息建立合適的模型，同時設計模型的優(yōu)化算法，最后求解得到恢復的數(shù)據(jù)矩陣。RPCA 采用低秩模型，將數(shù)據(jù)矩陣分解為1 個低秩矩陣和1 個稀疏矩陣，即M=L+E，那么利用RPCA，在滿足一些條件時就可以精確地恢復出L和E。廣義魯棒主成分分析（Generalized Robust Principal Component Analysis，GRPCA）［3］是RPCA 的拓展。當數(shù)據(jù)被兩種以上的混合噪聲污染時，RPCA處理結果并不理想，而GRPCA通過最小化核范數(shù)、l1范數(shù)和l21范數(shù)的組合問題，可以分離出被混合噪聲污染的低秩矩陣。RPCA 和GRPCA 的應用廣泛［3-4］，但是RPCA 和GRPCA 算法在解決數(shù)據(jù)結構非低秩性時效果會很差，即無法分離出1 個低秩矩陣L。為了處理L不滿足低秩的問題，目前已有的解決方法是假設L在特征映射后是低秩的，這意味著L在某些特征空間是潛在低秩的，而在原始空間中本身的秩比較高甚至是滿秩的。相關的代表算法有核主成分分析（Kernel Principal Component Analysis，KPCA）。KPCA 是傳統(tǒng)主成分分析（Principal Component Analysis，PCA）的擴展，它主要尋求核空間中數(shù)據(jù)點的近似低秩。與傳統(tǒng)PCA 相似的是，即使在映射后，KPCA對離群點（outliers）也非常敏感，如果數(shù)據(jù)存在大量噪聲或者離群點，KPCA 處理問題的效果會非常差，因此一些魯棒的核低秩算法進一步被提出。如文獻［5-6］等的研究中就提供了一種處理子空間聚類的核低秩方法，并且驗證了核低秩近似確實有利于非線性數(shù)據(jù)的聚類。盡管這些方法在聚類和線性低秩恢復任務上取得了很大的成功，但是它們都無法恢復原始空間中的非線性或超低維數(shù)據(jù)，所以本質(zhì)上不能直接應用于非線性數(shù)據(jù)恢復問題。目前Xie等［7-8］提出了一種更加魯棒的核低秩算法來處理非低秩數(shù)據(jù)恢復問題，該算法基于RPCA，考慮當L從原始空間映射到可再生核希爾伯特空間H中能得到Φ(L)，此時非線性的觀測點可以被認為是線性的，因此Φ(L)此時是低秩的。噪聲矩陣E是逐列稀疏的，因此采用l21范數(shù)作為E的約束。在求解這個模型時，采用了核函數(shù)，例如凸的多項式核函數(shù)以及非凸的高斯核，采用核函數(shù)的目的主要是為了方便計算，降低計算難度。Xie 等［7-8］的算法相比之前的KPCA 算法結果更魯棒，但是算法的計算復雜度高，計算過程中損耗較大，且僅解決了矩陣恢復問題，對于視頻恢復即張量處理沒有提及。本文提出了一種新的處理非線性數(shù)據(jù)的算法——卷積魯棒主成分分析（Convolution Robust Principal Component Analysis，CRPCA），不僅可以處理矩陣恢復問題，也可以應用于視頻恢復，這是其他算法無法比擬的。CRPCA 保留了RPCA 本身的優(yōu)良性質(zhì)，同時將RPCA 與卷積矩陣（Convolution Matrix，CM）結合，不需要將非線性的數(shù)據(jù)映射到某個特征空間，而是利用卷積矩陣的低秩性，即A(L)是低秩的，同時考慮噪聲E是稀疏的，然后使用乘子交替方向法（Alternating Direction Method of Multipliers，ADMM）［9-12］來求解目標函數(shù)，最后將CRPCA 應用于去噪實驗，結果表明，相對于RPCA、GRPCA、KRPCA 算法，CRPCA 算法的去噪效果更好、復雜度更低、計算損耗更少。

1 主要符號及公式

大寫字母表示1 階或更高階的張量，包括向量、矩陣和高階張量。在大多數(shù)情況下，本文考慮矩陣問題（即2 階張量），對于矩陣X，X：，j表示矩陣X的第j列，Xi，：表示矩陣X的第i行，矩陣的奇異值分解為X=UΣVT，‖X‖*=Σiσi(X)表示矩陣的核范數(shù)，也就是矩陣X的奇異值之和?！琗‖1=Σij‖Xij‖表示X的l1范數(shù)，表示X的l21范數(shù)。兩個其中XT是矩陣的轉置，tr(·)是矩陣的跡，I定義為單位矩陣。手寫體字體，例如A 表示線性算子，I 表示單位算子，對于希爾伯特空間之間的線性算子L：H1→H2，它的Hermitian 伴隨（或共軛）算子定義為L*，并且有以下定義：矩陣的歐氏內(nèi)積為

2 魯棒主成分分析

魯棒主成分分析（RPCA）很早就被提出，但至今依然受大家關注。在許多實際應用中，假設所給定的很大的數(shù)據(jù)矩陣M，它可以分解成：

其中：L是低秩的，E是稀疏的。此時并不知道L的列空間和行空間，甚至不知道它們的維數(shù)。同樣，也不知道E中非零項的位置以及個數(shù)。為了恢復矩陣當矩陣M的低秩結構L，本文考慮當E中元素服從獨立同分布的高斯分布，那么可以使用經(jīng)典的PCA來求解這個問題，即求解以下最優(yōu)化問題：

對矩陣M進行奇異值分解（Singular Value Decomposition，SVD）可以得到上述優(yōu)化問題的最優(yōu)解。但是當M有大量噪聲時，傳統(tǒng)PCA方法無法解決這個問題。此時優(yōu)化問題為：

該優(yōu)化問題是NP 難問題，無法在多項式時間內(nèi)求解，所以對此優(yōu)化問題的目標函數(shù)進行凸松弛。矩陣的核范數(shù)是秩函數(shù)的凸替代，矩陣的l1范數(shù)是l0范數(shù)的凸包，故將上述問題轉化成以下凸優(yōu)化問題：

Candès 等經(jīng)過研究證明了在滿足一定的條件下，矩陣的低秩部分L和稀疏部分E可以被準確地恢復出來。

3 卷積魯棒主成分分析

卷積魯棒主成分分析（CRPCA）是在魯棒主成分分析（RPCA）的基礎上加入卷積矩陣，解決了RPCA 無法求解數(shù)據(jù)不滿足低秩結構的問題，在處理非線性數(shù)據(jù)上有很好的效果。

3.1 卷積矩陣

在信號處理中，（離散）卷積是最基礎、最重要的概念。它的定義雖然大多是唯一的，但是也有很多種不同的解釋，這取決于使用的邊界條件。本文考慮的是循環(huán)卷積，即考慮循環(huán)邊界條件的卷積［13-14］。循環(huán)卷積過程就是將X∈Rm和K∈Rk(k≤m)轉換成X*K∈Rm：

其中：*表示卷積算子，假設[X]i-s=[X]i-s+m(i≤s)，這就是循環(huán)邊界條件。在本文一直假設k≤m，并稱K為卷積核。普遍來說，卷積算子是線性的并且可以轉換成矩陣相乘的形式：

其中：Ak(X)是卷積矩陣，下標k表示卷積矩陣總是與核大小k相關。根據(jù)循環(huán)卷積，向量X=[x1，x2，…，xm]的卷積矩陣是大小為m×k的截斷循環(huán)矩陣：

換句話說，Ak(X)的第j列就等于Sj-1(X)，S是循環(huán)移位運算符：該移位算子可以由Matlab 中circshit 函數(shù)實現(xiàn)，在k=m的特殊情況下，卷積矩陣Ak(X)是m×m的循環(huán)方陣。vec(·)是將X*K向量化，因此，可以得到：

3.2 基本性質(zhì)

考慮最簡單的例子，向量X∈Rm，那么它的卷積矩陣為Ak(X)∈Rm×k，則：

3.3 潛在低秩結構恢復

當n=1并且L為向量時，卷積矩陣Ak(L)的第j列其實是L中元素循環(huán)移位到j-1 個位置。準確地說，當L具有基本連續(xù)性，且移動程度相對較小時，循環(huán)移動前后的信號大多是低秩的，所以低秩的卷積矩陣將存在。為了處理數(shù)據(jù)潛在低秩問題，解決以下凸優(yōu)化問題：

這個優(yōu)化問題是凸的，可以被不同的方法解決。為了計算的有效性，在本文中采用乘子方向交替法（ADMM）。首先將式（9）轉換成下列等式問題：

其增廣拉格朗日函數(shù)為：

上述的問題是無約束的。通過固定其他變量，并分別對變量R、L、E求導，然后更新拉格朗日乘子Y1和Y2，μ＞0為懲罰項參數(shù)。本文算法概述了ADMM 求解凸優(yōu)化問題（9）。在更新變量時利用了奇異值閾值（Singular Value Thresholding，SVT）算子和收縮算子（Shrinkage Operator，SO）［15-16］求解。

本文算法的實現(xiàn)過程如下所示：

1）輸入數(shù)據(jù)M和參數(shù)λ。

2）對相關參數(shù)進行初始化R=L=0，E=0，Y1=Y2=0，μ=10-6，μmax=1010，ρ=1.05，ε=10-6，iter=0，Itermax=103。

3）固定其他變量，更新R：

4）固定其他變量，更新E：

5）固定其他變量，更新L：

6）更新拉格朗日乘子：

7）更新參數(shù)：

8）如未達到收斂條件

4 實驗結果及分析

實驗測試了卷積魯棒主成分分析用于圖像去噪、視頻去噪的能力，分別在合成數(shù)據(jù)、MNIST、COIL-2 數(shù)據(jù)集以及DeepVideoDeblurring 視頻數(shù)據(jù)集上進行測試，顯示了本算法對復雜數(shù)據(jù)處理的高效性。

4.1 實驗設置

1）基線（Baseline）：本文比較了幾種方法，包括魯棒主成分分析（RPCA）、核魯棒主成分分析（KRPCA）、廣義魯棒主成分分析（GRPCA）來評估模型的性能。

2）評估指標（Evaluation Metric）：峰值信噪比（Peak Signal-to-Noise Ratio，PSNR），單位為dB。

其中：X0、Xrec∈Rm×n分別為原始數(shù)據(jù)和恢復數(shù)據(jù)。

4.2 算法復雜度分析

假設輸入矩陣為M∈Rm×n，在RPCA 計算過程中單步迭代計算復雜度為O(m2n)，并且需要O(1/ε)的迭代次數(shù)以達到準確度ε。KRPCA 中計算奇異值分解以及n的立方根的總計算復雜度為O(n3+rn2)。在求解GRPCA 算法中，每一次循環(huán)中，奇異值分解的運算量為O((m+n)3)，矩陣求逆的運算量為O((m+n)3)。此外GRPCA 算法循環(huán)內(nèi)的多次乘法加法和截斷閾值的運算量為O(5n(m+n)+14n)。因此，GRPCA 算法的計算復雜度為O((m+n)3+I()5n(m+n)+14n)，其中I為循環(huán)的次數(shù)。

4.3 數(shù)據(jù)去噪

1）本文先對合成數(shù)據(jù)進行實驗，圖1 展示了向量恢復的結果，即對一維數(shù)組處理結果。實驗中隨機選取了100 個點，形成f(x)=sinx離散函數(shù)；再選取20 個點作為離群點。在這個實驗中，恢復出的數(shù)據(jù)L十分接近真實值truth，驗證了本文算法的準確性和有效性。

圖1 對向量的恢復效果Fig.1 Effect of vector recovery

2）表1 以及圖2 使用MNIST 數(shù)據(jù)集和COIL-20 數(shù)據(jù)集，黑白圖片作為二維數(shù)組，可視為矩陣。該部分驗證了算法對圖片的恢復能力，即恢復潛在矩陣低秩的高效性?？梢钥闯霰疚乃惴ㄐЧ噍^于其他三種算法，結果更好，恢復的準確度更高。

圖2 矩陣恢復的效果Fig.2 Effect of matrix recovery

表1 不同方法在MNIST和COIL-20數(shù)據(jù)集上峰值信噪比的對比 單位：dBTab.1 Comparison of PSNR of different methods on MNIST and COIL-20 datasets unit：dB

3）張量是多維數(shù)組，視頻比圖片多了時間信息，因此視頻可視作張量。由于攝像頭的晃動，導致拍攝的視頻背景變化，因此無法將背景看作低秩的，無法將前景從背景中分離出來。該部分利用DeepVideoDeblurring 視頻序列，同時加入噪聲作為輸入。而RPCA、KRPCA、GRPCA 無法對視頻（即張量）整體進行操作，圖3展示了本文算法對視頻序列的處理。

圖3 視頻恢復的效果（按順序截取視頻的前12幀）Fig.3 Effect of video recovery（capturing 12 frames of the video in sequence）

5 結語

本文介紹了一種新的去噪算法卷積魯棒主成分分析（CRPCA）。在解決數(shù)據(jù)潛在低秩的情況下，卷積魯棒主成分分析利用數(shù)據(jù)矩陣將數(shù)據(jù)轉換為低秩，并與魯棒主成分分析（RPCA）結合，同時采用乘子交替方向法（ADMM）進行計算。相較于傳統(tǒng)的魯棒主成分分析（RPCA）和核魯棒主成分分析（KRPCA）以及廣義魯棒主成分分析（GRPCA），在解決非線性數(shù)據(jù)及去噪問題上，由表和圖可以看出，本文算法效果更好，恢復出的數(shù)據(jù)更接近原始數(shù)據(jù)，在對向量、矩陣去噪處理上均取得了不錯的效果；同時，解決了其余算法無法處理的視頻問題，即張量去噪問題。除了去噪問題外，本文算法也可用于圖像的去模糊問題。