壓縮感知中的概率約束優化模型及其D.C.近似

任詠紅, 曹麗娜, 姜 歡， 曲文靜

(遼寧師范大學 數學學院,遼寧 大連 116029)

?

壓縮感知中的概率約束優化模型及其D.C.近似

任詠紅, 曹麗娜, 姜 歡， 曲文靜

(遼寧師范大學 數學學院,遼寧 大連 116029)

帶有噪聲的壓縮感知信號重建模型可表示為l1-范數問題.為了滿足使用少量觀測值重構出高精度的圖像，在設置觀測矩陣時需要滿足受限等距性(RIP)和非相干性，然而判斷一個矩陣的RIP是非常困難的.針對觀測矩陣的不確定性，將該模型轉化為具有概率約束的隨機優化模型，即在約束條件以很大的概率被滿足的情況下，求解最小l1-范數問題.構建了概率約束函數的一個D.C.近似函數，討論了函數的性質，建立了相應的D.C.近似問題，證明了D.C.近似問題與概率約束優化問題的等價性.

壓縮感知；概率約束；D.C.近似

近年來,信號處理領域出現了一種新穎的理論——壓縮感知(Compressive Sensing)或叫壓縮采樣. 壓縮感知的核心是利用特定矩陣把一個K-稀疏或可壓縮的高維信號投影到低維空間上，然后利用信號的稀疏先驗條件，通過一定的線性或非線性的重建模型重建出原始信號.而壓縮感知信號重建模型可表示成l0-范數問題：

(1)

其中，Φ∈M×N為觀測矩陣，x∈N,b∈M是觀測值，N>M.

問題(1)是NP-hard問題，直接求解較困難，有效的求解方法是匹配追蹤系列算法[1-3]，此算法重建速度快，但精確度低且需要測量的數據多.

Donoho等[4-5]建立了問題(1)的等價問題l1-范數問題：

(2)

而在現實測量過程中，常存在各種各樣噪聲的干擾，破壞了信號的稀疏特性.因此,壓縮感知需要恢復算法具有穩定性和對噪聲的魯棒特性.帶有噪聲ε≥0的壓縮感知信號重建模型可以表示為

(3)

關于問題(3)的求解，常集中于凸優化算法[6-9].凸優化算法重建誤差小，重建效果好，但是，速度慢,算法的復雜度高.

為了滿足使用少量觀測值重構出高精度的圖像，在設置觀測矩陣Φ時需要滿足受限等距性(RIP)和非相干性，然而判斷一個矩陣的RIP是非常困難的.本文針對觀測矩陣的不確定性，將該模型轉化為具有概率約束的隨機優化模型，即在約束條件以很大的概率被滿足的情況下，求解最小l1-范數問題.構建了概率約束函數的一個D.C.近似函數，討論了近似函數的性質，建立了相應的D.C.近似問題，證明了D.C.近似問題與概率約束優化問題的等價性.

1 概率約束優化模型

考慮帶有噪聲的壓縮感知信號重建模型：

其中,ε≥0代表噪聲.

基于觀測矩陣Φ的不確定性，將該模型轉化為具有概率約束的隨機優化模型如下：

(CCP)

其中,x∈X?N，‖·‖1為l1-范數，‖·‖2為l2-范數，Pr為概率，b∈M，ξ是支撐集Ξ上的隨機向量，Φ:Ξ→M×N(M>N)為隨機矩陣，ε≥0代表噪聲，α∈(0,1)是置信水平.

問題(CCP)是具有概率約束的隨機優化問題，求解該類問題具有代表性的方法主要有凸近似方法[10]、D.C.近似方法[11]等.

考慮問題(CCP), 若記

其中,

則問題(CCP)可變形為

(P)

2 D.C.近似問題

對?t>0，定義函數

記

π(z,ε,t)=φ1(z,ε,t)-φ2(z,ε,t), ?t>0.

由于φ1(z,ε,t)和φ2(z,ε,t)都是關于z的凸函數，則π(z,ε,t)是關于z的D.C.函數.

當t>0時，對所有的z∈有

π(z,ε,t)≥1(ε,+∞)(z).

則π(z,ε,t)是特征函數1(ε,+∞)(z)的一個凸保守的D.C.近似(如圖1和圖2所示).

圖1 特征函數1(ε,+∞)(z)Fig.1 Characteristic function 1(ε,+∞)(z)

函數φ1(z,ε,t)和φ2(z,ε,t) D.C.近似函數π(z,ε,t)圖2 特征函數1(ε,+∞)(z)的D.C.近似Fig.2 D.C. approximation function of characteristic function 1(ε,+∞)(z)

下述命題描述了函數π(z,ε,t)的性質.

