基于SCAD的壓縮感知閾值迭代算法的收斂性分析?

張 會(huì) 張 海 勾 明

(1-西北大學(xué)數(shù)學(xué)學(xué)院，西安 710069;2-中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研究所，北京 100190)

1 引言

壓縮感知[1,2]是一種全新的稀疏信號(hào)重構(gòu)技術(shù)．它能在完全重建的前提下，以遠(yuǎn)小于傳統(tǒng)的奈奎斯特采樣的方式獲取信息．其本質(zhì)是利用信息表示的稀疏性，將采樣與壓縮合并進(jìn)行的信息獲取方式．壓縮感知的意義在于突破傳統(tǒng)的采樣方式，以更經(jīng)濟(jì)的形式獲取信息，從而為高復(fù)雜性信息的獲取、處理與應(yīng)用帶來可能．近年來在信號(hào)處理、圖像處理和統(tǒng)計(jì)機(jī)器學(xué)習(xí)及其它多個(gè)領(lǐng)域獲得廣泛應(yīng)用[3,4]．

壓縮感知的數(shù)學(xué)描述為：假設(shè)有一個(gè)有限長度的信號(hào)x,x∈RN，該信號(hào)在某一下可表示為x= Ψs，這里Ψ =(θ1,θ2,···,θN)，s稱為基的系數(shù)，s至多有k個(gè)非零元素(k為s的稀疏度)．對(duì)于此信號(hào)，通過測(cè)量矩陣Θ來對(duì)x進(jìn)行觀測(cè)(測(cè)量)，假定得出的觀測(cè)值為y,y∈Rp，即滿足

通常稱Φ=ΘΨ,Φ∈Rp×N為傳感矩陣，當(dāng)k,p,N?→∞時(shí)，

ρ是稀疏性的一種度量，δ是欠采樣的比例．我們希望從觀測(cè)數(shù)據(jù)y恢復(fù)稀疏未知向量s，進(jìn)而恢復(fù)信號(hào)x．此問題從數(shù)學(xué)上可建模為下述L0問題個(gè)正交基

其中‖s‖0為L0范數(shù)，表示向量s的非零分量的個(gè)數(shù)．上述問題往往對(duì)應(yīng)于一個(gè)NP難問題，基于此，通常將其轉(zhuǎn)化為L1問題來求解

從而將一個(gè)NP難問題通過凸松弛求解．至此后，許多研究者關(guān)注于這類問題的研究[5-7]，這一思想也成為當(dāng)今流行的稀疏信號(hào)重建策略．

在特征提取研究中，F(xiàn)an和Li[8]提出了SCAD變量選擇方法，應(yīng)用于高維數(shù)據(jù)處理．在統(tǒng)計(jì)的意義下，F(xiàn)an和Li證明了SCAD具有變量選擇的稀疏性，無偏性和連續(xù)性，并證明了SCAD具有好的理論性質(zhì)，滿足所謂的Oracle性質(zhì)．因?yàn)槠淞己玫慕y(tǒng)計(jì)性質(zhì)，SCAD自提出后引起廣泛關(guān)注．為研究在更少采樣下信號(hào)重建工作，文獻(xiàn)[9]將非凸的SCAD罰函數(shù)引入壓縮感知問題的研究，研究表明基于SCAD的信號(hào)重建策略與現(xiàn)有方法相比較，在沒有噪聲影響時(shí)，具有很好的稀疏信號(hào)重建能力；而當(dāng)有觀測(cè)有噪聲時(shí)，具有更好的穩(wěn)健性．

