基于稀疏補分析模型的近似最優(yōu)子空間追蹤

張宗念,李金徽,黃仁泰,閆敬文

(1.東莞理工學(xué)院電子工程學(xué)院,廣東東莞 523808;2.東莞理工學(xué)院網(wǎng)絡(luò)中心,廣東東莞 523808;3.東莞理工學(xué)院計算機學(xué)院,廣東東莞 523808;4.汕頭大學(xué)電子工程系,廣東汕頭 515063)

?

基于稀疏補分析模型的近似最優(yōu)子空間追蹤

張宗念1,李金徽2,黃仁泰3,閆敬文4

(1.東莞理工學(xué)院電子工程學(xué)院,廣東東莞 523808;2.東莞理工學(xué)院網(wǎng)絡(luò)中心,廣東東莞 523808;3.東莞理工學(xué)院計算機學(xué)院,廣東東莞 523808;4.汕頭大學(xué)電子工程系,廣東汕頭 515063)

為了從含噪聲的測量矢量中重構(gòu)原始信號,研究了稀疏補分析模型下近似最優(yōu)子空間追蹤信號重構(gòu)算法.針對直接采用稀疏綜合模型下子空間追蹤過程非最速梯度下降和信號重構(gòu)概率不高的缺點,根據(jù)稀疏補分析模型下不同類型分析字典的結(jié)構(gòu)特點來設(shè)計近似目標(biāo)優(yōu)化函數(shù)；改進了迭代追蹤過程；優(yōu)化了稀疏補取值方法；提出并實現(xiàn)了基于稀疏補分析模型的近似最優(yōu)分析子空間追蹤算法.仿真實驗證明,當(dāng)稀疏補運算符分別采用隨機緊支框架和二維全變分矩陣時,算法的完全重構(gòu)信號概率均明顯高于ASP、AHTP、AIHT、AL1、GAP算法的完全重構(gòu)信號概率；對于含高斯噪聲的輸入信號,算法的重構(gòu)信號綜合平均PSNR比相應(yīng)的ASP、AHTP、AIHT算法分別提高了0.8dB、1.38dB、3.13 dB,但比GAP和AL1算法降低了0.32 dB和0.6dB.算法的完全重構(gòu)概率與綜合重構(gòu)性能有了明顯提高,收斂充分條件得到進一步簡化.

稀疏補分析模型；近似最優(yōu)；子空間；追蹤

1 引言

近年來,對壓縮感知信號處理的研究一直十分活躍,其中一類約束優(yōu)化問題是:從一組含有噪聲的測量矢量y=Mx+e中重構(gòu)原始信號矢量x∈Rd,其中測量矩陣M∈Rm×d(通常m

近十年來,國內(nèi)外學(xué)者對稀疏綜合模型下信號重構(gòu)及其應(yīng)用進行了深入研究,也取得了一系列成果[2-7],但是對稀疏補分析模型下信號優(yōu)化研究還是近幾年的事情,目前國內(nèi)還沒有這方面的文獻報道.稀疏補分析模型下直接求解優(yōu)化方程是一個NP-hard問題,故只能求近似最優(yōu)解,方法有兩類:一是采用分析l1范數(shù)法[9-10](Analysisl1Norm,AL1),該算法的完全重構(gòu)概率很高、重構(gòu)性能很好,但是算法計算量巨大、收斂速度慢.二是采用各種貪婪追蹤策略,如:S.Nam在2013年提出貪婪分析追蹤算法(Greedyanalysispursuit,GAP)[11],從一個滿支撐集補開始追蹤,每一次迭代去掉其中的一個元素,直到迭代滿足終止條件為止,最后一次迭代的支撐集補就是最終解.此算法可以獲得與AL1相當(dāng)?shù)闹貥?gòu)性能,其不足之處是迭代需要遍歷整個支撐集、計算量大、收斂速度也慢.2011年R.Giryes提出分析迭代硬閾值算法(AnalysisIterativeHardThresholding,AIHT)[12]把稀疏綜合模型下的硬閾值跟蹤[13]直接搬到稀疏補分析模型中來,也取得了不錯的信號重構(gòu)效果,但是沒有考慮稀疏補分析模型下分析字典Ω和分析表示矢量Ωx的結(jié)構(gòu)特點等問題,雖然收斂速度大大加快,但重構(gòu)概率和重構(gòu)性能較差.2012年R.Giryes把稀疏綜合模型下硬閾值追蹤[14]思想與AIHT算法相結(jié)合提出了稀疏補分析模型下的分析硬閾值追蹤重構(gòu)算法(AHTP)[15],與前幾種算法相比,信號重構(gòu)性能和收斂速度都有一定提升,但是并沒有分析Ω的結(jié)構(gòu)特點對算法性能的影響及算法收斂的保證條件等.2012年R.Giryes把稀疏綜合模型下子空間追蹤[16-17]類推到稀疏補分析模型中,提出分析子空間追蹤(AnalysisSubspacePursuit,ASP)[18],與AIHT、AHTP做了對比,重構(gòu)性能有一定提高,并給出了保證算法收斂的充分條件、重構(gòu)誤差上界.本文在ASP的基礎(chǔ)上,根據(jù)不同分析字典的結(jié)構(gòu)特點用近似目標(biāo)優(yōu)化函數(shù)取代原目標(biāo)優(yōu)化函數(shù),改進了算法的迭代追蹤步驟,對稀疏補的取值方法進行優(yōu)化,提出了基于稀疏補分析模型的近似最優(yōu)分析子空間追蹤(ApproximateOptimalAnalysisSubspacePursuitbasedonCosparseAnalysisModel,AOASP),進一步提高了算法的完全重構(gòu)概率和重構(gòu)性能,并通過仿真實驗證實了算法可行性.

