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

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院,遼寧 大連 116029)

?

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

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

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院,遼寧 大連 116029)

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

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

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

(1)

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

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

Donoho等[4-5]建立了問(wèn)題(1)的等價(jià)問(wèn)題l1-范數(shù)問(wèn)題：

(2)

而在現(xiàn)實(shí)測(cè)量過(guò)程中，常存在各種各樣噪聲的干擾，破壞了信號(hào)的稀疏特性.因此,壓縮感知需要恢復(fù)算法具有穩(wěn)定性和對(duì)噪聲的魯棒特性.帶有噪聲ε≥0的壓縮感知信號(hào)重建模型可以表示為

(3)

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

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

1 概率約束優(yōu)化模型

考慮帶有噪聲的壓縮感知信號(hào)重建模型：

其中,ε≥0代表噪聲.

基于觀測(cè)矩陣Φ的不確定性，將該模型轉(zhuǎn)化為具有概率約束的隨機(jī)優(yōu)化模型如下：

(CCP)

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

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

考慮問(wèn)題(CCP), 若記

其中,

則問(wèn)題(CCP)可變形為

(P)

2 D.C.近似問(wèn)題

對(duì)?t>0，定義函數(shù)

記

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

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

當(dāng)t>0時(shí)，對(duì)所有的z∈有

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

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

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

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

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

命題2.1 對(duì)于?t>0，函數(shù)π(z,ε,t)關(guān)于t是非減的.

證 對(duì)?t>0，則有

則對(duì)于?t1>t2>0，有

因此，當(dāng)t>0時(shí)，π(z,ε,t)關(guān)于t是非減的.

證畢.

記

(4)

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

證 由命題2.1可知，當(dāng)t>0時(shí)，對(duì)?z∈,π(z,ε,t)關(guān)于t是非減的，又由于

證畢.

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

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

證 記

由于f(z)=[t+z-ε]+除了在點(diǎn)z=ε-t處都是可微的.則當(dāng)z≠ε-t時(shí)，有

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

遼寧省教育廳科學(xué)技術(shù)研究一般項(xiàng)目(L2015291)；遼寧省自然科學(xué)基金指導(dǎo)計(jì)劃項(xiàng)目(201602459);國(guó)家自然科學(xué)基金資助項(xiàng)目(11671184)

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

1000-1735(2017)02-0154-05

10.11679/lsxblk2017020154

O221.5

A