經(jīng)典地，求解壓縮感知算法包括：OMP類算法，如OMP[10,11]、CoSaMP[12]、Subspace pursuit[13]、StOMP[14]、ROMP[15]等；重迭代算法，如The reweightedl1-minimization[16]、IRLS[17,18]等．OMP類算法主要用于求解問題(2)，此類算法在信號(hào)稀疏度比較大時(shí)收斂速度很快．重迭代算法主要用于求解問題(3)．OMP類算法是一種閾值迭代算法，閾值迭代算法可以高效、快速、精確求解壓縮感知問題．因此，對(duì)閾值迭代算法的研究很有價(jià)值．文獻(xiàn)[19]分析了凸閾值迭代算法以及非凸閾值迭代算法的收斂性．我們?cè)谖墨I(xiàn)[9]給出了高效的閾值迭代算法，但未給出其收斂性分析．本文是文獻(xiàn)[9]工作的延續(xù)，基于SCAD的壓縮感知閾值迭代算法，從理論上分析其收斂性，給出其收斂到稀疏解的充分條件，并證明其收斂速率達(dá)到指數(shù)階．

進(jìn)一步，眾所周知，在稀疏信號(hào)重建問題中，稀疏性與欠采樣的權(quán)衡很重要，快速迭代算法是解決稀疏信號(hào)重建問題的一種算法，但是該算法在稀疏性與欠采樣的權(quán)衡方面效果很差，不能完全重建稀疏信號(hào)．Donoho等人[20]研究發(fā)現(xiàn)，基于逼近Belief Propagation算法改進(jìn)的AMP算法的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)低于Belief Propagation算法，同時(shí)通過實(shí)驗(yàn)驗(yàn)證了基于AMP改進(jìn)的Soft閾值迭代算法在稀疏性與欠采樣的權(quán)衡方面較原閾值迭代算法有很大的改善，新方法在稀疏性與欠采樣的平衡方面與凸優(yōu)化相當(dāng)，估計(jì)稀疏向量能力有很大的提高．為進(jìn)一步提高SCAD閾值迭代算法重建稀疏信號(hào)的能力，本文研究基于AMP改進(jìn)的SCAD閾值迭代算法，給出基于AMP改進(jìn)的SCAD閾值迭代算法，并證明其收斂性．

2 基于SCAD的壓縮感知閾值迭代算法

本節(jié)首先給出基于SCAD的壓縮感知閾值迭代算法．對(duì)于一個(gè)有限長度的信號(hào)x?，s?為x?在正交基下的系數(shù)，Φ為傳感矩陣，基于SCAD的壓縮感知的數(shù)學(xué)模型為

其中

我們?cè)谖墨I(xiàn)[9]中給出了SCAD閾值函數(shù)的形式，SCAD閾值迭代算法可表示為

這里Sn(·)是SCAD閾值函數(shù)，s(n)是第n次迭代的估計(jì)值，r(n)是第n次迭代的殘差，ΦT是Φ的轉(zhuǎn)置．

記?i為Φ的第i列向量，s(i)為s的第i個(gè)元素，J為指標(biāo)集．定義

s(i)的主動(dòng)集(若s的元素s(j)通過閾值，則把s(j)放入集合I中(即j∈I)，集合I就稱為主動(dòng)集)記為I(i)，s?的主動(dòng)集記為I?，k為s?的稀疏度(即s?至多有k個(gè)非零的元素)．Φ的相關(guān)性記為

定理1假定，且對(duì)任意的1≤i＜k，都有

成立，則SCAD閾值迭代算法至多需要步就能恢復(fù)重建稀疏信號(hào)s?，并且當(dāng)t≥L時(shí)，有

且對(duì)任意的j，有

其中

這里c為大于零的常數(shù)．

注1稀疏信號(hào)s?的稀疏度k通常不會(huì)很大，傳感矩陣Φ的相關(guān)性μ的大小可以控制，因此，假定是可行的．

注2定理1表明SCAD閾值迭代算法只需有限步就可以找到正確的主動(dòng)集，并且SCAD閾值迭代算法一旦找到正確的主動(dòng)集，就能以指數(shù)階的速率收斂到精確解．

3 定理1的證明

本節(jié)給出定理1的證明．記

