喬田田,張 宇,李維國(guó)

(1.中國(guó)石油大學(xué)(華東)理學(xué)院,山東青島266580;2.哈爾濱理工大學(xué)電氣與電子工程學(xué)院,哈爾濱150080)

一種基于壓縮感知的信號(hào)重建新算法*

喬田田1,**,張 宇2,李維國(guó)1

(1.中國(guó)石油大學(xué)(華東)理學(xué)院,山東青島266580;2.哈爾濱理工大學(xué)電氣與電子工程學(xué)院,哈爾濱150080)

在求解基追蹤問(wèn)題的線性化Bregman迭代方法基礎(chǔ)上,結(jié)合了廣義逆的迭代技術(shù)得到一種稀疏信號(hào)重構(gòu)的新算法。該算法在計(jì)算Moore-Penrose廣義逆時(shí),采用了迭代計(jì)算的方式,與算法本身相結(jié)合使得僅有矩陣向量乘積運(yùn)算,避免了奇異值分解的較大工作量。通過(guò)數(shù)值試驗(yàn)可知,新算法相對(duì)線性化Bregman算法在計(jì)算時(shí)間上約減少了2/3,同時(shí)信號(hào)的恢復(fù)效果也是穩(wěn)定有效的。因此,新算法是一種有效可行的信號(hào)重建算法。

信號(hào)重構(gòu);壓縮感知;廣義逆;線性化Bregman迭代法;稀疏重構(gòu)

1 引 言

近年來(lái)對(duì)有關(guān)壓縮感知的稀疏信號(hào)重構(gòu)方面的研究越來(lái)越受到眾多學(xué)者的關(guān)注。壓縮感知是由Donoho[1]等人提出的一種稀疏信號(hào)重構(gòu)的新的信息獲取理論,在1998年提出的基追蹤模型可以很好地解決稀疏信號(hào)重構(gòu)問(wèn)題[2]。壓縮感知的很多應(yīng)用領(lǐng)域都涉及到基追蹤問(wèn)題:

式中,A∈Rm×n,f∈Rm,m＜n。

對(duì)于問(wèn)題(1)的求解,在最近幾年內(nèi)得到了迅猛的發(fā)展。諸多的研究算法層出不窮,像內(nèi)點(diǎn)法、梯度投影法等,其中主要是以?xún)?yōu)化中的Bregman算法的引入繼而產(chǎn)生的一系列速度快、效果好的算法為主流,因其相對(duì)其他算法在速度上具有明顯的優(yōu)勢(shì),使得眾多研究者對(duì)此興趣濃厚。Bregman算法是由L.Bregman在1967年提出的優(yōu)化問(wèn)題求解中的經(jīng)典方法[3],最近由Osher[4]等人將其引入圖像恢復(fù)的應(yīng)用中得到了前所未有的好結(jié)果,提高了圖像恢復(fù)的計(jì)算效率。隨即由于Donoho[5]、Candés[6-7]等人在壓縮感知方面的進(jìn)一步工作,使更多的研究者將其引入l1稀疏優(yōu)化問(wèn)題當(dāng)中[8-9]。隨著研究的進(jìn)一步深入,Osher等人提出了帶軟閾值算子的線性化Bregman方法的一系列的等價(jià)形式。由于應(yīng)用范圍的擴(kuò)大,A的性質(zhì)不斷弱化,方程Au=f很難被滿足,于是得到了帶有A+的線性化Bregman算法[10]。2010年,張慧等人[11]在此基礎(chǔ)上得到了A-的算法,掀開(kāi)了對(duì)特殊矩陣A的稀疏信號(hào)重構(gòu)算法方面更為細(xì)致的研究。

本文就是在這些算法研究的基礎(chǔ)上,結(jié)合之前在廣義逆迭代方面取得的成果提出了一種新的混亂迭代算法用以解決稀疏信號(hào)重構(gòu)的問(wèn)題。

2 預(yù)備知識(shí)

2.1 廣義逆

由于新算法是要結(jié)合廣義逆的迭代格式,所以在提出新算法之前給出相關(guān)的定義和引理。

定義1[12]:設(shè)A∈Cm×n,若X滿足下面性質(zhì),即Moore-Penrose條件:

則稱(chēng)X為A的偽逆,也稱(chēng)作Moore-Penrose廣義逆,記作A+。

