宋和平王國(guó)利

①(江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013)②(中山大學(xué)信息科學(xué)與技術(shù)學(xué)院 廣州 510006)

1 引言

近年來(lái)，稀疏信號(hào)處理成為信號(hào)處理和應(yīng)用數(shù)學(xué)等領(lǐng)域的一個(gè)新研究熱點(diǎn)，特別是新興發(fā)展的壓縮傳感(Compressed sensing, CS)理論[1,2]。壓縮傳感為稀疏信號(hào)處理提供了一個(gè)新的方向，可以通過(guò)欠采樣的線性測(cè)量重構(gòu)稀疏信號(hào)。壓縮傳感開(kāi)創(chuàng)了很多新的應(yīng)用，為此，多個(gè)國(guó)際期刊專(zhuān)門(mén)為壓縮傳感出版了專(zhuān)刊，總結(jié)了當(dāng)前的研究進(jìn)展[35]-。

壓縮傳感由欠采樣的線性測(cè)量重構(gòu)未知稀疏信號(hào)，其稀疏信號(hào)重構(gòu)是求解一個(gè)帶稀疏約束的欠定線性問(wèn)題即0?優(yōu)化問(wèn)題。然而，0?問(wèn)題是個(gè)NP難的非凸組合問(wèn)題。為此，壓縮傳感的奠基工作[1,2]提出用1?問(wèn)題代替0?問(wèn)題，即基追蹤(Basis Pursuit,BP)問(wèn)題[6]。此后，很多研究人員提出各種稀疏信號(hào)重構(gòu)的計(jì)算方法[7]。一般地可以分為3種：凸松弛算法、貝葉斯推理和貪婪算法。凸松弛算法將稀疏信號(hào)重構(gòu)的0?問(wèn)題替換為凸優(yōu)化問(wèn)題，如BP算法[6]等。貝葉斯推理算法由稀疏先驗(yàn)?zāi)Ｐ颓蠼庾畲蠛篁?yàn)估計(jì)，如貝葉斯壓縮傳感(Bayesian Compressive Sensing, BCS)[8]等。凸松弛算法依賴(lài)于最優(yōu)化算法的實(shí)現(xiàn)，相對(duì)來(lái)說(shuō)計(jì)算比較復(fù)雜耗時(shí)；貝葉斯推理算法依賴(lài)于信號(hào)的先驗(yàn)假設(shè)，而且算法參數(shù)比較多。貪婪算法具有易于設(shè)計(jì)實(shí)現(xiàn)、計(jì)算復(fù)雜度相對(duì)低的特點(diǎn)，吸引了很多研究者的關(guān)注。常見(jiàn)的算法有正交匹配追蹤(Orthogonal Matching Pursuit,OMP)[9]、子空間追蹤(Subspace Pursuit, SP)[10]、壓縮采樣匹配追蹤(Compressive Sampling Matching Pursuit, CoSaMP)[11]、分階段正交匹配追蹤(Stagewise Orthogonal Matching Pursuit,StOMP)[12]和迭代硬閾值化算法(Iterative Hard Thresholding, IHT)[13]等。迭代硬閾值化是一種簡(jiǎn)單實(shí)用的稀疏信號(hào)重構(gòu)方法，但其收斂速度比較慢。最近，文獻(xiàn)[14]提出一種新的加速算法雙超松弛閾值化算法(Double OverRElaxation thresholding,DORE)。DORE算法是一種基于條件期望值最大化(Expectation Conditional Maximization Either,ECME)迭代的加速算法，其中 ECME由方差未知的高斯模型推導(dǎo)。對(duì)稀疏度k未知情況，文獻(xiàn)[14]提出一種自動(dòng)雙超松弛閾值化算法(Automatic Double OverRElaxation thresholding, ADORE)。借用文獻(xiàn)[15]的概念，本文把這一類(lèi)算法分為單階段閾值化(One-Stage Thresholding, OST)和雙階段閾值化(Two-Stage Thresholding, TST)①閾值化(Thresholding)是一種非線性函數(shù)，如 MATLAB 函數(shù)wthresh，定義硬閾值化；軟閾值化。本文所述的雙階段閾值化是文獻(xiàn)[15]中TST概念的推廣。。

