王海鵬，降愛蓮，李鵬翔

（太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院，山西晉中 030600）

（?通信作者電子郵箱ailianjiang@126.com）

0 引言

主成分分析（Principal Component Analysis，PCA）作為一種常用的數(shù)據(jù)降維方法，在數(shù)據(jù)分析、目標(biāo)檢測、圖像識(shí)別等領(lǐng)域得到了廣泛應(yīng)用。PCA算法能夠提取目標(biāo)數(shù)據(jù)的主要特征達(dá)到降維的效果［1］。如果數(shù)據(jù)含有稀疏噪聲，PCA 提取的特征子空間會(huì)向噪聲數(shù)據(jù)方向偏移。魯棒主成分分析（Robust Principal Component Analysis，RPCA）是一種能夠?qū)哂薪Y(jié)構(gòu)信息但是被稀疏噪聲破壞的數(shù)據(jù)矩陣進(jìn)行分解的算法，找到隱藏在原始數(shù)據(jù)中的低秩成分，實(shí)際上就是找到了數(shù)據(jù)的本質(zhì)低維空間。RPCA 不僅在特征提取中有著抵抗噪聲的特性，而且在視頻的背景前景分離［2-4］、魯棒人臉識(shí)別［5］、移動(dòng)目標(biāo)檢測［6］等領(lǐng)域也具有廣闊的應(yīng)用前景。

2011 年，Candès 等［7］首次定義了RPCA 問題，即將一個(gè)含有稀疏噪聲的數(shù)據(jù)矩陣分解為低秩矩陣與稀疏矩陣兩部分。為了保證稀疏矩陣足夠稀疏，使用l0-范數(shù)進(jìn)行約束，同時(shí)要使低秩矩陣的秩盡可能小。然而Gillis等［8］證明二進(jìn)制矩陣（0-1矩陣）的分解是NP-Hard 問題，進(jìn)而證明l0-范數(shù)約束最優(yōu)化是一個(gè)NP-Hard 問題。由于l0-范數(shù)無法使用凸優(yōu)化解決，文獻(xiàn)［7］將RPCA 問題的低秩與稀疏約束松弛為核范數(shù)與l1-范數(shù)約束的目標(biāo)函數(shù)最優(yōu)化問題，并用拉格朗日方向交替法［9］求解。由于該算法每次迭代需要對(duì)數(shù)據(jù)進(jìn)行奇異值分解求核范數(shù)，因此該算法的時(shí)間復(fù)雜度非常高［4］。Shen 等［10］提出了基于增廣拉格朗日方向交替法的低秩矩陣擬合（Low-Rank Matrix Fitting，LMaFit）算法，該算法用兩個(gè)低秩矩陣的乘積表示一個(gè)低秩矩陣的方法代替核范數(shù)，降低了因使用奇異值分解而產(chǎn)生的時(shí)間開銷。這種方法是后續(xù)研究中降低時(shí)間開銷的重要方法。Yi 等［11］提出基于梯度下降（Gradient Descent，GD）的RPCA 算法，該算法使用稀疏矩陣估計(jì)算子估計(jì)出原始數(shù)據(jù)的稀疏矩陣的近似矩陣。GD 算法在優(yōu)化算法上選擇了梯度下降，提高了算法的運(yùn)行效率。Lu 等［12］推導(dǎo)出了張量核范數(shù)、張量軟閾值算子，并以此構(gòu)建數(shù)學(xué)模型，采用方向交替拉格朗日乘子法實(shí)現(xiàn)了張量魯棒主成分分析（Tensor Robust Principal Component Analysis，TRPCA）算法，該算法提高了RPCA 算法對(duì)彩色圖像處理、視頻背景建模的能力。TRPCA 算法因?yàn)槭褂昧藦埩科娈愔捣纸?，因此時(shí)間復(fù)雜度較高。Chereau 等［13］提出了基于最大相關(guān)熵模型的RPCA 算法，他們采用了冪迭代的方式來求解最大相關(guān)熵模型，進(jìn)而實(shí)現(xiàn)RPCA 算法。該算法的優(yōu)點(diǎn)是不需要預(yù)先設(shè)置低秩矩陣的主成分的數(shù)量，提高了算法的易用性。由于上述RPCA 算法的計(jì)算時(shí)間隨著數(shù)據(jù)規(guī)模提高而顯著提升，處理大規(guī)模數(shù)據(jù)會(huì)消耗大量的時(shí)間，因此本文將針對(duì)RPCA 問題，通過改進(jìn)RPCA 模型，降低RPCA 算法的時(shí)間復(fù)雜度，進(jìn)而降低數(shù)據(jù)規(guī)模對(duì)RPCA算法的影響，提高RPCA算法的運(yùn)行速度。