定義2[13]:設(shè)A,B∈Cn×m,稱(chēng)

是(A,B)的值域。

引理1[13]:設(shè)A∈Cm×n≠0,如果初始值V0滿足

式中,I是m×m單位矩陣,A*是矩陣A的共軛轉(zhuǎn)置。則由

產(chǎn)生的序列{Vq}q∈N收斂到A+。

2.2 線性化Bregman迭代法

用于求解問(wèn)題(1)的線性化Bregman算法的迭代格式為[8]

k∈N

的唯一解,當(dāng)μ→∞時(shí),即為問(wèn)題(1)的極小l2范數(shù)解。

與之對(duì)應(yīng)的帶軟閾值算子的迭代法[9]:

式中,u0=v0=0,且Tμ(·)是軟閾值算子[8]。

考慮到A的性質(zhì),約束條件Au=f很難滿足,文獻(xiàn)[8]中提出了A行滿秩情況下的式(8)等價(jià)的AT算法:

顯然,式(9)計(jì)算Au=f的最小二乘解。同時(shí)考慮到A的條件數(shù)太大的影響,得到了A行滿秩時(shí)等價(jià)的A+算法[8]:

對(duì)于A是任意矩陣時(shí),文獻(xiàn)[11]將其推廣至A-算法。從計(jì)算的角度,我們看到式(10)既能夠得到其最小二乘解,也充分考慮到條件數(shù)對(duì)計(jì)算穩(wěn)定性的影響,但卻由于A+的存在使得計(jì)算量加大。

3 新算法

從上節(jié)的敘述中可知,A為任意矩陣時(shí),A+算法(式(10))每一步的迭代計(jì)算雖然仍為矩陣向量乘積,但A+本身的計(jì)算量卻很大,且其所需時(shí)間也相對(duì)較大。因此,為了解決A+計(jì)算量大的問(wèn)題,利用引理1

以及考慮A+計(jì)算過(guò)程和信號(hào)恢復(fù)的細(xì)節(jié)丟失問(wèn)題,提出了下面的混亂迭代格式:

事實(shí)上,

即

考慮到式(5)等價(jià)于

從式(14)、(15)可知,方法(12)是充分考慮到廣義逆的迭代技術(shù)和使用更多步的細(xì)節(jié)信息來(lái)重建信號(hào),這從使用f0,f1,…,fk+1的數(shù)據(jù)中可以看出。同時(shí)我們還看到,計(jì)算量仍能保持僅有矩陣向量乘積的運(yùn)算,這在速度上依然保持了Bregman系列算法的優(yōu)勢(shì),因此我們有理由相信算法(12)的可行性。下面我們就通過(guò)數(shù)值試驗(yàn)對(duì)比原來(lái)的A+算法和改進(jìn)后的結(jié)果來(lái)進(jìn)一步驗(yàn)證我們的推理。

4 數(shù)值試驗(yàn)及分析

由于Bregman迭代系列方法取得的快速結(jié)果,本文僅在線性Bregman方法的基礎(chǔ)上進(jìn)一步改進(jìn),其結(jié)果若相對(duì)于Bregman系列方法都具有明顯優(yōu)勢(shì),則相對(duì)經(jīng)典的一些方法也就不必再加以對(duì)比。

數(shù)值試驗(yàn)是在Intel(R)Core(TM)2 Duo CPU E7200@2.5GHz 2.5GHz 1.0GB內(nèi)存的機(jī)器上進(jìn)行的,軟件MATLAB7.1版本。

進(jìn)行隨機(jī)信號(hào)的試驗(yàn),相同的初值選擇u0=f0= 0,A∈Rm×n,V0=α AT,其參數(shù)選取采用下面兩組:

參數(shù)(1)和(2)是分別針對(duì)不同量級(jí)的信號(hào)設(shè)定的。從上面的理論討論可知,0＜δ＜1,μ取相對(duì)較大的數(shù),這里我們?yōu)榱藢?duì)比結(jié)果一致選取10(可以參見(jiàn)文獻(xiàn)[9])。由于采用是相對(duì)量級(jí)上的隨機(jī)信號(hào)進(jìn)行的實(shí)驗(yàn),所以具有一般性,算法不受實(shí)際信息環(huán)境的影響。實(shí)驗(yàn)結(jié)果也是隨機(jī)的,數(shù)據(jù)分析具有一般性,數(shù)據(jù)結(jié)果的對(duì)比狀況基本一致。其中,我們還注意到參數(shù)(1)的隨機(jī)實(shí)驗(yàn),其矩陣條件數(shù)為cond(A)=2.054330337102665e+016,而參數(shù)(2)則達(dá)到cond(A)=1.792691288210052e+017,由此可見(jiàn),盡管矩陣是病態(tài)的情況下,算法的恢復(fù)效果仍然是穩(wěn)定的。