這里s?是最優(yōu)值，s(i)是第i步的估計(jì)值，z(i+1),w(i)的第j個(gè)元素記為z(i+1)(j),w(i)(j)，不失一般性，我們假設(shè)s?的元素按絕對(duì)值大小遞減排列(即s?的前k個(gè)元素非零，且|s?(1)|≥|s?(2)|≥···≥|s?(k)|≥0)，迭代初始值選為s(0)=0．為了證明定理1，我們需要以下三個(gè)引理．

引理1假定，則s?的最大元素s?(1)在第1步迭代后進(jìn)入主動(dòng)集中，并且對(duì)任意的j，有

證明

上式第三個(gè)等式成立是由于我們假設(shè)迭代初始值為零(即s(0)(j)=0)，則就有I(0)為空集，上式第四個(gè)不等式成立是由于當(dāng)j∈I?I(0)時(shí)，w(0)(j)=s?(j)，且有|s?(j)|≤|s?(1)|．這里我們只考慮s?的最大元素s?(1)在第1步迭代后是否進(jìn)入主動(dòng)集中，對(duì)于1＜i≤k不做討論．當(dāng)i＞k時(shí)，有

由于假設(shè)，所以有kμ＜1?kμ，故

因此，s?的最大元素s?(1)在第1步迭代后進(jìn)入主動(dòng)集中，并且有

引理2假定當(dāng)r＜k時(shí)，在第m步迭代后s?(1),s?(2),···,s?(r)都在主動(dòng)集中，并且對(duì)任意的j，有

如果，則在第m+n步迭代后，s?(1),s?(2),···,s?(r)仍在主動(dòng)集中，并且對(duì)任意的j，有

證明 我們用數(shù)學(xué)歸納法證明這個(gè)引理，首先證明，當(dāng)n=1時(shí)結(jié)論成立．

上式第二個(gè)不等式成立是由于當(dāng)j∈I(m)時(shí)，w(m)(j)=s?(j)?z(m)(j)，我們假定當(dāng)r＜k時(shí)，在第m步迭代后s?(1),s?(2),···,s?(r)都在主動(dòng)集中，即{1,2,···,r}?I(m)，故當(dāng)j∈I?I(m)時(shí)，w(m)(j)=s?(j)，并且|s?(j)|≤|s?(r+1)|．下面我們將證明s?的前r個(gè)元素在主動(dòng)集中．當(dāng)i∈{1,2,···,r}時(shí)

上式第四個(gè)不等式成立是由于有下面事實(shí)成立，令fs=α+α2+···+αs+βαs+1，若β(1?α)＞1，則對(duì)任意的s有fs＜βα成立，取s=1即可得到第四個(gè)不等式．當(dāng)i＞k時(shí)

因此，s?的前r個(gè)元素在主動(dòng)集中．從而n=1時(shí)結(jié)論成立．

接下來，我們假定第m+n步迭代結(jié)論成立，證明第m+n+1步迭代結(jié)論成立，與n=1時(shí)證明過程類似有

易得

當(dāng)i＞k時(shí)

由于

因此，s?的前r個(gè)元素在主動(dòng)集中，從而第m+n+1步迭代結(jié)論成立．

引理3假定，當(dāng)r＜k時(shí)

成立，并且在第m步迭代后s?(1),s?(2),···,s?(r)都在主動(dòng)集中，如果對(duì)任意的j，有

那么，再經(jīng)過lr步迭代后，s?(r+1)將進(jìn)入主動(dòng)集中，并且對(duì)任意的j，有

證明 令n=lr，由引理2可得

同引理2證明，得

當(dāng)i＞k時(shí)

由于

所以在第m+lr步迭代后，s?(r+1)在主動(dòng)集中．下面我們給出算法的誤差界，對(duì)任意的j，有