鑒于單次求解 BP問(wèn)題的稀疏重構(gòu)結(jié)果不夠理想，特別是對(duì)測(cè)量次數(shù)相對(duì)較少的情況，文獻(xiàn)[16]提出一種迭代改進(jìn) BP的算法迭代支持集檢測(cè)(Iterative Support Detection, ISD)，其思想是通過(guò)迭代支持集檢測(cè)來(lái)改善 BP算法的重構(gòu)結(jié)果。ISD是一個(gè)算法框架，具體實(shí)現(xiàn)依賴(lài)于支持集檢測(cè)方法。本文借鑒ISD算法中支持集檢測(cè)的思想，把ISD算法應(yīng)用于貪婪算法，提出一種新的稀疏信號(hào)重構(gòu)算法框架閾值化迭代檢測(cè)估計(jì)(Iterative Detection Estimation with Thresholding, IDET)。IDET算法框架為設(shè)計(jì)新的貪婪算法提供了思路，設(shè)計(jì)新的貪婪算法包括兩個(gè)方面：(1)選擇 OST算法的迭代步作為支持集檢測(cè)的參考；(2)根據(jù)稀疏信號(hào)的特征設(shè)計(jì)支持集檢測(cè)方法。同時(shí)，本文提出該算法框架的實(shí)現(xiàn)算法。該實(shí)現(xiàn)算法首先檢測(cè)IHT算法的迭代步得到一個(gè)支持集，然后通過(guò)求解支持集上的最小二乘問(wèn)題來(lái)估計(jì)待重構(gòu)的稀疏信號(hào)，迭代上述兩個(gè)步驟直至滿(mǎn)足停止條件。IDET算法的關(guān)鍵在于支持集檢測(cè)，本文提出3種適用于快速衰減信號(hào)[16]的支持集檢測(cè)方法?？焖偎p信號(hào)是指信號(hào)的絕對(duì)值從大到小衰減很快，常見(jiàn)的有稀疏高斯信號(hào)、稀疏拉普拉斯信號(hào)和一些冪律衰減信號(hào)。

2 基于閾值化的稀疏重構(gòu)算法

本文關(guān)注的是迭代貪婪算法，借用文獻(xiàn)[15]的概念，把這一類(lèi)算法分為單階段閾值化OST和雙階段閾值化 TST算法。OST算法是本文對(duì)應(yīng)文獻(xiàn)[15]中TST提出的概念，是指對(duì)算法迭代步進(jìn)行一次閾值化就能重構(gòu)稀疏信號(hào)的算法。下面將分別介紹OST算法和TST算法。另外，本節(jié)將介紹相關(guān)的迭代支持集檢測(cè)ISD算法。

2.1 單階段閾值化

文獻(xiàn)[14]由高斯概率框架推導(dǎo)出ECME迭代：

2.2 雙階段閾值化

考慮壓縮傳感的稀疏信號(hào)重構(gòu)問(wèn)題，雙階段閾值化TST算法的目的是檢測(cè)一個(gè)支持集I來(lái)近似測(cè)量向量。待重構(gòu)的稀疏信號(hào)初始賦值為,TST算法迭代計(jì)算下面兩個(gè)步驟：

(1)支持集檢測(cè)：檢測(cè)信號(hào)x的支持集I，即選擇測(cè)量矩陣A的哪些列去生成測(cè)量向量y，或者說(shuō)確定用信號(hào)x的哪些分量來(lái)稀疏表示x。

