低秩矩陣恢復(fù)的穩(wěn)定性和魯棒性

宋儒瑛,鄭 珂

(太原師范學(xué)院 數(shù)學(xué)系,山西 晉中 030619)

0 引言

無(wú)噪壓縮感知模型為y=Ax(其中A∈Cm×N,x∈CN),信號(hào)通過(guò)優(yōu)化模型

(P1)

進(jìn)行稀疏恢復(fù).對(duì)于恢復(fù)信號(hào)的誤差估計(jì)稱(chēng)為信號(hào)稀疏恢復(fù)的穩(wěn)定性[1].

有噪壓縮感知模型為y=Ax+e(其中e∈Cm),信號(hào)通過(guò)優(yōu)化模型

(P1,η)

進(jìn)行稀疏恢復(fù).對(duì)于恢復(fù)信號(hào)的誤差估計(jì)稱(chēng)為信號(hào)稀疏恢復(fù)的魯棒性[1].

隨著信息技術(shù)的快速發(fā)展,人們逐漸發(fā)現(xiàn)向量的信息量遠(yuǎn)不如矩陣的信息量大,隨機(jī)應(yīng)用壓縮感知技術(shù)恢復(fù)矩陣成為了新的研究方向.在對(duì)稀疏向量恢復(fù)和低秩矩陣恢復(fù)的研究中可知,低秩矩陣恢復(fù)問(wèn)題與稀疏向量恢復(fù)問(wèn)題是相對(duì)應(yīng)的.稀疏性是指向量中大部分元素為0,矩陣的低秩性是指矩陣的秩相對(duì)于矩陣的行數(shù)或列數(shù)而言很小.奇異值的個(gè)數(shù)等于矩陣的秩,如果對(duì)矩陣進(jìn)行奇異值分解后把其所有奇異值排列成向量,該向量的稀疏性便對(duì)應(yīng)于該矩陣的低秩性,所以低秩性可以看做是稀疏性在矩陣上的拓展.

從恢復(fù)低秩矩陣開(kāi)始,測(cè)量矩陣將由映射A:Cn1×n2→Cm取代,矩陣的非零奇異值取代向量的非零項(xiàng),壓縮感知理論也有了新的研究?jī)?nèi)容,文獻(xiàn)[2]介紹了低秩矩陣完整化問(wèn)題,文獻(xiàn)[3]解決了關(guān)于低秩矩陣恢復(fù)的Schatten p-擬范數(shù)極小化問(wèn)題,文獻(xiàn)[4]討論了低秩矩陣恢復(fù)的限制等距常數(shù)界的衰減性以及低秩矩陣無(wú)法進(jìn)行恢復(fù)時(shí)的限制等距常數(shù)的界,文獻(xiàn)[5]證明了Tony Cai和Anru Zhang的文章[6]中的猜想,同時(shí)還提出了關(guān)于用p最小化(0

(1)

(2)

1 低秩矩陣恢復(fù)的穩(wěn)定性

證明之前首先給出映射A的秩r穩(wěn)定零空間性質(zhì)定義以及相關(guān)引理輔助證明：

定義1[1，9]給定映射A:Cn1×n2→Cm并且令n=min{n1,n2},對(duì)于?M∈kerA{0}滿足以下不等關(guān)系

那么稱(chēng)映射A滿足秩r的穩(wěn)定零空間性質(zhì)并且常數(shù)0<ρ<1與矩陣秩r相關(guān).

為了便于標(biāo)記,可以用以下標(biāo)記[1]：

(X)1=Udiag(σ1(X),…,σr(X),0,…,0)V*

(X)2=Udiag(0,…,0,-σ1+r(X),…,-σn(X))V*

(Z)1=Udiag(σ1(Z),…,σr(Z),0,…,0)V*

(Z)2=Udiag(0,…,0,-σ1+r(Z),…,-σn(Z))V*

(X-Z)1=Udiag(σ1(X-Z),…,σr(X-Z),0,…,0)V*

(X-Z)2=Udiag(0,…,0,-σ1+r(X-Z),…,-σn(X-Z))V*

(3)

引理1給定秩為r的兩個(gè)矩陣X,Z∈Cn1×n2,映射A:Cn1×n2→Cm滿足

X-Z∈kerA{0},

并且矩陣可以分解為

X-Z=Udiag(σ1,…,σn)V*,

其中σ1≥…≥σn≥0,U∈Cn1×n1,V∈Cn2×n2都是酉矩陣,那么可以得出

‖(X-Z)2‖*≤‖Z‖*-‖X‖*+‖(X-Z)1‖*+2‖X1‖*.

證明：以上不等式經(jīng)過(guò)移項(xiàng)如下

‖(X-Z)2‖*+‖X‖*≤‖Z‖*+‖(X-Z)1‖*+2‖X1‖*.

(4)

從不等式的左邊‖X‖*開(kāi)始證明,首先結(jié)合(3)可得

(5)

接著證明‖(X-Z)2‖*可得

(6)

(5)與(6)相加可得

‖X‖*+‖(X-Z)2‖*≤2‖X2‖*+‖(X-Z)1‖*+‖Z‖*,

移項(xiàng)可得

‖(X-Z)2‖*≤2‖X2‖*+‖(X-Z)1‖*+‖Z‖*-‖X‖*.

接下來(lái)給出主要定理.

定理1假設(shè)映射A:Cn1×n2→Cm滿足秩r的穩(wěn)定零空間性質(zhì),并且常數(shù)0<ρ<1與秩r相關(guān),當(dāng)且僅當(dāng)對(duì)于?X,Z∈Cn1×n2以及A(X)=A(Z), 有以下不等式成立

(7)

證明：首先假設(shè)對(duì)于任意矩陣X,Z都有A(X)=A(Z),映射A滿足(7).由于?M∈kerA{0},可以令M:=X-Z∈kerA{0}.根據(jù)(3),可以令M1=X,M2=-Z,由此可得

(8)

將M,M1,M2帶入到(7)可得

移項(xiàng)重排可得

(1-ρ)(‖M1‖*+‖M2‖*)≤(1+ρ)(‖M2‖*-‖M1‖*),

經(jīng)過(guò)整理可得

‖M1‖*≤ρ‖M2‖*,

即

根據(jù)定義1可知映射A滿足秩r的穩(wěn)定零空間性質(zhì),并且常數(shù)0<ρ<1與秩r相關(guān).

接著反過(guò)來(lái)假設(shè)映射A:Cn1×n2→Cm滿足秩r的穩(wěn)定零空間性質(zhì)并且常數(shù)0<ρ<1與秩r相關(guān),即根據(jù)定義1可知對(duì)于?X,Z∈Cn1×n2滿足A(X)=A(Z),并且M:=X-Z∈kerA{0},M的奇異值滿足

(9)

再根據(jù)引理1可得

‖M2‖*≤2‖X2‖*+‖M1‖*+‖Z‖*-‖X‖*,

(10)

將(9)以及(10)結(jié)合可得

‖M2‖*≤2‖X2‖*+ρ‖M2‖*+‖Z‖*-‖X‖*,

由于ρ<1,移項(xiàng)可得

再次使用公式(9),可得

(11)

將M:=X-Z以及(3)帶入到(11)可得

定理1得證.

當(dāng)矩陣X∈Cn1×n2降維為向量x∈CN,此時(shí)恢復(fù)模型的范數(shù)變?yōu)?范數(shù),相應(yīng)的向量恢復(fù)定理的穩(wěn)定性分析見(jiàn)文獻(xiàn)[1].根據(jù)定理1可以得出無(wú)噪情形下低秩矩陣恢復(fù)的進(jìn)一步可以得出一個(gè)新結(jié)果如下：

