l1-pca算法的比較與改進

l1-pca算法的比較與改進

1基于輔助方法的解析計算公式和局部最優(yōu)解隨著技術(shù)的進步，許多應(yīng)用的數(shù)據(jù)顯示出維度特征。維數(shù)的增長給數(shù)據(jù)分析帶來了巨大的挑戰(zhàn)。通過降噪提取數(shù)據(jù)中重要的特征來降低高維數(shù)據(jù)的維數(shù)引起人們的重視。近些年來,國內(nèi)外很多學(xué)者對此問題進行了大量的研究,提出了很多算法為了解決這個問題并優(yōu)化算法,文獻[3]提出基于L1范數(shù)協(xié)方差估計的方法;文獻[4]提出利用半正定規(guī)劃問題來優(yōu)化L1范數(shù)的方法;文獻[5]提出聯(lián)合L2范數(shù)和L1范數(shù)來提取健壯子空間特征的方法;文獻[6]提出基于核函數(shù)的L1-PCA算法;文獻[7]提出利用信息熵來調(diào)節(jié)重建誤差權(quán)值的PCA算法。但是上述算法都存在2個問題:(1)存在很多局部最優(yōu)解。(2)這些算法通常是通過降低矩陣的秩實現(xiàn)降維,然而在數(shù)值計算中,矩陣的秩計算復(fù)雜。文獻[8-9]提出用跡范數(shù)代替矩陣的秩,并從理論上證明了在滿足一定條件下,跡范數(shù)代替矩陣的秩是可行的。受此啟發(fā),本文提出一種基于跡范數(shù)的L1-PCA算法,針對算法優(yōu)化問題提出了基于增強拉格朗日乘子的方法,并將算法應(yīng)用于Yale人臉數(shù)據(jù)集和bin-alpha數(shù)據(jù)集進行數(shù)據(jù)降噪處理。2fg保護方式傳統(tǒng)的PCA通常是利用矩陣的秩來實現(xiàn)數(shù)據(jù)降維。假設(shè)給定數(shù)據(jù)矩陣X={x其中,矩陣F和矩陣G的優(yōu)化解為:其中,A式(3)的‖A然而基于L1范數(shù)的PCA存在很多局部最優(yōu)解的問題。為此,令式(3)中FG近似等于XZ,即FG≡XZ,式(3)近似等價為:其中,k<<p,k<<n且rank(FG)=rank(XZ)。從式(4)可以看出rank(XZ)=min(rank(X),rank(Z)),因此,可以推出rank(Z)=k。然而,秩約束存在很多局部最優(yōu)解的問題。文獻[10]提出利用跡范數(shù)近似代替秩,而跡范數(shù)是凸問題,并且可以求得唯一最優(yōu)解。遵循這種思想,本文利用跡范數(shù)‖Z‖式(5)可近似等價為:跡范數(shù)‖Z‖其中,uf0733拉格朗日乘子法對于式(6)的求解問題,本文采用基于增強拉格朗日乘子的優(yōu)化方法。在式(6)中,令U=X-XZ,V=Z,式(6)可以等價為:針對式(7)的求解問題,本文采用增強拉格朗日乘子(AugmentedLagrangeMultiplier,ALM)其中,A、B是拉格朗日乘子;λ是懲罰因子;〈M,N〉定義為ALM是一種迭代更新算法,在迭代更新過程中需要給出問題求解過程和相關(guān)參數(shù)的迭代方法。3.1求解過程中型對于輸入A、B和λ,算法的關(guān)鍵就是解決式(8)的最優(yōu)解問題。這個問題可以通過U、V和Z閉合形式解決:(1)算法固定(V,Z)來求解U,式(8)可以等價為:式(9)可以等價為:式(10)閉合形式解的求解過程如下:令Q=X-XZ(10)B/λ,式(11)等價為:式(11)的問題可以分解為p個子問題:根據(jù)文獻[12],式(12)的解為:其中,其中,Q=X-XZ(10)B/λ。(2)算法固定(U,Z)來求解V。式(8)可寫成:式(13)可以等價為:式(14)可通過奇異值分解(SingularValueDecomposition,SVD)獲得,即:其中,P=(p其中,矩陣S(3)算法固定(U,V)來求解Z,式(8)可以等價為:令3.2參數(shù)迭代方法在增強拉格朗日乘子迭代過程中,每次迭代得到U、V和Z,其中,參數(shù)A、B和λ的迭代方法如下:其中,ρ是一個常量,并且ρ>1。從式(8)可以看出,公式不僅使用拉格朗日乘子A和B來約束U和V,而且還增加了2項懲罰項3.3算法的基本思想本文算法框架如下:輸入X輸出U、V、Z初始化:A=0,B=0,ρ=1.2從算法框架和式(16)可出看出,在優(yōu)化迭代過程中,λ的值越來越大,但是λ不能無限大,因此,在所提出的算法框架中λ的取值為min(λr,10算法的輸入?yún)?shù)為原始矩陣X,需要初始化的參數(shù)包括增強拉格朗日乘子的迭代參數(shù)A、B、λ以及限制迭代次數(shù)的參數(shù)r和Z的初始估計值(后續(xù)的實驗將其估計為0.9X)。算法首先初始化相應(yīng)的參數(shù)值,然后開始迭代計算U、V和Z的值,并更新參數(shù)A、B、λ的值,當(dāng)滿足收斂條件min(λr,10算法的時間復(fù)雜度主要由求解U、V、Z和迭代系數(shù)決定。其中,求解U利用了閉合形式解,而求解閉合形式解的時間復(fù)雜度為O(pn);求解V利用了奇異值分解,而奇異值分解的時間復(fù)雜度為O(min(p4噪聲隨機噪聲的變化為了評價所提出的基于跡范數(shù)的L1-PCA及其求解算法的有效性,將本文算法應(yīng)用于Yale人臉數(shù)據(jù)集和binalpha數(shù)據(jù)集進行圖像降噪處理。首先從Yale人臉數(shù)據(jù)選出部分圖像,并將圖像大小調(diào)整為32×32像素。為了評估所提算法的有效性,對每個圖像增加隨機噪聲,隨機噪聲的增加,對圖像設(shè)置方形遮擋。假如方形遮擋的尺寸設(shè)為d,遮擋數(shù)量設(shè)為m,對每個圖像隨機選取m個位置,將其d×d像素部分的值設(shè)為0。圖1顯示了設(shè)置4種不同遮擋增加隨機噪聲的例子,即增加隨機噪聲的圖像。圖2(a)~圖2(c)顯示了3組Yale人臉數(shù)據(jù)集的圖像在隨機增加了10塊3×3遮擋圖像的情況下,應(yīng)用PCA算法和本文算法降噪效果對比分析。圖2(a)~圖2(c)的第1行是增加了隨機噪聲的圖像;第2行是利用PCA算法的降噪效果;第3行是利用本文提出的算法降噪的效果。從圖2(a)~圖2(c)可以看出,本文算法降噪效果明顯、圖像特征更加清晰。將本文算法應(yīng)用于bin-alpha數(shù)據(jù)集進行降噪處理,每張圖像大小調(diào)整為20×16像素,部分結(jié)果如圖3所示。從圖3(b)中可以看出,字母和數(shù)字的輪廓清晰、同類圖像特征也明顯趨同。5跡范數(shù)的l1-