(2)信號(hào)估計(jì)：通過(guò)求解支持集I上的最小二乘問(wèn)題來(lái)更新待重構(gòu)的稀疏信號(hào)x，其中支持集定義為表示集合I在上的補(bǔ)集。TST算法的支持集檢測(cè)和信號(hào)估計(jì)分別被認(rèn)為是一次閾值化，不同算法在支持集檢測(cè)上各不相同，如OMP, SP, CoSaMP,StOMP等算法分別采用不同的策略進(jìn)行支持集檢測(cè)；信號(hào)估計(jì)都采用支持集上的最小二乘法。

2.3 迭代支持集檢測(cè)

迭代支持集檢測(cè) ISD算法[16]的提出是基于 BP算法的稀疏重構(gòu)結(jié)果，其思想是通過(guò)迭代支持集檢測(cè)來(lái)改善 BP算法的重構(gòu)性能。初始一個(gè)支持集, ISD算法迭代計(jì)算下面兩個(gè)步驟：

(2)支持集檢測(cè)： 以第(1)步重構(gòu)結(jié)果x作為參考檢測(cè)得到一個(gè)支持集I。

迭代支持集檢測(cè)(ISD)是一個(gè)算法框架，具體實(shí)現(xiàn)依賴(lài)于支持集檢測(cè)方法。文獻(xiàn)[16]針對(duì)快速衰減信號(hào)提出幾種有效的支持集檢測(cè)方法。這里只介紹其中一種簡(jiǎn)單實(shí)用的閾值化方法(如不作特別說(shuō)明，下文中ISD算法特指由式(4)定義的方法)。

3 閾值化迭代檢測(cè)估計(jì)

鑒于ISD算法在理論和應(yīng)用上的成功，本文把ISD算法中支持集檢測(cè)的思想應(yīng)用到雙階段閾值化TST算法，提出一種新的稀疏信號(hào)重構(gòu)算法框架閾值化迭代檢測(cè)估計(jì)(IDET)，其算法流程如圖1所示。閾值化迭代檢測(cè)估計(jì)IDET屬于TST算法，它利用 OST算法作為其中支持集檢測(cè)的參考。IDET算法設(shè)計(jì)的關(guān)鍵在于：(1)選擇合適的OST算法迭代步作為支持集檢測(cè)的參考；(2)根據(jù)稀疏信號(hào)的特征設(shè)計(jì)支持集檢測(cè)方法。由于ECME的迭代步需要計(jì)算存儲(chǔ)逆矩陣，特別不適用于大規(guī)模應(yīng)用，本文采用較為簡(jiǎn)單的IHT迭代步作為支持集檢測(cè)的參考，設(shè)計(jì)IDET的實(shí)現(xiàn)算法。該實(shí)現(xiàn)算法首先檢測(cè)IHT算法的迭代步得到一個(gè)支持集I，然后通過(guò)求解支持集I上的最小二乘問(wèn)題來(lái)估計(jì)待重構(gòu)的稀疏信號(hào)，迭代上述兩個(gè)步驟直至滿(mǎn)足停止條件。

IDET算法的關(guān)鍵在于支持集檢測(cè)，根據(jù)文獻(xiàn)[16]對(duì)稀疏信號(hào)特征的觀察，本文相應(yīng)的只設(shè)計(jì)適用于快速衰減信號(hào)的支持集檢測(cè)方法，提出3種不同的方法。綜上，提出的IDET實(shí)現(xiàn)算法描述為：

圖1 閾值化迭代檢測(cè)估計(jì)(IDET)的算法流程圖

(2)支持集檢測(cè)：更新信號(hào)估計(jì)：

檢測(cè)支持集I：

(3)信號(hào)估計(jì)：估計(jì)信號(hào)：

更新殘差信號(hào)：。

本文提出了3種支持集檢測(cè)方法，相應(yīng)的IDET實(shí)現(xiàn)算法命名為IDET-k, IDET-β和IDET-γ，其中是閾值化參數(shù)。

評(píng)注：