定理1的證明我們?nèi)圆捎脭?shù)學(xué)歸納法證明．由引理1、引理2、引理3得，當(dāng)?shù)綌?shù)i=1時(shí)，由引理1可知s?的最大元素被找到，假定s?(1),s?(2),···,s?(r)在主動(dòng)集中，則由引理2可知這些元素將會(huì)一直在主動(dòng)集中，由引理3我們知道經(jīng)過lr步迭代后，s?(r+1)將進(jìn)入主動(dòng)集中，并且再多迭代一步，估計(jì)值的每個(gè)元素與最優(yōu)值的誤差界小于

這個(gè)過程可以重復(fù)進(jìn)行，故SCAD閾值迭代算法至多需要步就能恢復(fù)重建稀疏信號(hào)s?．最后，我們證明當(dāng)s?的所有元素在主動(dòng)集中時(shí)，迭代估計(jì)值與最優(yōu)值的誤差以指數(shù)階的速率趨于零，證明如下，我們假定在第m步迭代后s?(1),s?(2),···,s?(k)都在主動(dòng)集中，并且對(duì)任意的j，有

如果，則在第m+n步迭代后s?(1),s?(2),···,s?(k)仍在主動(dòng)集中，并且對(duì)任意的j，有

與引理2類似，我們采用數(shù)學(xué)歸納法證明．假設(shè)第m+n步迭代結(jié)論成立，即在第m+n步迭代后s?(1),s?(2),···,s?(k)仍在主動(dòng)集中(即I??I(m+n))，并且對(duì)任意的j，有

成立，那么在第m+n+1步迭代后，由引理2可知s?(1),s?(2),···,s?(k)仍在主動(dòng)集中，并且對(duì)任意的j，我們有

故第m+n+1步迭代結(jié)論成立，從而結(jié)論成立．我們知道經(jīng)過L步迭代后s?(1),s?(2),···,s?(k)都在主動(dòng)集中，故取m=L,m+n=t，則可以得到

從而定理得證．

4 基于AMP改進(jìn)的SCAD閾值迭代算法

如引言所述，迭代算法能夠快速求解稀疏信號(hào)重建問題，但是該算法在稀疏性與欠采樣的權(quán)衡方面效果很差，不能完全重建稀疏信號(hào)，SCAD閾值迭代算法也存在這方面不足．為進(jìn)一步提高SCAD閾值迭代算法重建稀疏信號(hào)的能力，本文研究基于AMP改進(jìn)的SCAD閾值迭代算法．本節(jié)首先給出基于AMP改進(jìn)的SCAD閾值迭代算法，然后對(duì)其算法收斂性開展研究．

給定初始值s(0)=0，基于AMP改進(jìn)的SCAD閾值迭代算法可表示為

這里，對(duì)于一個(gè)向量

從而可得

對(duì)于不可導(dǎo)的點(diǎn)，以該點(diǎn)的次導(dǎo)數(shù)作為其導(dǎo)數(shù)，所以

記

一般情況下，k遠(yuǎn)小于p，所以e＜1．

定理2假定kμ＜ε(ε為正數(shù))，且對(duì)任意的1≤i＜k，都有

成立，則基于AMP改進(jìn)的SCAD閾值迭代算法至多需要+1步(li為正整數(shù))就能恢復(fù)重建稀疏信號(hào)s?，并且當(dāng)t≥L時(shí)，有

且對(duì)任意的j，有

注3定理2表明基于AMP改進(jìn)的SCAD閾值迭代算法只需有限步就可以找到正確的主動(dòng)集，并且迭代估計(jì)值與真實(shí)值的誤差有界．

5 定理2的證明

本節(jié)給出定理2的證明．首先，記

為了證明定理2，我們需要以下幾個(gè)引理．

基于AMP改進(jìn)的SCAD閾值迭代算法與SCAD閾值迭代算法第一步迭代相同，所以由引理1可得若，則s?的最大元素s?(1)在第1步迭代后進(jìn)入主動(dòng)集中，并且對(duì)任意的j，有

引理4假定，則在第n+1歩迭代后，s?(1)仍在主動(dòng)集中，并且對(duì)任意的j，有