2 稀疏補分析模型

定理3 對于任意Λ∈Ll,當(dāng)且僅當(dāng)||QΛ((I-M*M)QΛ)||2≤δl時,矩陣M滿足Ω-RIP特性[15].

3 近似最優(yōu)分析子空間追蹤算法

3.1 AOASP算法介紹

步驟2,開始循環(huán)迭代i=i+1；

步驟6,擴充支撐集補Λi=cosupp(Ω,l)；

3.2 AOASP算法性能分析

3.2.1 算法穩(wěn)定重構(gòu)條件

i=|log(||x||2/||e||2)/log(1/τρ1ρ2)|,

C=1+((1-τρ1ρ2)i/(1-τρ1ρ2))(τ(η1+ρ1η2)

+2(1-δ2l-p)),

τ=(1+δ2l-p)/(1-δ2l-p),η1(i1+i2+i3),i1=(1+δ3l-2p)(γ(1+α)),i2=C2l-p(1+δ3l-2p)/(γ(1+γ)(1+α)),

α,

定理5 給定隨機矩陣M∈m×d,對于任意z∈d,常數(shù)CM>0,εl>0,如果成立,則δl≤εl將以大于1-e-t的概率成立.

對于Ω處于通用位置時,通常要求l

3.2.2 稀疏補l 選取方法

4 仿真實驗

實驗一,測試算法的完全重構(gòu)概率.稀疏補運算符Ω采用隨機緊支框架,測量矩陣M采用獨立同分布構(gòu)成的隨機矩陣.δ=m/d表示亞取樣率,ρ=(d-l)/m表示稀疏補與測量矢量數(shù)目的比值,也是Null(ΩΛ)的維數(shù)與測量數(shù)目的比值,ρ與δ的關(guān)系曲線稱為相位過渡圖.實驗中m和l分別取20組不同值,即對應(yīng)ρ和δ分別取不同的值,針對每一種取值組合,重復(fù)實驗40次,測試各算法完全重構(gòu)信號的概率.實驗結(jié)果見圖1,曲線下方表示對于ρ和δ不同取值,算法以100%的概率完全重構(gòu)信號的情形,上方表示不能完全重構(gòu)信號的情形.分析圖中曲線可知,AOASP算法的信號完全重構(gòu)概率明顯高于ASP、AHTP、AIHT、GAP和AL1五種算法的完全重構(gòu)概率.另外,曲線也說明了分析運算符Ω的冗余度越高,即Ω內(nèi)向量的線性相關(guān)性越強,重構(gòu)算法的性能越好.