命題2.1 對于?t>0，函數π(z,ε,t)關于t是非減的.

證 對?t>0，則有

則對于?t1>t2>0，有

因此，當t>0時，π(z,ε,t)關于t是非減的.

證畢.

記

(4)

假設1X?N是凸緊致子集，ξ的支撐集Ξ是包含于k的閉集，Θ是使得X?Θ的一個有界開集.

證 由命題2.1可知，當t>0時，對?z∈,π(z,ε,t)關于t是非減的，又由于

證畢.

引理2.2 若假設1和假設2成立，則g1(x,ε,t)在Θ×(-t,+t)上是可微的，并且有

xg1(x,ε,t)=E[‖2Φ(ξ)T(Φ(ξ)x-b)·1(ε-t,+∞)(‖Φ(ξ)x-b)],

證 記

由于f(z)=[t+z-ε]+除了在點z=ε-t處都是可微的.則當z≠ε-t時，有

f′(z)=1(ε-t,+∞)(z).

xg1(x,ε,t)=E[‖2Φ(ξ)T(Φ(ξ)x-b)·1(ε-t,+∞)(‖Φ(ξ)x-b)]，

由于g2(x,ε)=g1(x,ε,t)，同理可得

xg2(x,ε)=E[‖2Φ(ξ)T(Φ(ξ)x-b)·1(ε,+∞)(‖Φ(ξ)x-b)].

證 由引理2.1，

由引理2.2得

證畢.

[1] MALLAT S,ZHANG Z.Matching pursuits with time-frequency dictionaries[J].IEEE Transaction on Signal Processing,1993,41(12):3397-3415.

[2] TROPP J,GILBERT A.Signal recover from random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2008,53(12):4655-4666.

[3] NEEDELL D,VERSHYNIN R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J].Foundations of Computational Mathematics,2009,9(3):317-334.

[4] CHEN S S,DONOHO D L,SAUNDERS M A.Atomic decomposition by basis pursuit[J].SIAM Review,2001,43(1):129-159.

[5] DONOHO D L,ELAD M,TEMLYAKOV V.Stable recovery of sparse overcomplete representations in the presence of noise[J].IEEE Transactions on Information Theory, 2006,52(1):6-18.

[6] KIM S, KOH K, LUSTIG M,et al.An interior-point method for large-scalel1regularized least squares[J].IEEE Journal of Selected Topics in Signal Processing,2007,1(4):606-617.

[7] BOYD S,VANDENBERGHE L.Convex optimization[M].Cambridge, UK:Cambridge University Press, 2004:561-615.

[8] FIQUEIREDO M A T,NOWAK R D,WRIGHT S J.Gradient projection for sparse reconstruction:application to compressed sensing and other inverse problems[J].IEEE Journal of Selected Topics in Signal Processing,2007,1(4):586-598.

[9] DONOHO D L,TSAIG Y.Fast solution ofl1-norm minimization problems when the solution may be sparse[R].Palo Alto:Department of Statistics,Stanford University,USA,2008.

[10] NEMIROVSKI A,SHAPIRO A．Convex approximations of chance constrained programs[J].SIAM Journal on Optimization,2006,17(4):969-996．

[11] HONG L J,YANG Y,ZHANG L W.Sequential convex approximations to joint chance constrained programs:a monte carlo approach[J].Operation Research,2011,59(3):617-630．

Probability constrained optimization model and its D.C. approximation in compressed sensing

RENYonghong,CAOLina,JIANGHuan,QUWenjing

(School of Mathematics, Liaoning Normal University, Dalian 116029, China)

Compressed sensing signal reconstruction with noise can be expressed asl1-norm problem. In order to reconstruct a high-precision image with a small amount of observations, it is necessary to satisfy the restricted isometric (RIP) and non-coherence when setting the observation matrix. However, it is very difficult to judge the RIP of a matrix. In view of the uncertainty of the observation matrix, thel1-norm problem is transformed into a stochastic optimization model with probability constraint in this paper. That is, the minimuml1-norm problem is solved when the constraint is satisfied with a large probability. A D.C. approximation function of the probability constraint function is constructed. The properties of the function are discussed and the corresponding D.C. approximation problem is established. The equivalence between the D.C. approximation and the probability constrained optimization problem is proved.

compressed sensing;probability constraint;D.C. approximation

2017-01-20

遼寧省教育廳科學技術研究一般項目(L2015291)；遼寧省自然科學基金指導計劃項目(201602459);國家自然科學基金資助項目(11671184)

任詠紅(1973-)，女，遼寧朝陽人，遼寧師范大學副教授，博士.E-mail:ryhong@lnnu.edu.cn

1000-1735(2017)02-0154-05

10.11679/lsxblk2017020154

O221.5

A