定理2假設(shè)映射A:Cn1×n2→Cm滿足秩r的穩(wěn)定零空間性質(zhì),并且常數(shù)0<ρ<1與秩r相關(guān),那么對(duì)于X∈Cn1×n2,核范數(shù)極小化問(wèn)題(1)的最優(yōu)解X#與X之間的誤差估計(jì)為

證明：由于X#表示優(yōu)化問(wèn)題的最優(yōu)解,所以‖X#‖*≤‖X‖*,并且A(X#)=A(X),這樣Z=X#帶入到(7)中可得

定理2得證.

2 低秩矩陣恢復(fù)的魯棒性

首先給出映射A的秩r的魯棒零空間性質(zhì)定義：

定義2給定映射A:Cn1×n2→Cm并且令n=min{n1,n2},其中‖·‖表示Cm上的一個(gè)范數(shù).對(duì)于?M∈kerA{0}奇異值滿足以下不等關(guān)系

(12)

稱(chēng)映射A滿足秩r的魯棒零空間性質(zhì)(與‖·‖相關(guān))并且常數(shù)0<ρ<1以及τ>0都與矩陣秩r相關(guān).

接下來(lái)給出主要定理.

定理3假設(shè)映射A:Cn1×n2→Cm滿足秩r的魯棒零空間性質(zhì)(與‖·‖相關(guān))并且常數(shù)0<ρ<1以及τ>0都與矩陣秩r相關(guān),當(dāng)且僅當(dāng)對(duì)于?X,Z∈Cn1×n2,有以下不等式成立

(13)

證明：首先假設(shè)對(duì)于任意矩陣X,Z∈Cn1×n2,映射A滿足(13).給定矩陣M:=X-Z∈kerA{0},令M1=X,M2=-Z,根據(jù)(3)可知

將M,M1,M2帶入到(13)可得

經(jīng)過(guò)重新整理可得

(1-ρ)(‖M1‖*+‖M2‖*)≤(1+ρ)(‖M2‖*-‖M1‖*)+2τ‖A(M)‖,

化簡(jiǎn)后可得

‖M1‖*≤ρ‖M2‖*+τ‖A(M)‖.