實驗二,測試算法的完全重構(gòu)概率.稀疏補運算符Ω采用有限差分分析運算符ΩDIF,其它參數(shù)取值同實驗一.實驗結(jié)果仍然用相位過渡圖表示,見圖2.從圖中可以看出,AOASP的信號完全重構(gòu)概率明顯高于ASP、AHTP、AIHT的信號完全重構(gòu)概率.

5 結(jié)論

通過對壓縮感知信號優(yōu)化問題中的稀疏補分析模型理論的研究,針對直接采用稀疏綜合模型下子空間追蹤過程非最速梯度下降和信號重構(gòu)概率不高的缺點,引入稀疏補投影思想,根據(jù)稀疏補分析模型下分析字典的不同結(jié)構(gòu)特點來設(shè)計近似目標(biāo)優(yōu)化函數(shù),修正了迭代追蹤過程,優(yōu)化了稀疏補取值方法,設(shè)計并實現(xiàn)了基于稀疏補分析模型的近似最優(yōu)分析子空間追蹤算法,進一步提高了算法的完全重構(gòu)概率,提高了算法的信號重構(gòu)性能,通過仿真實驗證實了算法是可行的.如何選擇不同類型的分析字典Ω才能找到目標(biāo)函數(shù)的近似最優(yōu)解等需進一步研究.

[1]Elad M,Milanfar P,Rubinstein R.Analysis versus synthesis in signal priors[J].Inverse Problems,2007,23 (3):947-968.

[2]Candes E J,Eladar Y C,Needel D.Compressed sensing with coherent and redundant dictionaries[J].Applied and Computational Harmonic Analysis.2011,31 (1):59-73.

[3]Rauhut H,Schnass K,Vanderhheynest P.Compressed sensing and redundant dictionaries[J].IEEE Trans.Inf.Theory.2008,54 (5):2210-2219.

[4]Candes E J,Tao T.Near-optimal signal recovery from random projections:Universal encoding strategies?[J].IEEE Trans.On Inf.Theory,2006,52(12):5406-5425.

[5]張宗念,黃仁泰,閆敬文.壓縮感知盲稀疏度重構(gòu)算法[J].電子學(xué)報,2011,39(1):18-21.

Zhang Zong-nian,Huang Ren-tai,Yan Jing-wen.A Blind Sparsity Reconstruction Algorithm for Compressed Sensing Signal[J].Acta Electronica Sinica,2011,39(1):18-21.(in Chinese)

[6]練秋生,陳書貞.基于解析輪廓波變換的圖像稀疏表示及其在壓縮傳感中的應(yīng)用[J].電子學(xué)報,2010,38(6):1-6.

Lian Qiu-sheng,Chen Shu-zhen.Sparse image representation using the analytic contourlet transform and its application on compressed sensing[J].Acta Electronica Sinica,2010,38(6):1-6.(in Chinese)

[7]Foucart S.Sparse recovery algorithms:sufficient conditions in terms of restricted isometry constants[C].Approximation Theory XIII,Springer Proceedings in Mathematics,2010,65-77.

[8]Garg R,Khandekar R.Gradient descent with sparsication:an iterative algorithm for sparse recovery with restricted isometry property[A].Proceedings of the 26th Annual International Conference on Machine Learning,ICML ′09[C].ACM,New York,NY,USA,2009,337-344.

[9]Cai J,Osher S,Shen Z.Split bregman methods and frame based image restoration[J].Multiscale Modeling & Simulation,2009,8(2):337-369.

[10]Dai W,Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction[J].IEEE Transactions on Information Theory,2009,55(5):2230-2249.

[11]Nam S,Davis M,Elad M,et al.The cosparse analysis model and algorithms[J].Applied and Computational Harmonic Analysis.2013,34(1):30-56.

[12]Giryes R,Nam S,Gribonval R.Iterative cosparse projection algorithms for the recovery of cosparse vectors[A].The 19thEuropean Signal Processing Conference (EUSIPCO-2011)[C],Barcelona,Spain,2011.

[13]Blumensath T,Davis M.Iterative hard thresholding for compressed sensing[J].Applied and Computational Harmonic Analysis,2009,27 (3):265-274.

[14]FoucartS S.Hard thresholding pursuit:an algorithm for compressive sensing[J].SIAM J.Numer.Anal.2011,49 (6):2543-2563.