1 RPCA問題及模型

由于主成分分析算法是由歐氏距離最小化推導(dǎo)出的算法，因此稀疏噪聲會(huì)因?yàn)闅W氏距離的二次方特性對(duì)主成分分析算法求得結(jié)果產(chǎn)生較大的影響［14］。

圖1（a）展示了PCA 算法在數(shù)據(jù)較均勻的條件下的效果，從圖中可以看出，PCA 能夠準(zhǔn)確地對(duì)這些分布均勻的數(shù)據(jù)降維。如果數(shù)據(jù)含有稀疏噪聲，如圖1（b），PCA 算法的結(jié)果會(huì)產(chǎn)生較大的偏差。RPCA 算法提取了含有稀疏噪聲數(shù)據(jù)的主要特征，并且對(duì)該含噪數(shù)據(jù)進(jìn)行了降維。

圖1 PCA算法與RPCA算法對(duì)比Fig.1 Comparison of PCA algorithm and RPCA algorithm

為了將含噪數(shù)據(jù)分解為低秩矩陣和稀疏矩陣，同時(shí)使低秩矩陣的秩與稀疏矩陣的非0 元素的數(shù)量盡可能少，文獻(xiàn)［7］中將RPCA模型表示為：

其中：Y表示包含稀疏噪聲的數(shù)據(jù)，L表示數(shù)據(jù)中的低秩部分，S 表示數(shù)據(jù)中的稀疏部分，rank(L)表示L 的秩，模型（1）滿足Y=L+S。模型（1）理論上可以達(dá)到分離低秩矩陣和稀疏矩陣的目的。然而l0-范數(shù)是一種無法使用凸優(yōu)化求解的范數(shù)。為了優(yōu)化模型（1），因此使用核范數(shù)與l1-范數(shù)將模型（1）松弛化為：

2 NSTI模型及其優(yōu)化算法分析

本文改進(jìn)原有RPCA 模型，提出了一個(gè)新的RPCA 模型，使得該模型在能夠表示RPCA 問題的基礎(chǔ)上又能夠采用簡單高效的方法進(jìn)行優(yōu)化，該優(yōu)化方法稱為牛頓-軟閾值迭代（Newton-Soft Threshold Iteration，NSTI）算法。

2.1 NSTI算法模型

為了降低因計(jì)算奇異值分解而導(dǎo)致的巨大的算法運(yùn)行時(shí)間的開銷，LMaFit和GD算法使用了如式（3）所示的方法：

其中U、V 是兩個(gè)低秩矩陣，滿足L=UVT。鑒于這種利用兩個(gè)低秩矩陣的乘積表示一個(gè)低秩矩陣的方法，可避免使用核范數(shù)，本文改進(jìn)模型（2），并給出NSTI算法的數(shù)學(xué)模型：

式（4）左邊的范數(shù)中，低秩矩陣L由兩個(gè)低秩矩陣U、V 的乘積表示，因?yàn)閞ank(L)=min(rank(U)，rank(V))，所以能夠保證L 是一個(gè)低秩矩陣。式（4）左邊是一個(gè)能夠?qū)、V 進(jìn)行凸優(yōu)化求解的范數(shù)，本文用牛頓法來優(yōu)化左邊的范數(shù)。采用牛頓法求解的原因有兩個(gè)：第一，牛頓法比梯度下降收斂速度更快；第二，不會(huì)因?yàn)槭褂昧伺ｎD法而增加過多的時(shí)間開銷。