根據(jù)公式(8)可知上式等價(jià)于(12) ,這便是秩r的魯棒零空間性質(zhì),其中的常數(shù)0<ρ<1,τ>0與秩r相關(guān).

接下來(lái)假設(shè)映射A滿足秩r的魯棒零空間性質(zhì),并且常數(shù)0<ρ<1,τ>0與秩r相關(guān).對(duì)于矩陣X,Z∈Cn1×n2,設(shè)M:=X-Z∈kerA{0},結(jié)合秩r的魯棒零空間性質(zhì)以及引理1,可以得出

‖M1‖*≤ρ‖M2‖*+τ‖A(M)‖,

‖M2‖*≤2‖X2‖*+‖M1‖*+‖Z‖*-‖X‖*,

將上述兩個(gè)式子相加可得

再次使用秩r的魯棒零空間性質(zhì),可以推導(dǎo)出

‖M‖*=‖M1‖*+‖M2‖*≤ρ‖M2‖*+τ‖A(M)‖+‖M2‖*

定理3得證.

當(dāng)矩陣X∈Cn1×n2降維為向量x∈CN,此時(shí)恢復(fù)模型的范數(shù)變?yōu)?范數(shù),相應(yīng)的向量恢復(fù)定理的魯棒性分析見(jiàn)文獻(xiàn)[1].接下來(lái)給出映射A的秩rFrobenius魯棒零空間性質(zhì)的定義.

定義3給定映射A:Cn1×n2→Cm并且令n=min{n1,n2},其中‖·‖表示Cm上的一個(gè)范數(shù).對(duì)于?M∈kerA{0}奇異值滿足以下不等關(guān)系

(14)

那么稱(chēng)映射A滿足秩rFrobenius魯棒零空間性質(zhì)(與‖·‖相關(guān)),并且常數(shù)0<ρ<1以及τ>0都與矩陣秩r相關(guān).矩陣Frobenius范數(shù)定義如下[1,9-10]：

故(14)可以記為

(15)

由此給出本節(jié)另一個(gè)主要定理如下：

定理4假設(shè)映射A:Cn1×n2→Cm滿足秩rFrobenius魯棒零空間性質(zhì)(與‖·‖相關(guān))并且常數(shù)0<ρ<1,τ>0與r相關(guān).那么對(duì)于?X,Z∈Cn1×n2,

其中C:=(1+ρ)2/(1-ρ),D:=(3+ρ)τ/(1-ρ).

證明：首先假設(shè)對(duì)于任意矩陣X,Z∈Cn1×n2,映射A:Cn1×n2→Cm滿足(15).令矩陣M:=X-Z∈kerA{0},M1=X,M2=-Z,根據(jù)(3)可知

將上式帶入到(15)可得

(16)

根據(jù)文獻(xiàn)[1]中命題2.3,文獻(xiàn)[9]中引理13或者文獻(xiàn)[10]中公式(2.1)得到

(17)

帶入到(16)可得

(18)

那么,類(lèi)似于(13)的證明結(jié)合(18)可得

(19)

接下來(lái),運(yùn)用(17)得到

繼續(xù)證明

鑒于(16)可以推導(dǎo)出

結(jié)合(19)可得出最后結(jié)果

由此進(jìn)一步可以得出一個(gè)新結(jié)果,如下：

定理5假設(shè)映射A:Cn1×n2→Cm滿足秩rFrobenius魯棒零空間性質(zhì)(與‖·‖=‖·‖2相關(guān)),并且常數(shù)0<ρ<1以及τ>0都與矩陣秩r相關(guān).那么對(duì)于X∈Cn1×n2,以及某個(gè)η≥0,假設(shè)y=A(X)+e并且‖e‖2≤η,二次約束核范數(shù)極小化問(wèn)題(2)的解X#與X的近似誤差為

對(duì)于常數(shù)C,D>0僅僅依賴于ρ和τ.

證明：二次約束核范數(shù)極小化問(wèn)題的最優(yōu)解為X#,所以‖X#‖*≤‖X‖*,根據(jù)定理4,將Z換成X#可得

這里‖A(X#-X)‖=‖A(Z)-y‖.由此可以得出

由優(yōu)化問(wèn)題噪聲誤差‖A(Z)-y‖≤η,可得

選取C:=2C可得

其中常數(shù)C,D>0僅僅依賴于ρ,τ,定理5得證.

3 結(jié)束語(yǔ)

本文內(nèi)容主要分為兩部分,第一部分是從充分性和必要性兩個(gè)角度證明了低秩矩陣恢復(fù)的穩(wěn)定性定理,第二部分首先針對(duì)不同矩陣范數(shù)定義了不同的魯棒零空間性質(zhì),并從充分性和必要性兩個(gè)角度證明得到了低秩矩陣恢復(fù)的魯棒性定理.證明于文獻(xiàn)[1]中對(duì)向量通過(guò)模型P1,P1,η進(jìn)行稀疏恢復(fù)的證明類(lèi)似.