王會(huì)敏
(紹興文理學(xué)院 數(shù)學(xué)系,浙江 紹興312000)
?
恢復(fù)部分支集已知的稀疏信號(hào)
王會(huì)敏
(紹興文理學(xué)院數(shù)學(xué)系,浙江紹興312000)
摘要:討論如何從少量線性測(cè)量中恢復(fù)部分支集信息已知的稀疏信號(hào)的問(wèn)題.所用方法是凸優(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)用問(wèn)題中,要恢復(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]表明通過(guò)選擇合適的測(cè)量矩陣,只要測(cè)量次數(shù)m>Cklog(n/k),則通過(guò)求解l1范數(shù)最小化問(wèn)題可以穩(wěn)定恢復(fù)k-稀疏信號(hào).注意到這里討論的恢復(fù)方法并沒(méi)有用到信號(hào)的一些先驗(yàn)信息.
在實(shí)際的應(yīng)用中,要恢復(fù)的稀疏信號(hào)往往有一些先驗(yàn)信息,比如信號(hào)的部分支集已知,或者信號(hào)的最大分量的估計(jì)等可以用來(lái)改善信號(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ī)過(guò)程的實(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)致片段上的稀疏性來(lái)發(fā)展一種圖像去噪的方法.Weizman等討論了采用迭代加權(quán)方法,利用先驗(yàn)信息恢復(fù)MRI圖像的問(wèn)題[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)策略來(lái)處理已知支集的先驗(yàn)信息.數(shù)值結(jié)果表明先驗(yàn)信息的使用會(huì)使得需要的測(cè)量次數(shù)下降.Vaswani等在[7]中研究了迭代重構(gòu)稀疏信號(hào)序列的問(wèn)題,其中將上一次試驗(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-),女, 河南安陽(yáng)人,博士,講師,主要研究方向:壓縮感知與低秩矩陣恢復(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