(1)IDET算法是本文借鑒ISD算法思想提出的算法框架，其實(shí)現(xiàn)算法采用OST算法IHT的迭代步作為參考來(lái)檢測(cè)支持集I。文獻(xiàn)[20]是本文算法框架的特例，該算法由基于 Bernoulli-Gaussian模型的二值假設(shè)檢驗(yàn)推導(dǎo)的迭代步也是IHT的迭代步，但其不涉及支持集檢測(cè)方法的設(shè)計(jì)。OMP, SP,CoSaMP等方法采用殘差信號(hào)與測(cè)量矩陣的相關(guān)度作為檢測(cè)支持集的參考，而是最小二乘的負(fù)梯度。IDET實(shí)現(xiàn)算法中支持集檢測(cè)參考的是最小二乘的梯度下降迭代步，梯度下降迭代步由于提供了稀疏信號(hào)估計(jì)在算法設(shè)計(jì)上更為靈活，可以根據(jù)稀疏信號(hào)的不同特點(diǎn)設(shè)計(jì)不同的支持集檢測(cè)方法。

關(guān)于Beats1的運(yùn)行模式研究，不僅需要分析其優(yōu)勢(shì)，還應(yīng)分析其不足，以便形成更客觀和更全面的認(rèn)識(shí)，探索具有良好前景的發(fā)展途徑。 例如： 目前電臺(tái)產(chǎn)業(yè)的主要用戶(hù)群體是中老年人，而使用蘋(píng)果公司產(chǎn)品的主要是青年群體，如何進(jìn)一步吸引青年群體對(duì)音樂(lè)的電臺(tái)模式的興趣已成為亟待解決的問(wèn)題； 另外，網(wǎng)絡(luò)科技的高速發(fā)展帶來(lái)了音樂(lè)產(chǎn)品頻繁的更新?lián)Q代，Beats1如何適應(yīng)產(chǎn)品的快速變化也是不容忽視的方面。 這些都是筆者下一步研究中需要深入探索的課題。

(2)IDET-β算法的支持集檢測(cè)方法與ISD算法類(lèi)似，都是通過(guò)與指數(shù)遞減的閾值相比保留絕對(duì)值較大的分量。IDET-γ算法的支持集檢測(cè)方法則保留當(dāng)前檢測(cè)到的支持集I，下次迭代在支持集I的補(bǔ)集上作檢測(cè)。這兩種支持集檢測(cè)方法都不像IDET-k一樣每次迭代確定支持集的勢(shì)為k，適用于稀疏度k未知的應(yīng)用。

(3)IDET算法思想與ISD算法類(lèi)似，關(guān)鍵的區(qū)別在于支持集檢測(cè)方法。它們最大的不同之處在于支持集檢測(cè)參考的是不同的稀疏重構(gòu)方法。IDET算法支持集檢測(cè)參考的是OST，而ISD算法支持集檢測(cè)參考的是BP。由此可見(jiàn)IDET算法比ISD算法在計(jì)算復(fù)雜度上更具優(yōu)勢(shì)。IDET估計(jì)信號(hào)采用的是支持集I上的最小二乘法，而ISD估計(jì)信號(hào)是在支持集I的補(bǔ)集上求解BP。由此可見(jiàn)IDET算法比ISD算法更適合于大規(guī)模應(yīng)用。

(4)IDET算法可認(rèn)為是一種與 DORE不同的OST加速算法。DORE先通過(guò)IHT估計(jì)稀疏信號(hào)，然后通過(guò)兩步超松弛加速算法，最后進(jìn)行一次硬閾值化來(lái)保證重構(gòu)的稀疏信號(hào)是k稀疏的。DORE需要知道先驗(yàn)稀疏度k，而 IDET-β,IDET-γ不需要這個(gè)強(qiáng)條件，只需給定一個(gè)閾值化參數(shù)即可。采用自動(dòng)雙超松弛閾值化ADORE需要很多次的DORE來(lái)估計(jì)稀疏度k。