圖1和圖2是在參數(shù)(1)條件下,繪制的原始信號(hào)、測(cè)量信號(hào)以及兩種方法分別恢復(fù)的結(jié)果;圖3和圖4是在參數(shù)(2)條件下,對(duì)應(yīng)的上述信號(hào)的圖像。表1中顯示在不同參數(shù)條件下,兩種算法的對(duì)比結(jié)果。在同一誤差量級(jí)的情況下,我們可以看到計(jì)算時(shí)間大約減少了2/3,并且隨著計(jì)算規(guī)模的增加,混亂迭代算法呈現(xiàn)出更為明顯的優(yōu)勢(shì)。同時(shí),注意到A的條件數(shù)巨大,說(shuō)明計(jì)算問(wèn)題是病態(tài)的。而且rank(A)＜＜m＜n,信號(hào)數(shù)目非常稀疏的情況下,我們采用混亂迭代算法仍能很好地替代A+的計(jì)算取得滿意的結(jié)果,說(shuō)明該算法的確很有競(jìng)爭(zhēng)力,具有較好的恢復(fù)效果。

圖1 原始信號(hào)和對(duì)應(yīng)的測(cè)量信號(hào)(n=500,m=250)Fig.1 Clear and measurement signal when n=500,m=250

圖2 恢復(fù)信號(hào)(n=500)Fig.2 Restored signals when n=500

圖3 原始信號(hào)和對(duì)應(yīng)的測(cè)量信號(hào)(n=5 000,m=1 000)Fig.3 Clear and measurement signal when n=5 000,m=1 000

圖4 恢復(fù)信號(hào)(n=5 000)Fig.4 Restored signals when n=5 000

表1 不同參數(shù)下兩種算法的計(jì)算結(jié)果對(duì)比Table 1 Two algorithm calculation results under different parameters

5 結(jié) 論

從上面的分析中可以看到,本文提出的基于線性化Bregman迭代方法和廣義逆迭代技術(shù)的新算法在求解基追蹤問(wèn)題時(shí),是非常有效的。它具有線性化Bregman迭代法的全部?jī)?yōu)點(diǎn),還在計(jì)算耗時(shí)和工作量上具有較大的優(yōu)勢(shì)。從理論分析可知,該方法更多地考慮數(shù)據(jù)信息細(xì)節(jié)丟失的影響,利用更多的數(shù)據(jù)信息,從而使稀疏信號(hào)重構(gòu)的效果得以提高,是在本質(zhì)上提高重構(gòu)的效果。從數(shù)值試驗(yàn)的結(jié)果分析可知,信號(hào)數(shù)據(jù)都是隨機(jī)產(chǎn)生的,同時(shí)在試驗(yàn)過(guò)程中也并未發(fā)現(xiàn)有任何例外的情況,因此結(jié)論具有一般性。下一步應(yīng)可以考慮更為細(xì)微的信號(hào)的恢復(fù)情況,進(jìn)一步增強(qiáng)信號(hào)恢復(fù)的準(zhǔn)確性。

[1] Tsaig Y,Donoho D L.Extensions of compressed sensing [J].Signal Processing,2006,86(3):549-571.

[2] Chen S S,Donoho D L,Saunders M A.Atomic decomposition by basis pursuit[J].SIAM Journal on Scientific Computing,1998,20(1):33-61.

[3] Bregman L M.The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming[J].USSR Computational Mathematics and Mathematical Physics,1967,7 (3):200-217.

[4] Osher S,Burger M,Goldfarb D,et al.An iterative regularization method for total variation-based image restoration[J].Multiscale Modeling&Simulation,2005,4 (2):460-489.

[5] Donoho D L.Compressed sensing[J].IEEE Transac