式（4）右邊稀疏矩陣S 通過l1-范數(shù)來表示其稀疏性質(zhì)。l1-范數(shù)是l0-范數(shù)的凸近似。最小化l1-范數(shù)的目的是為了讓S稀疏化。本文采用軟閾值迭代算法求解稀疏矩陣S。該方案相對(duì)于文獻(xiàn)［11］中的GD 算法的稀疏矩陣估計(jì)算子，具有計(jì)算速度快的優(yōu)點(diǎn)。軟閾值迭代算法的缺點(diǎn)是軟閾值是靜態(tài)的，并且需要在算法運(yùn)行之前根據(jù)數(shù)據(jù)調(diào)整軟閾值的大小。本文提出了軟閾值估計(jì)算子，用來彌補(bǔ)軟閾值迭代算法中的不足。

2.2 NSTI算法

NSTI算法分為兩部分，其中一部分是求解稀疏矩陣S。S對(duì)于模型（4）的梯度為：

由軟閾值迭代算法［15］，可求出稀疏矩陣S 的近似解。式（6）是軟閾值算子也是S近似解的計(jì)算式。

NSTI 算法的另一部分是求解低秩矩陣的兩個(gè)因子U、V。U、V對(duì)于模型（4）的一階梯度為：

Hessian 矩陣是牛頓法求解的關(guān)鍵，通過計(jì)算出Hessian矩陣，就能利用牛頓法求出低秩矩陣U、V。U、V 矩陣對(duì)應(yīng)的Hessian矩陣為：

因此，可得到如下兩式：

NSTI算法詳細(xì)過程如下。

輸入 數(shù)據(jù)Y，精確度α，收斂閾值t，秩r；

輸出 U、V、S。

1）首先對(duì)Y 進(jìn)行奇異值分解，選取前r個(gè)奇異值與前r個(gè)左奇異向量的乘積初始化U，選取前r 個(gè)奇異值與前r 個(gè)右奇異向量的乘積初始化V。稀疏矩陣S為0矩陣。

2）計(jì)算Y'=Y -UVT，并計(jì)算軟閾值λ=f(Y'，α)。

3）利用軟閾值迭代求出稀疏矩陣S=soft(Y'，λ)。

4）計(jì)算矩陣E=Y'-S，以及U、V 的Hessian 矩陣的逆

NSTI 算法思想借鑒了方向交替法。將模型（4）中要求的3 個(gè)變量分為兩部分，通過交替迭代求解模型中的3 個(gè)變量。2.1 節(jié)提到牛頓法比梯度下降收斂速度更快，軟閾值迭能夠快速求解稀疏部分，因此NSTI采用牛頓法與軟閾值迭代交替計(jì)算的方案來優(yōu)化模型（4）。該方案能夠求解模型（4）中的3個(gè)變量并且算法的收斂速度與計(jì)算速度都得到了提升。

2.3 軟閾值估計(jì)

軟閾值λ 決定著數(shù)據(jù)Y 中的數(shù)據(jù)的劃分：λ 值越低，每次迭代，能提取更多的元素成為稀疏矩陣，然而這樣會(huì)使得原本屬于低秩矩陣的成分被劃分到稀疏矩陣中，優(yōu)點(diǎn)是能夠提高算法的精確度；反之，λ 值越高，將提高低秩矩陣元素的比例，優(yōu)點(diǎn)是能夠降低算法迭代次數(shù)。如果λ 值過高，那么最終收斂的結(jié)果會(huì)將全部元素劃分到低秩矩陣L中，稀疏矩陣S將會(huì)是一個(gè)0矩陣；反之，λ值過低，那么全部元素將劃分到稀疏矩陣S中，L矩陣將變成一個(gè)0矩陣。軟閾值計(jì)算方式為：

對(duì)任意屬于Y'(Y'=Y -UVT)的元素a1、a2，通過和閾值λ 比較，小于閾值λ 的則被歸到低秩成分L 中，大于λ 的被歸到稀疏成分S中。如果|a1|＜|a2|，而且一定存在低秩成分，那么a1比a2更有可能是低秩成分，低秩空間UVT的元素被認(rèn)為是其對(duì)應(yīng)原始數(shù)據(jù)Y 的元素在低秩空間的投影，原始數(shù)據(jù)減去其在低秩空間大的投影的絕對(duì)值是原始數(shù)據(jù)元素到低秩子空間的距離。將數(shù)據(jù)擴(kuò)展到Y(jié) 全部元素，對(duì)于任意ai(i=1，2，…，mn -1，mn)，一定存在這樣的一個(gè)序列，其中ai與bj是一一對(duì)應(yīng)關(guān)系。通過式（13）估計(jì)一個(gè)λ，將數(shù)據(jù)中距離平面較近的一部分劃分為一個(gè)低秩矩陣，將距離平面較遠(yuǎn)的數(shù)據(jù)部分劃分為一個(gè)稀疏矩陣。通過調(diào)節(jié)α 的大小控制λ 的大小，進(jìn)而控制算法的精確度。