(5)閾值化迭代檢測(cè)估計(jì)的IDET-β和IDET-γ跟閾值化參數(shù)有關(guān)。閾值化參數(shù)越大稀疏重構(gòu)效果越好，相應(yīng)地其支持集I增加地越慢，這樣需要更多的迭代次數(shù)(見(jiàn)實(shí)驗(yàn)部分)。

(6)與其他貪婪算法，如OMP, SP, CoSaMP等不同，閾值化迭代檢測(cè)估計(jì)的 IDET-k每次迭代確定支持集的勢(shì)為k，而不是逐次增加 1或多個(gè)(k,2k)索引到支持集I后再進(jìn)行一次硬閾值化。IDET-β的支持集I是非遞增或嵌套的，而 IDET-γ的支持集I是遞增或嵌套的。

(7)正如ISD算法所討論，閾值化迭代檢測(cè)估計(jì)的IDET-β和IDET-γ只適用于快速衰減信號(hào)，對(duì)那些信號(hào)絕對(duì)值衰減很慢甚至不衰減(如二值 0/+1、三值0/-1/+1信號(hào))情況不適用，閾值化迭代檢測(cè)估計(jì)的 IDET-k沒(méi)有這個(gè)限制?？傮w來(lái)說(shuō)，閾值化迭代檢測(cè)估計(jì)IDET算法對(duì)非快速衰減信號(hào)沒(méi)有顯示出比1?最優(yōu)化更好的稀疏重構(gòu)性能[15,21]，但可以通過(guò)線性或非線性映射把非快速衰減信號(hào)轉(zhuǎn)化為適用于IDET算法的快速衰減信號(hào)[22]。

4 計(jì)算復(fù)雜度分析

閾值化迭代檢測(cè)估計(jì)的 IDET-k, IDET-β和IDET-γ算法主要的計(jì)算步驟為矩陣向量乘法(matrix-vector multiplication)。迭代硬閾值化IHT迭代的計(jì)算復(fù)雜度為 O ( m n)，那么算法 IDET-k,IDET-β和 IDET-γ的更新稀疏信號(hào)的計(jì)算復(fù)雜度為。閾值化步驟的計(jì)算復(fù)雜度為 O ( n l gk)②)算法IDET-k的支持集檢測(cè)需找出前k個(gè)最大值即計(jì)算復(fù)雜度為O(nlgk) , IDET-β和IDET-γ的支持集檢測(cè)只需兩次遍歷查找即計(jì)算復(fù)雜度為O(2n)，求解支持集上的最小二乘所采用的近似共軛梯度法的計(jì)算復(fù)雜度為為近似共軛梯度法迭代次數(shù))③算法IDET-β和IDET-γ支持集I變化不一，但|I|≤k，這里以|I|≤k計(jì)算。實(shí)驗(yàn)部分近似共軛梯度法迭代次數(shù)設(shè)為20。，更新殘差信號(hào)的計(jì)算復(fù)雜度為，那么每次迭代所需計(jì)算復(fù)雜度總和為。雙超松弛閾值化法(DORE)算法兩次硬閾值化的計(jì)算復(fù)雜度為，兩次超松弛步驟的計(jì)算復(fù)雜度為，那么每次迭代所需計(jì)算復(fù)雜度總和為。IDET算法和DORE算法需存儲(chǔ)測(cè)量矩陣A，其所需的存儲(chǔ)量為。OMP, SP等TST算法的計(jì)算復(fù)雜度分析參考文獻(xiàn)[23]。

5 實(shí)驗(yàn)結(jié)果

