何希平,楊 勁,劉 波
(1.重慶工商大學(xué) 電子商務(wù)及供應(yīng)鏈系統(tǒng)重慶市重點(diǎn)實(shí)驗(yàn)室,重慶400067;2.重慶工商大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院,重慶400067;3.重慶工商大學(xué) 重慶市檢測(cè)檢測(cè)控制集成系統(tǒng)工程實(shí)驗(yàn)室,重慶400067)
對(duì)大規(guī)模數(shù)據(jù)的統(tǒng)計(jì)分析、稀疏低秩近似[1,2]、降維表達(dá)[3]與壓縮感知等處理,是目前深受研究人員青睞的技術(shù)和方法。線性運(yùn)算的高時(shí)效性使得如何有效地刻畫研究對(duì)象之間局部或整體的近似線性關(guān)系成為數(shù)據(jù)分析過(guò)程中倍受重視并起著決定性作用的理論與技術(shù)問(wèn)題。矩陣低秩逼近[4-8]由于其簡(jiǎn)潔性,已成為數(shù)據(jù)處理的基本手段之一。
在高維數(shù)據(jù)處理中,高維數(shù)據(jù)的相關(guān)性不容忽視,正是由于奇異值向量直接反映矩陣秩的大小,即矩陣中行或列向量的相關(guān)度,使得基于高維數(shù)據(jù)矩陣的奇異值分解(singular value decomposition,SVD)成為了信號(hào)主成分分析、高維數(shù)據(jù)降維、線性判別分析、稀疏表示、矩陣低秩分解等應(yīng)用的重要技術(shù)手段。用奇異值分解技術(shù)實(shí)現(xiàn)信號(hào)降噪[9-11]即為線性近似的代表應(yīng)用之一。
本文重點(diǎn)研究信號(hào)SVD重建的通用技術(shù),其預(yù)期的主要目標(biāo)包括:①構(gòu)建信號(hào)基于SVD分解的低秩線性表達(dá)與重建的通用模型;②研究并實(shí)驗(yàn)一維信號(hào)的強(qiáng)相關(guān)結(jié)構(gòu)矩陣的構(gòu)建與SVD線性化表達(dá)模型;③通過(guò)含噪聲的一維數(shù)字信號(hào)和二維數(shù)字圖像的低秩近似與去噪聲實(shí)驗(yàn)展示模型的適應(yīng)性。
設(shè)X= (x1,…,xn)∈Rm×n為m 個(gè)n維信號(hào)的抽樣矩陣,M為X的列均值矩陣,X的中心化信號(hào)矩陣Y=X
對(duì)信號(hào)X的SVD分解可轉(zhuǎn)化為對(duì)Y的分解。
定理 設(shè)Y∈Rm×n為X的中心化信號(hào)矩陣,秩為r,則必存在正交矩陣U= (u1,…,um)∈Rm×m和正交矩陣V=(v1,…,vn)∈Rn×n,使得
稱式 (1)為矩陣Y的奇異值分解 (簡(jiǎn)記為SVD),σi稱為Y的奇異值。由式 (2)和式 (3)可見(jiàn),YTY為X的協(xié)方差矩陣的m-1倍,且YTY的非零特征值σ2i的對(duì)應(yīng)特征向量為vi,YYT的非零特征值σ2i的對(duì)應(yīng)特征向量為ui(i=1,…,r),從而Y的SVD分解可通過(guò)對(duì)YTY和YYT進(jìn)行特征分解實(shí)現(xiàn)。u1,…,um構(gòu)成Rm空間的一組規(guī)范正交基,v1,…,vn構(gòu)成Rn空間的一組規(guī)范正交基。
從中心化信號(hào)矩陣Y的奇異值分解式 (1)可以得到精確重建X的一些非常有用的信息
其中
式 (7)為X的低秩重建近似信號(hào),式 (6)給出的是一個(gè)非凸優(yōu)化模型,求解困難。借助拉格朗日乘數(shù)法,可以將秩不超過(guò)X的秩r的約束轉(zhuǎn)化為在目標(biāo)函數(shù)中引入一個(gè)核范數(shù)的正則化項(xiàng)
則這一優(yōu)化問(wèn)題可以借助擬梯度分析獲得解的解析表達(dá)式[7]。而信號(hào)的恢復(fù)率η則可按式 (9)給出的基礎(chǔ)成分的系數(shù)向量Λ與滿秩奇異值分解的系數(shù)向量∑的相似性度量進(jìn)行近似估算
顯然,1≥η≥0。當(dāng)Λ=∑時(shí),η=1,則可通過(guò)式 (7)獲得信號(hào)X的精確重建;否則,通過(guò)式 (8)的解析解抑制基礎(chǔ)成分Yi的系數(shù)λi的大小,控制對(duì)原始信號(hào)的近似表達(dá)程度;同時(shí)由于奇異值與信號(hào)方差的緊密關(guān)系,也可以通過(guò)抑制λi有效地抑制信號(hào)噪聲。
最常見(jiàn)的源信號(hào)是一維和二維信號(hào),這也是本文重點(diǎn)研究的對(duì)象。根據(jù)不同的目的,如去噪聲、稀疏表示、數(shù)據(jù)壓縮等,可以通過(guò)式 (8)選擇不同的線性系數(shù)來(lái)組合原始信號(hào)的SVD基礎(chǔ)成分,進(jìn)而利用式 (7)完成對(duì)信號(hào)X的重建??梢?jiàn),重建算法的第一步應(yīng)該是構(gòu)建原始信號(hào)X的中心化信號(hào)矩陣Y,為利用式 (7)的信號(hào)重建模型,首先還必須把一維信號(hào)向量變換成對(duì)應(yīng)的結(jié)構(gòu)矩陣。利用一維信號(hào)可以構(gòu)造出很多種矩陣,如Hankel矩陣、Toeplitz矩陣、Circulant矩陣等。研究實(shí)踐結(jié)果表明,矩陣構(gòu)造方式不同,則SVD的信號(hào)處理效果就會(huì)不一樣。
信號(hào)重建的重要依據(jù)之一就是相鄰信號(hào)時(shí)序的結(jié)構(gòu)相關(guān)性,因此,重建一維信號(hào)也可通過(guò)構(gòu)建一維數(shù)字信號(hào)時(shí)序的鄰域相關(guān)結(jié)構(gòu)矩陣,再利用結(jié)構(gòu)矩陣的SVD低秩逼近模型實(shí)現(xiàn)重建。
設(shè)一維離散數(shù)字信號(hào)的時(shí)序x= (x1,…,xm)T∈Rm,則可以利用此信號(hào)構(gòu)造如下的Hankel矩陣X (各行時(shí)序間或者列時(shí)序間依次超前一個(gè)時(shí)間步長(zhǎng))
則X的第一列和最后一行 (或第一行和最后一列)元素構(gòu)成原離散數(shù)字信號(hào)x。Hankel矩陣X的相鄰元素較好地反應(yīng)了信號(hào)時(shí)序的相鄰相關(guān)的特點(diǎn)。
也可用一維離散數(shù)字信號(hào)x構(gòu)造Toeplitz矩陣X (同一條對(duì)角線上的元素相同)
則X的第一列和第一行元素構(gòu)成離散數(shù)字信號(hào)的時(shí)間序列x。
而式 (12)表示的信號(hào)x的Circulant矩陣完全由它的第一列即x(或第一行即x′)確定,其余各列均為其前一列元素順時(shí)針 (或逆時(shí)針)循環(huán)移一位得到,即以上一列第二 (或最后)元素為首元素依序循環(huán)排列 (相當(dāng)于上一時(shí)序循環(huán)提前或延遲一個(gè)時(shí)間步長(zhǎng))
對(duì)于一維離散數(shù)字信號(hào)x,有了結(jié)構(gòu)矩陣X以后,就可通過(guò)式 (1)~式 (4)計(jì)算結(jié)構(gòu)矩陣X的中心化信號(hào)矩陣Y的SVD分解和基礎(chǔ)成分。由式 (4)~式 (8)不難發(fā)現(xiàn),X的重建信號(hào)是Y的SVD基礎(chǔ)成分Yi的線性組合。若分別記Yi中的、與所構(gòu)造的結(jié)構(gòu)矩陣X中構(gòu)成信號(hào)時(shí)序x的列和行對(duì)應(yīng)的列和行向量 (行向量不含第一元素)為pi和qi,并記則x的重建信號(hào)可表示為
式中:μ——由結(jié)構(gòu)矩陣X的列均值構(gòu)成的與x同維度的向量。實(shí)際應(yīng)用中,μ可直接取x的均值構(gòu)成。
直觀觀察可見(jiàn),在式 (10)~式 (12)表示的3種結(jié)構(gòu)矩陣中,Hankel矩陣元素的相鄰相關(guān)性最強(qiáng),Toeplitz矩陣次之,Circulant矩陣元素的相鄰相關(guān)性相對(duì)較弱。使用Hankel矩陣與Toeplitz矩陣的計(jì)算復(fù)雜性與參數(shù)k的選取有密切關(guān)系,k越小,SVD計(jì)算復(fù)雜性越低;反之,復(fù)雜性越高。當(dāng)信號(hào)時(shí)序較長(zhǎng)時(shí),Circulant矩陣的階數(shù)較大,SVD的計(jì)算復(fù)雜度呈指數(shù)級(jí)增長(zhǎng),效率較低。
根據(jù)前面分析,重建算法的具體步驟如下:
(1)由信號(hào)矩陣X求得中心化矩陣Y;
(2)對(duì)中心化矩陣Y進(jìn)行SVD分解,得到奇異值向量∑和Y的基礎(chǔ)成分Y1,…,Yr;
(3)求解優(yōu)化模型 (8),得到Λ= (λ1,…,λr)T;
(4)根據(jù)式 (7)計(jì)算重建近似信號(hào)。
在重建模型求解過(guò)程中,重要的是對(duì)優(yōu)化模型 (8)中的Λ= (λ1,…,λr)T的選擇。針對(duì)不同應(yīng)用可選擇不同的信號(hào)恢復(fù)率η0,并在恢復(fù)率η0的控制下,基于主成分表達(dá)的思想,使用貪心法首先選取一個(gè)非零的λi,使得僅由基礎(chǔ)成分Yi重建的X的恢復(fù)率η最接近η0,且η0≥η,并令λk=0 (k<i);然后再選取下一個(gè)非零的λj(i<j),使得由基礎(chǔ)成分Yi和Yj重建的X的恢復(fù)率η最接近η0,且η0≥η,并令λk=0 (i<k<j);如此繼續(xù)選取下一Yj。在η還未接近η0的大小時(shí),均可取λj=σj,以便算法快速收斂,同時(shí)使Λ取值表現(xiàn)出稀疏特性。
利用SVD分解模型 (4)和重建模型 (7),可以對(duì)信號(hào)進(jìn)行主成分分析,或者利用基礎(chǔ)成分對(duì)信號(hào)進(jìn)行近似或者稀疏壓縮表示 (選取較少的幾個(gè)基礎(chǔ)成分近似表示原信號(hào)),或者消除信號(hào)噪聲等。
對(duì)一維數(shù)字信號(hào)去噪,一般考慮如下加性白噪聲模型
其中,ni~N(0,σ2)(i=1,2,…,m)為獨(dú)立同分布的高斯白噪聲。
由式 (1)、式 (2)、式 (4)可見(jiàn),信號(hào)SVD分解模型實(shí)質(zhì)上是對(duì)信號(hào)矩陣左右兩邊各乘以一個(gè)正交矩陣而得到信號(hào)的奇異值矩陣,而作為其逆變換的信號(hào)重建過(guò)程正好是以奇異值為所求基礎(chǔ)成分的權(quán)的線性表出過(guò)程,從而噪聲在變換過(guò)程中保持可加性未變,并且噪聲通常表現(xiàn)為高頻尖峰數(shù)據(jù),因此在去噪聲應(yīng)用中,可以利用軟硬閾值模型[12]作用于奇異值向量∑,求得重建模型 (7)中的基礎(chǔ)成分的系數(shù)向量Λ,進(jìn)而恢復(fù)原始信號(hào)。
去噪聲的過(guò)程實(shí)質(zhì)上就是選擇一種誤差度量模型,通常是均方誤差 (MSE)
尋求與含噪信號(hào)x以MSE最小為目標(biāo)的原始信號(hào)x0的估計(jì)
在SVD去噪中,x是根據(jù)式 (13)表示的模型得到的結(jié)果。
由于圖像噪聲與一維信號(hào)相似,更常見(jiàn)的也是加性高斯白噪聲,而在SVD重建模型中,二維圖像即構(gòu)成了信號(hào)矩陣X,所以,可以直接在類似于式 (16)的MSE最小化的優(yōu)化目標(biāo)模型控制下,利用SVD重建算法實(shí)現(xiàn)圖像去噪聲,也可以對(duì)圖像進(jìn)行分塊,然后通過(guò)分塊線性近似實(shí)現(xiàn)。
基于主成分分析和貪心算法的思想,可以按式 (9)表示的恢復(fù)率計(jì)算模型,根據(jù)稀疏度要求按從前至后的順序選擇基礎(chǔ)成分及其對(duì)應(yīng)奇異值,而舍棄后面重要性相對(duì)較低的成分,可以有效實(shí)現(xiàn)信號(hào)的稀疏k近似表示
其中
借助式 (17)的模型,可以簡(jiǎn)便地實(shí)現(xiàn)對(duì)原始信號(hào)進(jìn)行壓縮與稀疏表示。事實(shí)上,由于k個(gè)基礎(chǔ)成分 (通常k<<r)僅需要由k對(duì)ui、vi生成,所以信號(hào)存儲(chǔ)要求由o(mn)降低為o(k(m+n)),可以大幅壓縮信號(hào)的存儲(chǔ)量,實(shí)現(xiàn)信號(hào)的稀疏近似表示。
對(duì)一維信號(hào)去噪聲,我們選擇了長(zhǎng)度為2048的Heavy sine離散數(shù)字信號(hào)作為原始信號(hào),并按式 (14)添加了高斯噪聲,且取σ=1.5。
在具體算法中,我們對(duì)Λ的選取采用的一種策略是如下主成分選取模型
為進(jìn)一步分析結(jié)構(gòu)矩陣的特性,我們對(duì)同一信號(hào)的3種結(jié)構(gòu)矩陣SVD低秩重建結(jié)果做了統(tǒng)計(jì)計(jì)算,并與小波軟閾值自動(dòng)去噪結(jié)果進(jìn)行對(duì)比,結(jié)果見(jiàn)表1,其信號(hào)處理直觀對(duì)比如圖1所示。
表1 一維信號(hào)去噪結(jié)果的統(tǒng)計(jì)對(duì)比
其中小波變換選取的是5層sym8,閾值選取方法為SURE。從表中數(shù)據(jù)可見(jiàn):①Hankel矩陣、Toeplitz矩陣、Circulant矩陣分別表達(dá)信號(hào)矩陣時(shí),前兩種矩陣比第3種更有利于用SVD對(duì)信號(hào)進(jìn)行閾值去噪聲和近似表達(dá);②借助Hankel矩陣或者Toeplitz矩陣表達(dá)信號(hào)時(shí),通過(guò)對(duì)信號(hào)進(jìn)行SVD閾值去噪的效果明顯優(yōu)于小波閾值去噪的效果,且兩者通過(guò)SVD實(shí)現(xiàn)的效果非常相近;③由式 (9)表達(dá)的恢復(fù)率計(jì)算模型只能用于近似表達(dá)信號(hào)間的相似程度,可作為算法選擇時(shí)簡(jiǎn)化的近似計(jì)算依據(jù),但不能嚴(yán)格把它作為信號(hào)相似性好壞的判據(jù);④Circulant矩陣由于誤差偏大的原因,不適合于信號(hào)的SVD去噪與最佳近似表達(dá)應(yīng)用場(chǎng)合。
圖1 一維信號(hào)去噪效果對(duì)比
雖然去噪聲并非本文研究的最終目標(biāo),但是圖1所示的直觀效果表明對(duì)信號(hào)進(jìn)行SVD閾值去噪的效果明顯優(yōu)于小波閾值去噪的效果。另一方面,SVD閾值去噪的效果與閾值選擇和線性近似時(shí)系數(shù)調(diào)節(jié)算法也有關(guān)。實(shí)驗(yàn)中按式(19)進(jìn)行系數(shù)選擇,是一種比較粗略的處理方法,實(shí)用中可以在優(yōu)化模型 (16)的控制下動(dòng)態(tài)調(diào)節(jié)各系數(shù)以達(dá)到更加理想的效果。
為檢驗(yàn)SVD閾值去噪對(duì)二維圖像信號(hào)處理的效果,我們選擇了兩幅512×512的灰度圖像,均添加了均值為0、標(biāo)準(zhǔn)差為16的高期白噪聲,然后分別用小波軟閾值自適應(yīng)去噪與SVD閾值去噪進(jìn)行效果對(duì)比,直觀效果如圖2所示,而統(tǒng)計(jì)結(jié)果見(jiàn)表2。其中,與一維信號(hào)類似,對(duì)經(jīng)加高斯白噪聲的圖像選用sym8小波做3層小波分解,對(duì)所獲得的細(xì)節(jié)系數(shù)選用自適應(yīng)軟閾值小波收縮;而SVD閾值去噪聲時(shí)閾值為奇異值的均值。
圖2 圖像閾值去噪效果對(duì)比
表2 噪聲圖像閾值去噪結(jié)果對(duì)比
由表2所示的3種統(tǒng)計(jì)圖像特征不難發(fā)現(xiàn),盡管簡(jiǎn)化了系數(shù)優(yōu)化過(guò)程,使得SVD去噪算法中利用奇異值均值閾值對(duì)近似系數(shù)的選擇只是一種粗略估計(jì),然而SVD去噪效果也與自適應(yīng)軟閾值小波去噪聲結(jié)果非常接近,如果進(jìn)一步優(yōu)化SVD近似的逼近算法,提高去噪效果是必然的。
同時(shí),為了測(cè)試k近似壓縮表示的效果和優(yōu)化近似系數(shù)選擇的意義,我們對(duì)圖2中的兩幅加噪圖像在相似度模型 (17)的控制下,分別取η0=0.85、0.90和0.95的3種不同值時(shí),自適應(yīng)地選取了不同的k值,將對(duì)應(yīng)的重建結(jié)果與原始圖像、自適應(yīng)軟閾值小波去噪結(jié)果圖像進(jìn)行了統(tǒng)計(jì)與直觀對(duì)比。實(shí)驗(yàn)所得到的統(tǒng)計(jì)特征見(jiàn)表3,直觀對(duì)比效果如圖3所示。
表3 噪聲圖像k近似結(jié)果的統(tǒng)計(jì)特征對(duì)比
圖3 圖像k近似效果與小波去噪對(duì)比
由表3所示的圖像的3種統(tǒng)計(jì)特征不難發(fā)現(xiàn):①SVD逼近中,即使要求恢復(fù)率η0≥0.85,相對(duì)于奇異值個(gè)數(shù)來(lái)說(shuō),信號(hào)的k近似中的線性組合基礎(chǔ)成分?jǐn)?shù)k也比較小,說(shuō)明SVD線性組合模型對(duì)信號(hào)逼近與壓縮表示非常有效;②選擇恰當(dāng)?shù)幕謴?fù)率η0,不僅可以通過(guò)SVD低代價(jià)壓縮近似表示噪聲信號(hào),而且還可能達(dá)到比自適應(yīng)軟閾值小波去噪聲更好的信號(hào)處理效果;③表3第5行數(shù)據(jù)也說(shuō)明,當(dāng)一味追求過(guò)高的恢復(fù)率時(shí),不僅線性表達(dá)的代價(jià)會(huì)提高,而且消除噪聲的效果也會(huì)降低。
本文提出的基于信號(hào)矩陣的SVD分解的線性近似的優(yōu)化重建模型,就其本質(zhì)是對(duì)信號(hào)進(jìn)行相關(guān)性分析,尋求信號(hào)線性表達(dá)的低秩矩陣。文中所給出的數(shù)學(xué)模型不僅可以用于一維和二維信號(hào)去噪聲,而且可以用于信號(hào)的稀疏與壓縮表示,表達(dá)式簡(jiǎn)單易于計(jì)算;所給出的模型的SVD奇異值均值閾值去噪聲和k近似逼近算法的模型都簡(jiǎn)便易行。實(shí)驗(yàn)結(jié)果表明,新優(yōu)化重建模型對(duì)一維信號(hào)和二維圖像的噪聲抑制均能獲得很好的統(tǒng)計(jì)特征,可靠與穩(wěn)定性高,實(shí)用性強(qiáng)。
[1]Meng Deyu,Zhao Qian,Xu Zongben.Improve robustness of sparse PCA by L1-norm maximization [J].Pattern Recognition,2012,45 (1):487-497.
[2]Haipeng Shena,Jianhua Z Huang.Sparse principal component analysis via regularized low rank matrix approximation [J].Journal of Multivariate Analysis,2008,99 (6):1015-1034.
[3]David Nelson,Siamak Noorbaloochi.Information preserving sufficient summaries for dimension reduction [J].Journal of Multivariate Analysis,2013,115 (3):347-358.
[4]Ma S,Goldfarb D,Chen L.Fixed point and bregman iterative methods for matrix rank minimization [J]. Math Progra,2011,128 (1-2):321-353.
[5]Cai J F,Candès E J,Shen Z W.A singular value thresholding algorithm for matrix completion [J].SIAM J Optim,2010,20:1956-1982.
[6]RAO Guo,PENG Yi,XU Zongben.Robust sparse and lowrank matrix decomposition based on S1/2modeling [J].Science China Information Sciences,2013,43 (6):733-748 (in Chinese).[饒過(guò),彭毅,徐宗本.基于S1/2建模的穩(wěn)健稀疏-低秩矩陣 分 解 [J]. 中 國(guó) 科 學(xué): 信 息 科 學(xué),2013,43 (6):733-748.]
[7]ZHANG Zhenyue,ZHAO Keke.Regularization methods for low-rank factorization of matrices with missing data [J].Scientia Sinica Mathematica,2013,43 (3):249-271 (in Chinese).[張振躍,趙科科.數(shù)據(jù)缺損矩陣低秩分解的正則化方法 [J].中國(guó)科學(xué):數(shù)學(xué),2013,43 (3):249-271.]
[8]PENG Yigang,SUO Jinli,DAI Qionghai,et al.From compressed sensing to low-rank matrix recovery:Theory and applications [J].ACTA Automatica Sinica,2013,39 (7):981-994(in Chinese).[彭義剛,索津莉,戴瓊海,等.從壓縮傳感到低秩矩陣恢復(fù):理論與應(yīng)用 [J].自動(dòng)化學(xué)報(bào),2013,39(7):981-994.]
[9]HUANG Jianzhao,XIE Jian,LI Feng,et al.Com pound denoising method based on discrete stationary wavelet transform and optimized SVD [J].Piezoelectrics & Acoustooptics,2013,35 (3):448-451 (in Chinese). [黃建招,謝建,李鋒,等.基于優(yōu)化SVD和平穩(wěn)小波的復(fù)合降噪方法 [J].壓電與聲光,2013,35 (3):448-451.]
[10]CHEN Enli,ZHANG Xi,SHEN Yongjun,et al.Fault diagnosis of rolling bearings based on SVD denoising and blind signals separation [J].Journal of Vibration and Shock,2012,31 (23):185-190 (in Chinese). [陳恩利,張璽,申永軍,等.基于SVD降噪和盲信號(hào)分離的滾動(dòng)軸承故障診斷[J].振動(dòng)與沖擊,2012,31 (23):185-190.]
[11]ZHAO Xuezhi,YE Bangyan,CHEN Tongjian.Principle of singularity detection based on SVD and its application [J].Journal of Vibration and Shock,2008,27 (6):11-14 (in Chinese). [趙學(xué)智,葉邦彥,陳統(tǒng)堅(jiān).基于SVD的奇異性信號(hào)檢測(cè)原理及其應(yīng)用 [J].振動(dòng)與沖擊,2008,27 (6):11-14.]
[12]HE Xiping,YANG Jin.A novel type of threshold functions for wavelet shrinkage [J].Computer Engineering &Science,2013,35 (8):114-119 (in Chinese). [何希平,楊勁.一類新的小波收縮閾值函數(shù) [J].計(jì)算機(jī)工程與科學(xué),2013,35 (8):114-119.]