2.4 NSTI時(shí)間復(fù)雜度分析

假設(shè)數(shù)據(jù)Y 是一個(gè)m × n 的數(shù)據(jù)矩陣，Y=L+S，L 是一個(gè)m × n 的矩陣，L 矩陣的秩為r，r 遠(yuǎn)小于m 和n。假設(shè)矩陣U、V 的規(guī)模分別為m × r，n × r，那么L 的秩最大為r。對(duì)于稀疏矩陣S，S的規(guī)模為m × n。

基于上述假設(shè)，奇異值分解的時(shí)間復(fù)雜度為O(n2m)，初始化U、V 矩陣的過程為O(mr)，因此初始化過程時(shí)間復(fù)雜度為O(n2m)。

在算法迭代過程中：第2）、3）步時(shí)間復(fù)雜度為O(nm)；第4）步求解Hessian 矩陣時(shí)，需要計(jì)算的時(shí)間復(fù)雜度為O(mnr)，在求Hessian 矩陣的逆矩陣中，因?yàn)镠essian 矩陣的規(guī)模時(shí)r ×r，所以Hessian 矩陣的逆運(yùn)算開銷可以忽略；同理第6）步中的時(shí)間復(fù)雜度為O(mnr)。因此每次迭代復(fù)雜度為O(mnr)，軟閾值估計(jì)算子的時(shí)間復(fù)雜度為O(nm)。假設(shè)算法迭代x次收斂，則算法完整的時(shí)間復(fù)雜度為O(xnmr)，因?yàn)閞遠(yuǎn)小于m 和n，因此算法時(shí)間復(fù)雜度近似為O(xnm)。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)選取NSTI 算法、LMaFit 算法和GD 算法三個(gè)算法進(jìn)行對(duì)比。LMaFit、GD 是文獻(xiàn)［16-17］評(píng)價(jià)認(rèn)可的效率較高的兩個(gè)算法。通過與LMaFit算法和GD算法對(duì)比來證明NSTI算法時(shí)間效率和算法精確度的提高。實(shí)驗(yàn)環(huán)境為Matlab 2019a，實(shí)驗(yàn)機(jī)器配置為Intel Core i7 8700，6 核心12 線程，內(nèi)存為8 GB，操作系統(tǒng)為Windows 10。在實(shí)驗(yàn)中的奇異值分解函數(shù)為PROPACK 數(shù)據(jù)分析工具包中的lansvd 函數(shù)?；趌anczos分解的lansvd 奇異值分解函數(shù)具有比傳統(tǒng)奇異值分解函數(shù)更快的計(jì)算速度。

3.2 算法有效性分析

為了驗(yàn)證算法是有效的，將從算法的整體損失、低秩矩陣損失和稀疏矩陣損失三個(gè)角度來說明。算法整體損失為l，l越小說明算法越精確，提取的稀疏矩陣越稀疏。其中l(wèi)為：

決定數(shù)據(jù)Y 規(guī)模的參數(shù)有m、n 和低秩矩陣的秩r 以及稀疏矩陣的非0元素的比例a，其中數(shù)據(jù)Y=L+S。低秩矩陣L中的元素生成過程如下：首先生成一組基向量，選擇r 個(gè)基向量，隨機(jī)組合生成一個(gè)m × n 的秩為r 的低秩矩陣L。然后利用a 隨機(jī)生成一個(gè)稀疏矩陣S，該實(shí)驗(yàn)使用Matlab 內(nèi)置函數(shù)sprand。

