恢復(fù)部分支集已知的稀疏信號(hào)

王會(huì)敏

(紹興文理學(xué)院　數(shù)學(xué)系，浙江　紹興312000)

?

恢復(fù)部分支集已知的稀疏信號(hào)

王會(huì)敏

(紹興文理學(xué)院數(shù)學(xué)系，浙江紹興312000)

摘要：討論如何從少量線性測(cè)量中恢復(fù)部分支集信息已知的稀疏信號(hào)的問題.所用方法是凸優(yōu)化方法，所用范數(shù)為關(guān)于已知支集的余集上的l1范數(shù).文章討論了支集信息不完全準(zhǔn)確的情形，給出了保證信號(hào)穩(wěn)定恢復(fù)的限制等距常數(shù)界.

關(guān)鍵詞：壓縮感知；l1范數(shù)最小化；限制等距常數(shù)

引言

壓縮感知是一個(gè)最近出現(xiàn)的熱門領(lǐng)域，主要目標(biāo)是從少量的線性測(cè)量中恢復(fù)稀疏信號(hào).因?yàn)樵诤芏鄳?yīng)用問題中，要恢復(fù)的信號(hào)都是稀疏的或者漸進(jìn)稀疏的，壓縮感知的潛在應(yīng)用前景非常廣.

min‖x‖0，s.t.y=Φx

(1)

恢復(fù)x.

min‖x‖1，s.t.y=Φx

(2)

Candes，Romberg和Tao[2]表明通過選擇合適的測(cè)量矩陣，只要測(cè)量次數(shù)m>Cklog(n/k)，則通過求解l1范數(shù)最小化問題可以穩(wěn)定恢復(fù)k-稀疏信號(hào).注意到這里討論的恢復(fù)方法并沒有用到信號(hào)的一些先驗(yàn)信息.

在實(shí)際的應(yīng)用中，要恢復(fù)的稀疏信號(hào)往往有一些先驗(yàn)信息，比如信號(hào)的部分支集已知，或者信號(hào)的最大分量的估計(jì)等可以用來改善信號(hào)恢復(fù)的表現(xiàn).比如，視頻信號(hào)往往會(huì)表現(xiàn)出相鄰框架上的相關(guān)性.考慮一個(gè)壓縮信號(hào)x∈Rn，如果x表示一個(gè)圖像的離散cosine變換或者小波變換的稀疏化，則x對(duì)應(yīng)于低頻子帶的分量最可能是非零的，并且負(fù)荷了信號(hào)的大部分能量.這樣的情形下，當(dāng)x被壓縮采樣時(shí)，在恢復(fù)算法中考慮這些信息，是有助于恢復(fù)的.例如，Garcis-Frias和 Esnaola[3]表明如果一個(gè)信號(hào)是一個(gè)隨機(jī)過程的實(shí)現(xiàn)，統(tǒng)計(jì)先驗(yàn)信息有助于改進(jìn)信號(hào)恢復(fù)的質(zhì)量.Elad和Aharon[4]討論了圖像的稀疏和冗余表示，定義了全局信號(hào)的先驗(yàn)信息，強(qiáng)迫導(dǎo)致片段上的稀疏性來發(fā)展一種圖像去噪的方法.Weizman等討論了采用迭代加權(quán)方法，利用先驗(yàn)信息恢復(fù)MRI圖像的問題[5].

本文考慮部分支集信息已知的信號(hào)恢復(fù)，已知的支集信息不一定完全準(zhǔn)確，可能有一定誤差.

1數(shù)學(xué)模型

令x0∈Rn是要恢復(fù)的信號(hào)，T0∈suppx0.假定部分支集估計(jì)T?{1，...，n}，則一個(gè)可能的構(gòu)造方法是

x*=argmin‖x‖1，w，s.t.y=Φx

(3)

min‖x‖1，w，s.t.‖y-Φx‖ε

(4)

C.Miosso等在[6]中提出了一個(gè)基于迭代加權(quán)最小二乘算法的加權(quán)策略來處理已知支集的先驗(yàn)信息.數(shù)值結(jié)果表明先驗(yàn)信息的使用會(huì)使得需要的測(cè)量次數(shù)下降.Vaswani等在[7]中研究了迭代重構(gòu)稀疏信號(hào)序列的問題，其中將上一次試驗(yàn)得到的支集估計(jì)作為下一次的已知支集信息.他們得到了準(zhǔn)確重構(gòu)的充分條件.本文考慮了得到的支集信息不準(zhǔn)確的情形，并用限制等距常數(shù)刻劃了穩(wěn)定恢復(fù)的條件.