證明 我們用數(shù)學(xué)歸納法證明這個(gè)引理，首先證明當(dāng)n=1時(shí)結(jié)論成立．

令ε(1)1=，若ε1≤ε(1)1，則

下面我們將證明s?的第1個(gè)元素仍在主動(dòng)集中．當(dāng)i=1時(shí)

當(dāng)i＞k時(shí)

由于

因此，s?的第1個(gè)元素仍在主動(dòng)集中．從而n=1時(shí)結(jié)論成立．

接下來，我們假定n＜t時(shí)結(jié)論成立，證明n=t時(shí)結(jié)論成立，與n=1時(shí)證明過程類似，我們有

由于e＜1，所以存在，令

若ε1≤ε(t)1，則

易得

當(dāng)i＞k時(shí)

由于

因此，s?的第1個(gè)元素仍在主動(dòng)集中，從而第t+1步迭代結(jié)論成立．令

引理結(jié)論成立．

引理5假定

成立，那么再經(jīng)過l1步迭代后，s?(2)將進(jìn)入主動(dòng)集中，并且對(duì)任意的j，有

證明令n=l1，由引理4可得

同引理4證明，得

當(dāng)i＞k時(shí)

由于

因此，s?的第2個(gè)元素在主動(dòng)集中，并且對(duì)任意的j，有

令

可得若kμ＜ε(1)2，則對(duì)任意的j，有

從而引理成立．

引理6假定kμ＜ε2≤ε(1)2，則在第l1+n+1歩迭代后，s?(1),s?(2)仍在主動(dòng)集中，并且對(duì)任意的j，有

證明 我們用數(shù)學(xué)歸納法證明這個(gè)引理，首先當(dāng)n=1時(shí)，由引理5的證明可得，若kμ＜ε(1)

2，則有

下面我們將證明s?的第2個(gè)元素仍在主動(dòng)集中．當(dāng)i=2時(shí)

當(dāng)i＞k時(shí)

由于

因此，s?的第2個(gè)元素仍在主動(dòng)集中．從而n=1時(shí)結(jié)論成立．

接下來，我們假定n＜t時(shí)結(jié)論成立，證明n=t時(shí)結(jié)論成立，與n=1時(shí)證明過程類似，有

令

若ε2≤ε(t)2，則

易得

當(dāng)i＞k時(shí)

由于

因此，s?的第2個(gè)元素仍在主動(dòng)集中，從而第t+l1+1步迭代結(jié)論成立．令ε2=，引理結(jié)論成立．

引理7假定

成立，那么再經(jīng)過l2步迭代后，s?(3)將進(jìn)入主動(dòng)集中，并且對(duì)任意的j，有

證明 令n=l2，由引理6可得

令

可得

同引理6證明，得

當(dāng)i＞k時(shí)

由于

因此，s?的第3個(gè)元素在主動(dòng)集中，并且對(duì)任意的j，有

可得若kμ＜ε(1)3，則對(duì)任意的j，有

從而引理成立．

定理2的證明由引理4、引理5、引理6、引理7，依此類推可以得到ε1,ε2,···,εk(ε1≥ε2≥···≥εk),α1,α2,···,αk?1，以及l(fā)1,l2,···,lk?1．若ε≤εk，則當(dāng)kμ＜ε(ε為正數(shù))，且對(duì)任意的

成立時(shí)，基于AMP改進(jìn)的SCAD閾值迭代算法至多需要步(li為正整數(shù))就能恢復(fù)重建稀疏信號(hào)s?，并且當(dāng)t≥L時(shí)，令就有I??I(t)，且對(duì)任意的j，有

從而定理得證．

6 結(jié)論