實(shí)驗(yàn)數(shù)據(jù)的規(guī)模設(shè)為1 000×1 000，低秩矩陣的秩為20，稀疏矩陣的稀疏度為0.2。圖2（a）顯示隨著迭代次數(shù)增加，算法整體與各部分逐漸收斂。NSTI 算法借鑒了方向交替法的思想，每次迭代求出一組參數(shù)，作為下次迭代的輸入。算法每次迭代，都能夠降低算法的整體損失與各參數(shù)的損失，最終達(dá)到算法的整體收斂。圖2（b）中驗(yàn)證了算法能夠正確地求出一個(gè)符合輸入數(shù)據(jù)的稀疏度的稀疏矩陣。算法在迭代初期，計(jì)算出的稀疏矩陣包含大量的非0 元素，但隨著算法迭代，稀疏矩陣收斂于原始的稀疏矩陣。

圖2 NSTI算法運(yùn)行效果Fig.2 Running effect of NSTI algorithm

3.3 算法性能對(duì)比

為了驗(yàn)證NSTI 算法的時(shí)間效率的提升。設(shè)計(jì)實(shí)驗(yàn)對(duì)比三種算法在同一數(shù)據(jù)下經(jīng)過迭代達(dá)到相同的損失l 所需要的運(yùn)行時(shí)間。

圖3 是三種算法在相同規(guī)模的數(shù)據(jù)下運(yùn)行時(shí)間的對(duì)比，說明了NSTI 算法比LMaFit 算法、GD 算法，運(yùn)行速度要快，運(yùn)行時(shí)間穩(wěn)定。

圖3 三種算法在不同數(shù)據(jù)規(guī)模下的對(duì)比Fig.3 Comparison of three algorithms under different data sizes

LMaFit 的單次迭代時(shí)間復(fù)雜度為O(n3)，GD 算法的單次迭代時(shí)間復(fù)雜度為O(n3)，NSTI 算法單次迭代時(shí)間復(fù)雜度為O(n2)，所以NSTI的計(jì)算時(shí)間相對(duì)LMaFit、GD增長緩慢。在算法機(jī)理上，NSTI 選用的牛頓法，在理論上比梯度下降收斂速度快，又因?yàn)镽PCA 問題的低秩的特性，牛頓法的計(jì)算速度由O(n3)變?yōu)镺(n2)，所以牛頓法比梯度下降法計(jì)算速度快。NSTI選擇的軟閾值迭代法理論上時(shí)間復(fù)雜度為O(n2)，在保證算法準(zhǔn)確度的同時(shí)，保證了算法的時(shí)間效率。

圖4 是當(dāng)非0 元素比例a=0.1，數(shù)據(jù)規(guī)模為5 000×5 000，通過調(diào)整低秩矩陣的秩r，對(duì)數(shù)據(jù)進(jìn)行矩陣分解，對(duì)比三個(gè)算法在達(dá)到相同的損失l所需要的時(shí)間：當(dāng)r ＜8時(shí)，NSTI算法與GD 算法運(yùn)行時(shí)間比較穩(wěn)定；當(dāng)r ≥8時(shí)，三種算法的變化規(guī)律逐漸接近。

由于算法機(jī)理的不同，NSTI、GD 與LMaFit 單次迭代的時(shí)間隨著r提升而小幅提升，然而LMaFit的迭代次數(shù)隨著r的提升而降低，進(jìn)而降低了計(jì)算時(shí)間。如圖4，NSTI 與GD 算法略有提升，LMaFit算法有明顯下降。

圖4 三種算法在不同低秩r下運(yùn)行時(shí)間對(duì)比Fig.4 Comparison of running time of three algorithms under different low rank r conditions

圖5 展示了NSTI 對(duì)比其他算法的時(shí)間效率提升百分比，圖5的數(shù)據(jù)來源是圖4。通過圖5可以看出，NSTI算法在秩為1 時(shí)相比較GD、LMaFit 算法，能夠分別提升54.0%與93.5%的時(shí)間效率；當(dāng)秩為20 時(shí)，能夠分別提升24.6%與45.5%的時(shí)間效率。