本節(jié)介紹仿真實(shí)驗(yàn)，所有代碼均由 MATLAB實(shí)現(xiàn)④所有代碼可在https://github.com/songhp/IDET/下載。，部分采用了文獻(xiàn)[14,21]提供的代碼，運(yùn)行環(huán)境為MATLAB v7.6，計(jì)算機(jī)操作系統(tǒng)為Windows XP, 2.53 GHz Intel Celeron CPU, 2 GB內(nèi)存。實(shí)驗(yàn)比較算法選擇 OST的加速算法 DORE算法和TST算法中性能較好的SP算法[15,21]，IDET算法不與1?最優(yōu)化(如ISD算法)和其他OST/TST算法(如OMP算法等)比較，這些算法已經(jīng)在文獻(xiàn)[14,15,21]中有詳細(xì)的比較。算法評(píng)價(jià)有兩組：相變(phase transitions)曲線和 Shepp-Logan Phantom 圖像重構(gòu)，更多的實(shí)驗(yàn)比較見(jiàn)文獻(xiàn)[23]。

5.1 相變曲線

在實(shí)驗(yàn)中，所有測(cè)量矩陣A都采用均勻球面矩陣集(Uniform spherical ensemble)，即測(cè)量矩陣A是隨機(jī)高斯矩陣并對(duì)A歸一化。實(shí)驗(yàn)所用k稀疏的信號(hào)x是隨機(jī)選擇勢(shì)為k的支持集，相應(yīng)的元素值由高斯分布均勻生成。為公平比較算法，實(shí)驗(yàn)中迭代停止條件設(shè)最大迭代次數(shù)為100或相對(duì)誤差為：。定義為稀疏性度量(sparsity),為不確定性度量(indeterminacy)，那么得到評(píng)價(jià)稀疏信號(hào)重構(gòu)的 2維相平面。對(duì)每一個(gè)δ，通過(guò)插值找到稀疏重構(gòu)概率大于0.50的所有ρ，這樣得到相變曲線。曲線之下表示稀疏重構(gòu)成功，反之則失敗。越高的相變曲線表示算法重構(gòu)能力越好。本實(shí)驗(yàn)采用文獻(xiàn)[21]所用代碼生成相變曲線。確定稀疏信號(hào)維數(shù)，線性選取16 對(duì)。每對(duì)實(shí)驗(yàn)運(yùn)行 100 次。采用是真實(shí)稀疏信號(hào))判定稀疏重構(gòu)準(zhǔn)確。

實(shí)驗(yàn)測(cè)試閾值化參數(shù)β對(duì)算法 IDET-β的影響，設(shè)β=0.7,0.8,0.9，選取δ=0.05, 0.20, 0.35, 0.50，閾值化參數(shù)β對(duì)算法IDET-β的影響如圖2所示，相應(yīng)的相變曲線如圖3所示。從圖中可以看出，β越大稀疏信號(hào)重構(gòu)的準(zhǔn)確重構(gòu)率越高，稀疏重構(gòu)性能越好。同樣地，測(cè)試閾值化參數(shù)γ對(duì)算法IDET-γ的影響，設(shè)γ=0.7,0.8,0.9，選取δ=0.05, 0.20, 0.35,0.50，閾值化參數(shù)γ對(duì)算法 IDET-γ的影響如圖 4所示，相應(yīng)的相變曲線如圖3所示。從圖中可以看出，γ越大稀疏信號(hào)重構(gòu)的準(zhǔn)確重構(gòu)率越高，稀疏重構(gòu)性能越好。圖5實(shí)驗(yàn)對(duì)比了DORE, SP算法與IDET-k算法的準(zhǔn)確重構(gòu)率，可以看出 IDET-k比DORE準(zhǔn)確重構(gòu)率高，稀疏重構(gòu)性能更好；在m/n比較大時(shí)，SP比IDET-k稀疏重構(gòu)性能更好。從圖3可以看出，所有算法中DORE算法稀疏重構(gòu)性能最差，閾值化迭代檢測(cè)估計(jì)的IDET-β, IDET-γ依賴(lài)于閾值化參數(shù)，參數(shù)越大算法稀疏重構(gòu)性能越好；SP算法在m/n＞0.4時(shí)顯示出更好的稀疏重構(gòu)性能。

圖2 算法IDET-β不同閾值化參數(shù)的準(zhǔn)確重構(gòu)率比較