壓縮感知是一種全新的稀疏信號(hào)重構(gòu)技術(shù)，其本質(zhì)是利用信息表示的稀疏性，將采樣與壓縮合并進(jìn)行的信息獲取方式，開展其快速重建算法研究有著重要的意義．閾值迭代算法是一種高效、快速、重建精度高的求解壓縮感知問題的算法．基于非凸罰函數(shù)的壓縮感知是近期研究熱點(diǎn)之一．本文研究基于SCAD罰函數(shù)的閾值迭代算法的收斂性，證明了在信號(hào)稀疏度和傳感矩陣的相關(guān)性滿足一定條件的情況下，SCAD閾值迭代算法至多需要有限步就能精確重建稀疏信號(hào)，并且一旦找到精確解，其迭代估計(jì)值與最優(yōu)值的誤差以指數(shù)階的速率趨于零．從而從理論上為基于SCAD罰函數(shù)的閾值迭代算法提供了支撐．由于快速迭代算法在稀疏性與欠采樣的權(quán)衡方面效果很差，而AMP算法在稀疏性與欠采樣的權(quán)衡方面有很大的改善，重建稀疏信號(hào)能力有很大的提高．因此，本文研究基于AMP改進(jìn)的SCAD閾值迭代算法，并證明其收斂性．本文結(jié)果可推廣到其它非凸閾值迭代算法．

參考文獻(xiàn)：

[1]Candes E,Romberg J,Tao T.Stable signal recovery from incomplete and inaccurate measurements[J].Communications on Pure and Applied Mathematics,2006,59(8):1207-1223

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

[3]Euder H G.On compressive sensing applied to radar[J].Signal Processing,2010,90(5):1402-1414

[4]Majumdar A,Ward K.Compressed sensing of color images[J].Signal Processing,2010,90(12):3122-3127[5]Chen S,Donoho D,Saunders M.Atomic decomposition by basis pursuit[J].SIAM Journal on Scientific Computing,1998,20(1):33-61

[6]Tibshirani R.Regression shrinkage and selection via the lasso[J].Journal of the Royal Statistical Society,1996,58(1):267-288

[7]Xu Z B,Zhang H,Wang Y,et al.Lregularizer[J].Science in China:Information Sciences,2010,53(6):1159-1169

[8]Fan J Q,Li R Z.Statistical chanllenges with high dimensionality:feature selection in knowledge discovery[OL].arXiv preprint math/0602133,2006

[9]張海，梁勇，徐宗本，等.基于SCAD罰函數(shù)的有噪壓縮感知集[J].數(shù)學(xué)學(xué)報(bào)，2013,56(5):767-776 Zhang H,Liang Y,Xu Z B,et al.Compressive sensing with noise based on SCAD penalty[J].Acta Mathematica Sinica,2013,56(5):767-776

[10]Pati Y,Rezaifar R,Krishnaprasad P.Orthogonal matching pursuit:recursive function approximation with application to wavelet decomposition[C]//Signals,Systems and Computers,1993,1993 Conference Record of the Twenty-Seventh Asilomar Conference on IEEE,1993:40-44

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

[12]Needell D,Tropp J A.CoSaMP:iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis,2008,26(3):301-321

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

[14]Donoho D L,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

[15]Needell D,Vershynin R.Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit[J].IEEE Journal of Selected Topics in Signal Processing,2010,4(2):310-316[16]Candes E,Wakin M B,Boyd S.Enhancing sparsity by reweightedL1minimization[J].Journal of Fourier Analysis and Applications,2008,14(5):877-905

[17]Gorodnitsky I F,Rao B D.Sparse signal reconstruction from limited data using FOCUSS:a reweighted minimum norm algorithm[J].IEEE Transaction on Signal Processing,1997,45(3):600-616

[18]Daubechies I,Devore R,Fornasier M,et al.Iteratively reweighted least squares minimization for sparse recovery[J].Communications on Pure and Applied Mathematics,2010,63(1):1-38

[19]Zeng J S,Lin S B,Xu Z B.Sparse solution of underdetermined linear equation via adaptively iterative thresholding[J].Signal Processing,2014,97:152-161

[20]Donoho D L,Maleki A,Montanari A.Message passing algorithms for compressed sensing[J].Proceedings of the National Academy of Sciences,2009,106(45):18914-18919