圖5 與對(duì)比算法相比NSTI的性能提升Fig.5 Performance improvement of NSTI compared with comparison algorithm

3.4 視頻背景/前景提取實(shí)驗(yàn)

為了驗(yàn)證NSTI算法在視頻前景背景分離的能力，設(shè)計(jì)實(shí)驗(yàn)對(duì)比算法在視頻背景/前景提取中的效果。將視頻看做數(shù)據(jù)Y，視頻的背景看作是低秩矩陣L，視頻的前景看作是稀疏矩陣S［15］。對(duì)視頻的數(shù)據(jù)矩陣進(jìn)行RPCA，得到低秩矩陣和稀疏矩陣。低秩矩陣輸出為背景，稀疏矩陣輸出為前景。圖6為該實(shí)驗(yàn)要處理視頻的第40、70、100幀。

圖6 原始視頻Fig.6 Original video

圖7 展示不同算法提取的背景。對(duì)比提取的背景，在第70幀和第100幀中原畫汽車的位置，GD算法與LMaFit算法出現(xiàn)黑影，在NSTI 算法對(duì)應(yīng)的位置沒有黑影，色彩與原始圖像的色彩基本一致，這說明NSTI 算法提高了去除噪聲的能力。在右側(cè)欄桿位置，LMaFit 算法將欄桿全部劃分到前景，NSTI算法，GD算法將欄桿算作背景。

圖8 中的GD 和LMaFit 算法出現(xiàn)一個(gè)NSTI 算法中沒有出現(xiàn)的圖塊。對(duì)比9 張?zhí)崛〉那熬皥D片，NSTI 算法相對(duì)GD、LMaFit 算法，提取的視頻前景最完整。表1 說明NSTI 算法比其他算法的運(yùn)行時(shí)間效率至少提高了78.7%。

RPCA 算法能夠?qū)?shù)據(jù)分解為一個(gè)低秩矩陣和一個(gè)稀疏矩陣，進(jìn)而將視頻分解為背景與前景。又因?yàn)樵撘曨l數(shù)據(jù)的背景的秩為1，因此能夠保證NSTI 算法的牛頓法部分的時(shí)間效率最高。NSTI 采用了軟閾值迭代法，同時(shí)用軟閾值估計(jì)算子確定軟閾值，這種改進(jìn)了的軟閾值迭代算法能夠求出更加精確的稀疏矩陣，因此可以從數(shù)據(jù)中看出NSTI算法求出的前景更加精確。

圖7 不同算法提取的背景對(duì)比Fig.7 Comparison of background extracted by different algorithms

圖8 不同算法提取的前景對(duì)比Fig.8 Comparison of foreground extracted by different algorithms

表1 各算法消耗的時(shí)間 單位：sTab.1 Time consumed by different algorithms unit：s

3.5 圖像降噪實(shí)驗(yàn)

為了證明算法在圖像降噪的能力的提升，本實(shí)驗(yàn)對(duì)一組a=0.2含噪圖片進(jìn)行降噪。實(shí)驗(yàn)數(shù)據(jù)共有10張含噪圖片。圖像降噪實(shí)驗(yàn)中，原始圖像被視為低秩矩陣L，噪聲被視作稀疏矩陣S，通過RPCA 處理達(dá)到降噪效果。本實(shí)驗(yàn)將對(duì)比算法的運(yùn)行時(shí)間以及算法的殘差e，利用殘差對(duì)比算法的精確度高低，e越小精確度越高。e的計(jì)算方式為：

其中：L表示圖片的數(shù)據(jù)矩陣，Lsrc表示原始圖片，Li表示第i幅含噪圖片降噪后的結(jié)果。該實(shí)驗(yàn)采用峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）［12］來評(píng)價(jià)算法的降噪能力。