2限制等距常數(shù)

下面介紹限制等距常數(shù)的概念.

定義1令Φ∈Rm×n是給定矩陣.對(duì)滿足1km的任意正整數(shù)k，定義Φ的k階限制等距常數(shù)是滿足下列條件的最小的正數(shù)δk∈(0，1)，

對(duì)所有k-稀疏信號(hào)x∈Rn成立.顯然，當(dāng)kk'時(shí)，δkδk'，.

下面介紹一個(gè)限制正則常數(shù)的概念.

定義2令X，X'∈Rm×n，滿足R(X)r，R(X')r'，并且〈X，X'〉=0，r，r'-階限制正則常數(shù)θr，r'是滿足下列條件的最小正數(shù)

在[8]中，研究者提供了下面的不等式

θr，r'θr1，r1'，如果rr'，r1r1'，

θr，r'δr+r'θr1，r1'+max(δr，δr')

3主要結(jié)果及證明

則(*)式的解x*滿足

‖x*-x0‖2

對(duì)于任意正整數(shù)r和ri，1il，有

特別，對(duì)于任意a≥1和正整數(shù)r和r'，使ar'是正整數(shù)，則

θr，ar'.

δ2k

令x*=x0+h是(*)式的解，則應(yīng)用與[9]中類似的表示，可以得到

‖hc‖1

分解hi=hi1+hi2，i=1，...，l，這里hi1是hi中前b-a個(gè)最大系數(shù)的分量構(gòu)成的向量.有

‖h1‖2，

‖h2‖2，...，‖hi‖2，...，則

注意到x*和x都是可行解，因此有‖Φh‖2ε.根據(jù)限制等距性質(zhì)有

〈Φh，Φ(h0+h*)〉

〈Φh，Φ(h0+h*)〉

另一方面，由于

〈Φh，Φ(h0+h*)〉‖Φh‖2‖Φ(h0+h*)‖2，

有

‖h‖2).

證畢.

參考文獻(xiàn):

[1]E J Candes. Compressed sampling[J].In International Congress of Mathematics，2006， 3:1433-1452.

[2]E J Candes，J Romberg，T Tao.Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J].IEEE.Trans.Inform.Theory，2006，52(2):489-509.

[3]J G Frias，I Esnaola.Exploiting prior knowledge in the recovery of signals from noisy random projections[J].In Data Compression Conference， 2007：333-342.

[4]M Elad，M Aharon.Image denoising via sparse and redundant representations over learned dictionaries[J].IEEE.Trans.Image.Process，2006，15：3726-3745.

[5]L Weizman，Y Eldar，D Bashat.Compressed sensing for longitudinal MRI: An adaptive-weighted approach[J].Medical Physics， 2015， 42(9):5195-5208.

[6]C J Miosso，R von Barries，M Argaez，et al.Compressive sensing reconstruction with prior information by iteratively reweighted least squares[J].IEEE.Trans.Sig.Proc，2010，57(6):2424-2431.

[7]N Vaswani.Least squares CS-residual(LS-CS):Compressive sensing on Least squares residual[J].IEEE.Trans.Sig.Proc，2010：58.

[8]T Tony Cai，Lie Wang，Guangwu Xu.Shifting inequality and recovery of sparse signals[J].IEEE Transactions on signal processing，2010，58(3):1300-1308.

[9]M P Friedlander，H Mansour，R Saab, et al.Recovering compressively sampled signals using partial support information[J].IEEE.Trans.Info.Theory,2012，58(2):1122-1134.

(責(zé)任編輯魯越青)

Recovering Sparse Signals with Partial Support Information

Wang Huimin

(Department of Mathematics, Shaoxing University, Shaoxing, Zhejiang 312000)

Abstract：In this paper, we consider recovering sparse signals with prior support information. We assume that the positions of some nonzero elements have been known. We propose a weighted optimized approach and derive the sufficient condition to guarantee a successful recovery.

Key words：matrix completion; nuclear norm minimization; singular value decomposition

收稿日期：2016-03-10基金項(xiàng)目：浙江省自然科學(xué)基金青年基金項(xiàng)目(LQ14A010005)，浙江省教育廳科研項(xiàng)目(Y201328557).

作者簡(jiǎn)介：王會(huì)敏(1980-)，女， 河南安陽人，博士，講師，主要研究方向：壓縮感知與低秩矩陣恢復(fù).

doi：10.16169/j.issn.1008-293x.k.2016.07.07

中圖分類號(hào)：C25

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1008-293X(2016)07-0035-04