[15]Giryes R,Nam S,Elad M.Greedy-like algorithm for the cosparse analysis model[J].Special Issue in LAA on Sparse Approximate solution of Linear Systems.2012,(7).

[16]Lu Y M,Do M N.A theory for sampling signals from a union of subspaces[J].IEEE Trans.Signal Process.,2008,56(6):2334-2345.

[17]Blumensath T,Davies E.Sampling theorems for signals from the union of finite-dimensional linear subspaces[J].IEEE Trans.Inform.Theory,2009,55(4):1872-1882.

[18]Giryes R,Nam S,Elad M.CoSamp and SP for the cosparse analysis model[A].20thEuropean Signal Processing Conference(EUSIPCO 2012)[C].Bucharest,Romania,Aug,2012.26-31.

[19]Nam S,Davis M,Elad M,et al.Cosparse analysis modeling[A].The 9th International Conference on Sampling Theory and Applications(sampta-2011)[C].Singapore,2011.

張宗念 男,1963年6月生于河北深州,副教授.2000年獲華南理工大學(xué)博士學(xué)位.主要研究方向為壓縮感知理論與應(yīng)用、圖像處理.

E-mail:zzn99@sohu.com

李金徽 男,1980年4月生于遼寧沈陽,工程師.2004年獲重慶工商大學(xué)學(xué)士學(xué)位.主要研究方向為分布式計算機網(wǎng)絡(luò).

E-mail:li@dgut.edu.cn

黃仁泰 男,1964年12月生于廣東東莞,副教授.2006年獲華中科技大學(xué)碩士學(xué)位.主要研究方向為分布式計算機網(wǎng)絡(luò).

E-mail:huangrt@dgut.edu.cn

閆敬文 男,1964年7月生于吉林磐石,博士,教授,博士生導(dǎo)師.1997獲中國科學(xué)院長春光機所博士學(xué)位.主要研究方向為圖像處理和分析、遙感圖像處理等.

E-mail:jwyan@stu.edu.cn

Approximately Optimal Subspace Pursuit Based on Cosparse Analysis Model

ZHANG Zong-nian1,LI Jin-hui2,HUANG Ren-tai3,YAN Jing-wen4

(1,DepartmentofElectronicEngineering,DongguanUniversityofTechnology,Dongguan,Guangdong523808,China;2.NetworkCenter,DongguanUniversityofTechnology,Dongguan,Guangdong523808,China;3.DepartmentofComputerScience,DongguanUniversityofTechnology,Dongguan,Guangdong523808,China;4.DepartmentofElectronicsEngineering,ShantouUniversity,Shantou,Guangdong515063,China)

An approximately optimal subspace pursuit algorithm under cosparse analysis model was studied to reconstruct the original signal from the noisy measurement vectors.To overcome the drawbacks of the non steepest gradient during the pursuit process and the low successful reconstruction probability for sparse synthesis model,an approximately optimal subspace pursuit algorithm based on cosparse analysis model was presented and realized.The approximately optimal optimization object function for the algorithm was designed according to the structure of the different analysis dictionaries,the iterative pursuit process of the algorithm was revised,and the methods of selecting cosparsity was optimized.The simulation experiments show that the complete reconstruction probability of the new algorithm is evidently larger than that of the algorithm for ASP,AHTP,AIHT,AL1 and GAP when the cosparse operator is a random compact frame or a two dimension total variant matrix.The comprehensive average PSNR of the output signal for the new algorithm is larger than that of the algorithm of ASP,AHTP,and AIHT for 0.8dB,1.38dB and 3.13 dB respectively and is less than that of the algorithm of GAP and AL1 for 0.32 dB and 0.6dB when the input signal is with Gaussion noise.The complete reconstruction probability of the new algorithm was greatly improved by adopting the above measures,and the convergence condition for the new algorithm was simplified.

cosparse analysis model;approximately optimal;subspace;pursuit

2013-01-18；

2016-03-04； 責(zé)任編輯:郭游

國家自然科學(xué)基金(No.40971206)；廣東省自然科學(xué)基金(No.2015A030313654)

TN911.72

A

0372-2112 (2016)10-2289-05

??學(xué)報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.001