圖9 的數(shù)據(jù)說明了NSTI 算法的輸出結(jié)果噪點(diǎn)最少，相比GD和LMaFit，NSTI的圖像更加清晰。表2的數(shù)據(jù)說明了NSTI的殘差值比其他算法至少降低了45.3%。NSTI算法的時(shí)間效率比其他兩個(gè)算法至少高出64.3%。NSTI算法計(jì)算得到的圖片的PSNR 值比LMaFit 算法高出18.8%，比GD 算法高出24.8%。因此可以說明NSTI算法處理的圖像更加清晰。

表2 圖像降噪實(shí)驗(yàn)Tab.2 Image denoising experiment

圖9 圖像降噪實(shí)驗(yàn)Fig.9 Image denoising experiment

因?yàn)镹STI算法提高了算法效率，所以在處理圖像數(shù)據(jù)更加高效，NSTI 算法比LMaFit 算法提高的時(shí)間效率為78.29%，與圖5的數(shù)據(jù)相符合。NSTI算法采用了改進(jìn)的軟閾值迭代算法，不需要預(yù)估稀疏度，相比較稀疏矩陣估計(jì)算子，提高了圖像降噪的水平，PSNR高達(dá)31.337 5 dB。

3.6 圖像恢復(fù)實(shí)驗(yàn)

為了驗(yàn)證NSTI 算法在圖像恢復(fù)方面的能力設(shè)計(jì)人臉恢復(fù)實(shí)驗(yàn)，選取的對(duì)比算法有GD、LMaFit、TRPCA 算法，數(shù)據(jù)集為耶魯大學(xué)的人臉數(shù)據(jù)集。耶魯大學(xué)的人臉數(shù)據(jù)包含面部的不同表情、光影、方向及佩飾的圖像。

圖10 4種算法的圖像恢復(fù)效果對(duì)比Fig.10 Image recovery effects comparison among four algorithms

表3展示了各個(gè)算法分別處理得到的圖像的PSNR 的值，PSNR 值越大，說明算法的恢復(fù)圖像能力越強(qiáng)。圖10 驗(yàn)證了NSTI算法能夠有效地恢復(fù)圖像。與LMAFit相比，NSTI的時(shí)間效率與PSNR 值比較高，這一點(diǎn)在表3 中得到驗(yàn)證。NSTI，GD與TRPCA算法的PSNR值在表3中無明顯區(qū)別，這說明對(duì)于耶魯大學(xué)數(shù)據(jù)集，NSTI、GD 與TRPCA 三種算法的圖像恢復(fù)能力基本一致。因?yàn)镹STI算法使用了牛頓法與軟閾值迭代法，所以在時(shí)間效率上，NSTI比另外三種算法要高，能夠快速地計(jì)算出人臉的低秩特征。表3證明了NSTI有著最高的時(shí)間效率。

NSTI 算法比其他算法的時(shí)間效率高的原因有兩點(diǎn)：第一，GD 算法每次迭代需要求解稀疏矩陣估計(jì)算子，該算子的時(shí)間復(fù)雜度為O(n3)；LMaFit算法每次迭代都需要計(jì)算奇異值分解，奇異值分解的時(shí)間復(fù)雜度為O(n3)；TRPCA 算法存在張量核范數(shù)的運(yùn)算，張量核范數(shù)的時(shí)間復(fù)雜度O(n3)。第二，NSTI采用了牛頓法與軟閾值迭代法提高計(jì)算速度，NSTI每次迭代時(shí)間復(fù)雜度為O(n2)。

表3 不同算法圖像恢復(fù)性能對(duì)比Tab.3 Comparison of image restoration performance of different algorithms

4 結(jié)語

本文研究了RPCA 問題，利用牛頓法和軟閾值迭代法改進(jìn)了RPCA模型，并提出了NSTI算法。經(jīng)實(shí)驗(yàn)證明，本文提出的NSTI算法，與其他RPCA算法相比，在時(shí)間效率與算法精確度上有明顯提升。本文提出的軟閾值估計(jì)算子能夠計(jì)算出一個(gè)動(dòng)態(tài)且精確的軟閾值，能夠提高NSTI算法的收斂速度和精確度。NSTI算法也存在著不足，像GD 算法一樣，參數(shù)中需要輸入低秩r，來決定低秩矩陣的秩r，而沒辦法在算法中直接估計(jì)出r的大小。