圖3 算法DORE, SP,IDET的相變曲線比較

圖4 算法IDET-γ不同閾值化參數(shù)的準(zhǔn)確重構(gòu)率比較

圖5 算法DORE, SP與IDET -k的準(zhǔn)確重構(gòu)率比較

5.2 圖像重構(gòu)

本小節(jié)實(shí)驗(yàn)比較IDET算法與DORE, SP算法重構(gòu)Shepp-Logan Phantom圖像。測(cè)量向量y是2維離散傅里葉變換射線采樣系數(shù)。測(cè)量矩陣是采樣矩陣(部分離散傅里葉變換矩陣)，是稀疏化矩陣(逆 Harr小波變換)。Shepp-Logan Phantom圖像的Harr小波變換系數(shù)是稀疏的。稀疏重構(gòu)性能評(píng)價(jià)標(biāo)準(zhǔn)采用峰值信噪比(Peak Signal-to-Noise Ratio, PSNR)、迭代次數(shù)和 CPU運(yùn)行時(shí)間。峰值信噪比，其中0x是Harr小波變換系數(shù)，分別表示Shepp-Logan Phantom圖像的最大值、最小值。為公平比較算法，實(shí)驗(yàn)中迭代停止條件設(shè)最大迭代次數(shù)為1000或相對(duì)誤差為：。對(duì)圖像大小為256×256，設(shè)e =0.01, β=0.8, γ=0.8。圖 6顯示的是圖像射線采樣數(shù)為35～50時(shí)IDET算法與DORE, SP算法的重構(gòu)結(jié)果比較。IDET的3個(gè)實(shí)現(xiàn)算法IDET-k, IDET-β, IDET-γ重構(gòu)圖像的 PSNR都要比 DORE, SP算法大。算法 SP,IDET-β迭代次數(shù)要比其他算法少，IDET-k在射線采樣數(shù)比較高時(shí)，其迭代次數(shù)下降很明顯。算法IDET-γ和DORE在很多情況下維持比較高的迭代次數(shù)，但就 CPU 運(yùn)行時(shí)間而言，IDET-γ跟 SP,IDET-β, IDET-k一樣要比DORE算法少很多。

圖6 重構(gòu)Shepp-Logan Phantom圖像的峰值信噪比PSNR、迭代次數(shù)和CPU運(yùn)行時(shí)間比較

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

本文研究壓縮傳感的稀疏信號(hào)重構(gòu)算法，把貪婪算法分為兩類(lèi)：OST與TST。受ISD算法思想的啟發(fā)，本文提出一種結(jié)合OST和TST的貪婪算法框架IDET。IDET算法與傳統(tǒng)的TST不同之處在于采用OST作為支持集檢測(cè)的參考，可以根據(jù)稀疏信號(hào)的特征設(shè)計(jì)相應(yīng)的支持集檢測(cè)方法。針對(duì)快速衰減信號(hào)，IDET的實(shí)現(xiàn)算法設(shè)計(jì)了 3種檢測(cè)IHT迭代步的方法。實(shí)驗(yàn)結(jié)果表明，IDET實(shí)現(xiàn)算法比 DORE算法、SP算法(大多數(shù)情況下)具有更好的稀疏重構(gòu)性能。貪婪算法以其快速、易于實(shí)現(xiàn)(特別是對(duì)大規(guī)模應(yīng)用)的特點(diǎn)在壓縮傳感研究領(lǐng)域得到廣泛的關(guān)注，如國(guó)內(nèi)的研究[24]。IHT之類(lèi)的OST算法實(shí)現(xiàn)簡(jiǎn)單，但其收斂比較慢。本文提出的IDET實(shí)現(xiàn)算法是一種比DORE算法更具優(yōu)勢(shì)的IHT加速算法。根據(jù)IDET算法思想，我們可以設(shè)計(jì)更多的OST加速算法。ISD算法在理論與實(shí)踐上表明重構(gòu)相同稀疏度的稀疏信號(hào)所需的測(cè)量次數(shù)比 BP算法更少，為此，研究IDET算法在理論上減少測(cè)量次數(shù)成為新的方向。

