張 會 張 海 勾 明

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

1 引言

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

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

通常稱Φ=ΘΨ,Φ∈Rp×N為傳感矩陣，當k,p,N?→∞時，

ρ是稀疏性的一種度量，δ是欠采樣的比例．我們希望從觀測數據y恢復稀疏未知向量s，進而恢復信號x．此問題從數學上可建模為下述L0問題個正交基

其中‖s‖0為L0范數，表示向量s的非零分量的個數．上述問題往往對應于一個NP難問題，基于此，通常將其轉化為L1問題來求解

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

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

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

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

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

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

其中

我們在文獻[9]中給出了SCAD閾值函數的形式，SCAD閾值迭代算法可表示為

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

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

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

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

成立，則SCAD閾值迭代算法至多需要步就能恢復重建稀疏信號s?，并且當t≥L時，有

且對任意的j，有

其中

這里c為大于零的常數．

注1稀疏信號s?的稀疏度k通常不會很大，傳感矩陣Φ的相關性μ的大小可以控制，因此，假定是可行的．

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

3 定理1的證明

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

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

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

證明

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

由于假設，所以有kμ＜1?kμ，故

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

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

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

證明 我們用數學歸納法證明這個引理，首先證明，當n=1時結論成立．

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

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

因此，s?的前r個元素在主動集中．從而n=1時結論成立．

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

易得

當i＞k時

由于

因此，s?的前r個元素在主動集中，從而第m+n+1步迭代結論成立．

引理3假定，當r＜k時

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

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

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

同引理2證明，得

當i＞k時

由于

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

定理1的證明我們仍采用數學歸納法證明．由引理1、引理2、引理3得，當迭代步數i=1時，由引理1可知s?的最大元素被找到，假定s?(1),s?(2),···,s?(r)在主動集中，則由引理2可知這些元素將會一直在主動集中，由引理3我們知道經過lr步迭代后，s?(r+1)將進入主動集中，并且再多迭代一步，估計值的每個元素與最優(yōu)值的誤差界小于

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

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

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

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

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

從而定理得證．

4 基于AMP改進的SCAD閾值迭代算法

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

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

這里，對于一個向量

從而可得

對于不可導的點，以該點的次導數作為其導數，所以

記

一般情況下，k遠小于p，所以e＜1．

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

成立，則基于AMP改進的SCAD閾值迭代算法至多需要+1步(li為正整數)就能恢復重建稀疏信號s?，并且當t≥L時，有

且對任意的j，有

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

5 定理2的證明

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

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

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

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

證明 我們用數學歸納法證明這個引理，首先證明當n=1時結論成立．

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

下面我們將證明s?的第1個元素仍在主動集中．當i=1時

當i＞k時

由于

因此，s?的第1個元素仍在主動集中．從而n=1時結論成立．

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

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

若ε1≤ε(t)1，則

易得

當i＞k時

由于

因此，s?的第1個元素仍在主動集中，從而第t+1步迭代結論成立．令

引理結論成立．

引理5假定

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

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

同引理4證明，得

當i＞k時

由于

因此，s?的第2個元素在主動集中，并且對任意的j，有

令

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

從而引理成立．

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

證明 我們用數學歸納法證明這個引理，首先當n=1時，由引理5的證明可得，若kμ＜ε(1)

2，則有

下面我們將證明s?的第2個元素仍在主動集中．當i=2時

當i＞k時

由于

因此，s?的第2個元素仍在主動集中．從而n=1時結論成立．

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

令

若ε2≤ε(t)2，則

易得

當i＞k時

由于

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

引理7假定

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

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

令

可得

同引理6證明，得

當i＞k時

由于

因此，s?的第3個元素在主動集中，并且對任意的j，有

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

從而引理成立．

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

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

從而定理得證．

6 結論

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

參考文獻：

[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罰函數的有噪壓縮感知集[J].數學學報，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