稀疏重構(gòu)算法

王汗三，陳 杰

(西安電子科技大學(xué)理學(xué)院，陜西西安 710071)

圖像恢復(fù)是通過計(jì)算機(jī)處理，對(duì)質(zhì)量下降的圖像加以重建或恢復(fù)的處理過程。因攝像機(jī)與物體相對(duì)運(yùn)動(dòng)、系統(tǒng)誤差、畸變、噪聲等因素的影響，使圖像往往不是真實(shí)景物的完善映像［1－3］。在遙感圖像處理中，為消除遙感圖像的失真、畸變，恢復(fù)目標(biāo)的反射波譜特性和正確的幾何位置，通常需要對(duì)圖像進(jìn)行恢復(fù)處理，包括輻射校正、大氣校正、條帶噪聲消除、幾何校正等內(nèi)容。在圖像恢復(fù)中，對(duì)于一個(gè)目標(biāo)函數(shù)求極小值，其中要求解的目標(biāo)函數(shù)就是如下的一個(gè)不受約束的最優(yōu)化問題［4－7］

其中，f為Rn→R光滑函數(shù)，c為Rn→R 正則函數(shù)其中定義域x∈Rn。

對(duì)于式(1)具體到l2－l1中，有

其中，y∈Rn，A∈Rk×n，k ＜n，τ∈R+標(biāo)準(zhǔn)歐幾里得范數(shù)代表lp范數(shù)，其中p≥1。式(2)可以用于求出欠定線性方程y=Ax的稀疏近似解［8－9］。

之前涉及上述快速算法包括文獻(xiàn)［2］中的方法。在信號(hào)處理中關(guān)于l1懲罰項(xiàng)的記載參見文獻(xiàn)［10］。對(duì)于上述最優(yōu)化問題比較流行的新的應(yīng)用，就是壓縮感知(CS)［9］。最新結(jié)果顯示，一個(gè)稀疏信號(hào)相對(duì)較少的數(shù)據(jù)投影，可以包含絕大多數(shù)信息。當(dāng)設(shè)置了沒有噪聲的情況下，通過發(fā)現(xiàn)一個(gè)可以匹配原始信號(hào)的稀疏信號(hào)從而精確逼近。

1 方法概述

求解式(1)，可以通過生成一些列的{xt，t=0，1，…}進(jìn)行迭代求解，首先通過泰勒公式進(jìn)行展開，并運(yùn)用MM算法進(jìn)行簡(jiǎn)化

其中，αt∈R+。將式(3)進(jìn)行化簡(jiǎn)得到

其中，ut∈xt－▽f(xt)。將式(3)中前兩項(xiàng)，即(zxt)T▽f(xt)+z－x可以看作一個(gè)二次可分離的逼近f(x)，如果對(duì)于正則項(xiàng)c(z)是可分離的情況，則式(3)是可分離的形式。對(duì)于正則項(xiàng)c(z)是可分離的情況，可寫為如下形式

式(2)中的l1正則項(xiàng)顯然如式(5)所示，即ci(z)=，當(dāng)正則項(xiàng)是lpp范數(shù)時(shí)，也滿足式(5)，即正則項(xiàng)是可分離的。

對(duì)于正則項(xiàng)是塊可分離的情況，如式(6)所示

其中，x［1］，x［2］，…，x［m］是 x 中 m 個(gè)不相交的子集。

綜上所述，可以得到式(3)每一次迭代的解。當(dāng)正則項(xiàng)c(x)是可分離的或者塊分離的，可以得到有限的極小值。隨后可以證明極小值的解收斂。

2 算法

2.1 算法框架

圖1 算法流程圖

通過選取不同的正則項(xiàng)c(x)，不同的方法選擇αt，序號(hào)8中xt+1滿足的條件不同，可以得到不同的實(shí)例化。

2.2 正則項(xiàng)c(x)是可分離的，對(duì)于子問題的求解

2.3 對(duì)于αt的選取

可以用αtI來代替 Hessian矩陣▽2f(x)，令，st=xt－xt－1，Rt= ▽f(xt)－ ▽f(xt－1)，要求 αtst≈Rt從而得到αt

2.4 解的條件

對(duì)于每一次迭代，xt+1滿足如下

其中，σ∈(0，1)是一個(gè)常量，通常取一個(gè)接近于零的數(shù)。

2.5 終止條件

終止條件用于迭代程序的最后終止的條件。

2.6 對(duì)于的自適應(yīng)選取

就像GPRS和IST算法，好的初始值對(duì)于問題的解是有益處的。關(guān)于自適應(yīng)的選擇就是首先給定一個(gè)初始的τ0，用于初始化算法，當(dāng)?shù)诙芜\(yùn)行算法程序時(shí)，可以自適應(yīng)地選擇一個(gè)τ，這樣可以減少算法的迭代次數(shù)。如果用一個(gè)稍大的τ來解決式(1)，然后逐漸縮小到期望值，比直接給定一個(gè)較小的τ，通常會(huì)更有效。

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

前提條件選取A是［20×40］的隨機(jī)矩陣，分別選取x為不同的稀疏度，ζ=1.1。

圖2 參數(shù)選取流程

表1 改進(jìn)后算法與SpaRSA算法的比較

圖3 改進(jìn)后算法與SpaRSA算法的比較

4 結(jié)束語

介紹了用于解決大欠定最優(yōu)化問題的稀疏重構(gòu)算法SpaRSA，并改進(jìn)了SpaRSA的解法以及對(duì)τ的選取，仿真結(jié)果表明，該算法能夠更快的求出近似解，在正則項(xiàng)是凸的情況下，可以證明目標(biāo)函數(shù)的極小解是收斂的。

［1］STEPHEN J W，ROBERT D.Sparse reconstruction by separable approximation［J］.IEEE Trance on Math，2009(1):981－986.

［2］CLAERBOUT J，MUIR F.Robust modelling of erratic data［J］.Geophysics，1973(8):826 －844.

［3］AXELSSON O.Iterative solution methods［M］.Newyork:Cambridge University Press，1996.

［4］BARZILAI J，BORWEIN J.Two point step size gradient methods［J］.IMA Journal of Numerical Analysis，1988(8):141－148.

［5］OLSHAUSEN B A，F(xiàn)IELD D J.Emergence of simple － cell receptive field properties by learning a sparse code for natural images［J］.Nature，1996，38(1):607 － 609.

［6］LEWICKI M S，SEJNOWSKI T J.Learning overcomplete representations［J］.Neural Computer，2000，12(2):337 －365.

［7］COMBETTESP，WAJSV.Signal recovery by proximal forward－ backward splitting［J］.SIAM Journal of Multiscale Model Simulation，2005(4):1168 －1200.

［8］CLARKE F.Optimization and nonsmooth analysis［M］.New York:Wiley Press，1983.

［9］CAND`ES E，ROMBERG J，TAO T.Stable signal recovery from incomplete and inaccurate information［J］.Communications on Pure and Applied Mathematics，2005，59(6):1207－1233.

［10］MILLER A.Subset selection in regression［M］.London:Chapman and Hall，2002.