[1] Candes E, Romberg J, and Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.

[2] Donoho D. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[3] Bajwa W, Leus G, Scaglione A, et al.. Guest editorial: special issue on compressive sensing in communications[J]. Physical Communication, 2012, 5(2): 61-63.

[4] Allstot D, Rovatti R, and Setti G. Editorial: special issue of compressive sensing[J]. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2012, 2(3): 337-339.[5] Ahmad F, Arce G, Narayanan R, et al.. Special section guest editorial: compressive sensing for imaging[J]. Journal of Electronic Imaging, 2013, 22(2): 020901-1-020901-2.

[6] Chen S, Donoho D, and Saunders M. Atomic decomposition by basis pursuit[J]. SIAM Review, 2001, 43(1): 129-159.

[7] Qaisar S, Bilal R, Iqbal W, et al.. Compressive sensing: from theory to applications, a survey[J]. Journal of Communications and Networks, 2013, 15(5): 443-456.

[8] Ji S, Xue Y, and Carin L. Bayesian compressive sensing[J].IEEE Transactions on Signal Processing, 2008, 56(6):2346-2356.

[9] Tropp T and Gilbert A. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12):4655-4666.

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

[11] Needell D and Tropp J. CoSaMP: iterative signal recovery from incomplete and inaccurate samples[J]. Communications of the ACM, 2010, 53(12): 93-100.

[12] Donoho D, Tsaig Y, Drori I, et al.. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2012, 58(2): 1094-1121.

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

[14] Qiu K and Dogandzic A. Sparse signal reconstruction via ECME hard thresholding[J]. IEEE Transactions Signal Processing, 2012, 60(9): 4551-4569.

[15] Maleki A and Donoho D. Optimally tuned iterative reconstruction algorithms for compressed sensing[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2):330-341.

[16] Wang Y and Yin W. Sparse signal reconstruction via iterative support detection[J]. SIAM Journal on Imaging Sciences,2010, 3(3): 462-491.

[17] 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.

[18] Beck A and Teboulle M. A fast iterative shrinkage thresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2(1): 183-202.

[19] Blumensath T. Accelerated iterative hard thresholding[J].Signal Processing, 2012, 92(3): 752-756.

[20] Amini A, Babaie-Zadeh M, and Jutten C. A fast method for sparse component analysis based on iterative detectionestimation[C]. International Workshop on Bayesian Inference and Maximum Entropy Methods in Science and Engineering,Paris, France, 2006: 123-130.

[21] Sturm B. Sparse vector distributions and recovery from compressed sensing[OL]. http://arxiv.org/pdf/1103.6246v2,2013.10.

[22] Zhang X, Wen J, Han Y, et al.. An improved compressive sensing reconstruction algorithm using linear non-linear mapping[C]. Proceedings of Information Theory and Applications Workshop, La Jolla, CA, USA, 2011: 1-7.

[23] 宋和平. 稀疏信號(hào)重構(gòu)的貪婪算法及其應(yīng)用[D]. [博士論文],中山大學(xué), 2011.Song He-ping. Greedy algorithms with application to sparse signal recovery[D]. [Ph.D.dissertation], Sun Yat-Sen University, 2011.

[24] 劉記紅, 黎湘, 徐少坤, 等. 基于改進(jìn)正交匹配追蹤算法的壓縮感知雷達(dá)成像方法[J]. 電子與信息學(xué)報(bào), 2012, 34(6):1344-1350.Liu Ji-hong, Li Xiang, Xu Shao-kun, et al.. Compressed sensing radar imaging methods based on modified orthogonal matching pursuit algorithms[J]. Journal of Electronics ＆amp;Information Technology, 2012, 34(6): 1344-1350.