tions on Information Theory,2006,52(4):1289-1306. [6] Candès E J,Romberg J.Quantitative robust uncertainty principles and optimally sparse decompositions[J]. Foundations of Computational Mathematics,2006,6(2): 227-254.

[7] Candès E J,Romberg J,Tao T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory,2006,52(2):489-509.

[8] Yin W,Osher S,Goldfarb D,et al.Bregman iterative algorithms for l1-minimization with applications to compressed sensing[J].SIAM Journal on Imaging Sciences, 2008,1(1):143-168.

[9] Cai J F,Osher S,Shen Z.Linearized Bregman iterations for compressed sensing[J].Mathematics of Computation, 2009,78(267):1515-1536.

[10] Cai J F,Osher S,Shen Z.Linearized Bregman iterations for frame-based image deblurring[J].SIAM Journal on Imaging Sciences,2009,2(1):226-252.

[11] 張慧,成禮智.A-線性Bregman迭代算法[J].計(jì)算數(shù),2010,32(1):97-104. ZHANG Hui,CHENG Li-zhi.A-linearized Bregman iteration algorithm[J].Mathmatica Numerica Sinica, 2010,32(1):97-104.(in Chinese)

[12] Wang G,Wei Y,Qiao S.Generalized Inverses:Theory and Computations[M].Beijing:Science Press,2004.

[13] 王松桂,楊振海.廣義逆矩陣及其應(yīng)用[M].北京:北京工業(yè)大學(xué)出版社,1996:202-209. WANG Song-gui,YANG Zhen-hai.Generalized Inverse Matrix and its Application[M].Beijing:Beijing Industrial University Press,1996:202-209.(in Chinese)

QIAO Tian-tian was born in Suihua,Heilongjiang Province,in 1983.She is now a lecturer and currently working toward the Ph.D. degree.Her research concerns image and signal processing.

Email:qtthsnxf@126.com

張 宇(1988—),女,黑龍江大慶人,碩士研究生,主要從事電力電子方面的研究;

ZHANG Yu was born in Daqing,Heilongjiang Province,in 1988.She is now a graduate student.Her research concerns power electronics.

李維國(guó)(1964—),男,山東臨沂人,教授、博士生導(dǎo)師,主要從事數(shù)值計(jì)算與圖像處理方面的研究。

LI Wei-guo was born in Linyi,Shandong Province,in 1964. He is now a professor and also the Ph.D.supervisor.His research interests include numerical computing and image processing.

A New Signal Reconstruction Algorithm Based on Compressed Sensing

QIAO Tian-tian1,ZHANG Yu2,LI Wei-guo1
(1.College of Science,China Universityof Petroleum,Qingdao 266580,China; 2.College of Electrical and Electronic Engineering,Harbin University of Science and Technology,Harbin 150080,China)

Combined with the iterative method of generalized inverse,a new algorithm for sparse signal reconstruction is developed based on linearized Bregman iteration for solving the basis pursuit problems.During calculating Moore-Penrose generalized inverse,the algorithm only has the matrix-vector multiplication by iteration combined with its own,so that the singular value decomposition(SVD)is avoided.The numerical experiments show the computation time has reduced by about 2/3 than that of original algorithms. Meanwhile,the recovery of signals is stabe and effective.So this new algorithm is a feasible signal reconstruction algorithm.

signal reconstruction;compress sensing;generalized inverse;linearized Bregman iteration; sparse reconstruction

The National Natural Science Foundation of China(No.61101208);The Fundamental Research Funds for the Central Universities(13CX02086A);The Innovation Fund of Oceanic Telemetry Engineering and Technology Research Center,State O-ceanic Administration(2012003)

date:2013-05-31;Revised date:2013-09-25

國(guó)家自然科學(xué)基金資助項(xiàng)目(61101208);中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金(13CX02086A);國(guó)家海洋局海洋遙測(cè)工程技術(shù)研究中心創(chuàng)新青年基金項(xiàng)目(2012003)

**通訊作者:qtthsnxf@126.com Corresponding author:qtthsnxf@126.com

TN911

A

1001-893X(2013)10-1289-04

喬田田(1983—),女,黑龍江綏化人,博士研究生,講師,主要從事圖像與信號(hào)處理方面的研究;

10.3969/j.issn.1001-893x.2013.10.007

2013-05-31;

2013-09-25