高雅，張海

(西北大學(xué)數(shù)學(xué)學(xué)院，陜西 西安　710127)

具有Log型懲罰函數(shù)的稀疏正則化

高雅，張海

(西北大學(xué)數(shù)學(xué)學(xué)院，陜西 西安710127)

研究具有Log型懲罰函數(shù)的稀疏正則化，給出一種新的非凸變量選擇及壓縮感知策略，提出一種高效快速閾值迭代算法.并通過(guò)變量選擇問(wèn)題和稀疏信號(hào)重建驗(yàn)證了所提出的Log型稀疏正則化模型的有效性.

壓縮感知；閾值迭代算法；稀疏性

1　引言

高維數(shù)據(jù)分析是當(dāng)前統(tǒng)計(jì)學(xué)、金融經(jīng)濟(jì)學(xué)、計(jì)算機(jī)科學(xué)和生物信息學(xué)等領(lǐng)域面臨的主要問(wèn)題之一.伴隨著科學(xué)技術(shù)的快速發(fā)展，各個(gè)學(xué)科均產(chǎn)生了大批量數(shù)據(jù)[1].例如在高能物理領(lǐng)域，作為信息技術(shù)發(fā)展的主要推動(dòng)者之一，高能物理的實(shí)驗(yàn)數(shù)據(jù)量每年已經(jīng)超過(guò)100PB(千億萬(wàn)字節(jié)，1PB=220GB)，且隨著實(shí)驗(yàn)規(guī)模的不斷擴(kuò)大，實(shí)驗(yàn)復(fù)雜性的不斷增加，現(xiàn)代高能物理產(chǎn)生的海量數(shù)據(jù)對(duì)數(shù)據(jù)分析研究提出巨大的挑戰(zhàn).例如在生物信息領(lǐng)域，生物技術(shù)的進(jìn)步帶來(lái)基因組學(xué)，蛋白組學(xué)，各種組學(xué)的出現(xiàn)，使得海量數(shù)據(jù)的積累變得非常迅速，其中僅個(gè)人的基因數(shù)據(jù)都以GB(千兆字節(jié)，1GB=1024MB)作為數(shù)據(jù)量單位.再比如說(shuō)在信息技術(shù)方向，截止到2012年，數(shù)據(jù)量已經(jīng)從TB(萬(wàn)億字節(jié)，1TB=1024GB)級(jí)別躍升到PB，EB(百億億字節(jié)，1EB=1024PB)乃至ZB(十萬(wàn)億億字節(jié)，1ZB=1024EB)級(jí)別.IBM的研究稱，整個(gè)人類文明所獲得的全部數(shù)據(jù)中，有90%是過(guò)去兩年內(nèi)產(chǎn)生的.而到了2020年，全世界所產(chǎn)生的數(shù)據(jù)規(guī)模將達(dá)到今天的44倍.從而開(kāi)展如何有效利用高維海量數(shù)據(jù)的大數(shù)據(jù)研究成為了各個(gè)科學(xué)研究領(lǐng)域面臨的挑戰(zhàn)與機(jī)遇.

稀疏正則化方法是解決高維數(shù)據(jù)分析的有力工具之一.經(jīng)典的變量選擇方法L0正則化方法最早用于變量選擇和特征提取，主要是以參數(shù)個(gè)數(shù)為約束，進(jìn)而得到最優(yōu)的變量選擇結(jié)果.但是L0正則化方法需要求解一個(gè)組合優(yōu)化問(wèn)題，即NP難問(wèn)題，難度較大不易實(shí)現(xiàn).1996年，Tibshirani[2]提出了 L1正則化方法，即 Lasso方法.Lasso方法求解的是一個(gè)凸優(yōu)化問(wèn)題，它在完成變量選擇的同時(shí)可估計(jì)出參數(shù)值.從而給出了一種全新的變量選擇方法.基于此，Lasso方法在上個(gè)世紀(jì)90年代后期開(kāi)始廣泛應(yīng)用于統(tǒng)計(jì)學(xué)及信號(hào)處理等領(lǐng)域.但是，Lasso方法的解不具有一致性，當(dāng)數(shù)據(jù)之間有某種強(qiáng)相關(guān)性時(shí)，不能有效選擇正確變量.對(duì)于此問(wèn)題有兩種研究方向.其一，研究在何種條件下，Lasso具有解的一致性.此方面研究見(jiàn)文獻(xiàn)[3-5].另一種研究方向?yàn)槿绾翁岢鲆环N新的懲罰函數(shù)方法將問(wèn)題解決，此方面研究見(jiàn)文獻(xiàn)[6-9].Candes在文中[3]提出一種加強(qiáng)L1正則化方法，同時(shí)給出一種重賦權(quán)Lasso方法，并猜測(cè)Log型懲罰函數(shù)會(huì)具有很好的稀疏信號(hào)重建能力.

基于Candes的研究工作，本文研究具有Log型的懲罰函數(shù)及其快速算法，并通過(guò)變量選擇和信號(hào)重建進(jìn)行兩組實(shí)驗(yàn)，說(shuō)明具有Log型懲罰函數(shù)的正則化方法具有有效性.

2　具有 Log型懲罰函數(shù)的稀疏正則化方法

本節(jié)首先給出一些記號(hào)，并給出Log型懲罰函數(shù)，并進(jìn)一步給出一種快速高效的求解方法.

稀疏正則化方法的重大應(yīng)用領(lǐng)域是稀疏信號(hào)重建.為了更好地理解本文的研究方法，下面從稀疏信號(hào)重建問(wèn)題開(kāi)展研究.其結(jié)果可簡(jiǎn)單推廣到其他應(yīng)用領(lǐng)域.一般地，稀疏信號(hào)重建問(wèn)題描述為：假設(shè)有一個(gè)有限長(zhǎng)度的信號(hào)w，w∈RN，該信號(hào)在某一個(gè)正交基下，表示為w=?x，這里?=(?1，···，?N)，x稱為基的系數(shù).假定通過(guò)測(cè)量矩陣ψ來(lái)對(duì)w進(jìn)行觀測(cè)(測(cè)量)，假定得出的觀測(cè)值為y，觀測(cè)噪聲為ε，即滿足

其中，Θ=ψ?稱為傳感矩陣.本文希望從觀測(cè)數(shù)據(jù)y恢復(fù)稀疏未知向量x，進(jìn)而恢復(fù)信號(hào)w.

一般地，信號(hào)重建問(wèn)題可以建立如下L0問(wèn)題的數(shù)學(xué)模型進(jìn)行求解：

其中∥x∥0為向量x中非零向量的個(gè)數(shù).上述模型可以轉(zhuǎn)化為如下正則化表示方法：

其中x=(x1，···，xN)T∈RN，正則化參數(shù)λ＞0.這就是L0正則化方法.L0方法可以產(chǎn)生最稀疏的解，但是需要求解一個(gè)NP組合優(yōu)化問(wèn)題，所以通常將L0方法轉(zhuǎn)化為下述求解凸優(yōu)化問(wèn)題的L1正則化方法：

由于 L1正則化方法的求解可以借用現(xiàn)在凸優(yōu)化的工具，L1正則化成為當(dāng)今流行的稀疏信號(hào)重建策略，并在上世紀(jì) 90代后期廣泛應(yīng)用于統(tǒng)計(jì)學(xué)及信號(hào)處理領(lǐng)域.主要代表工作是LASSO(Least Absolute Shrinkage and Selection Operator)[2]和BPDN(Basis Pursuit De-Noising)[10].

雖然L1正則化方法具有凸優(yōu)化問(wèn)題中最稀疏的解，但其解仍不夠稀疏.同期，Chartrand[11]提出了非凸正則化方法具有更稀疏的解.文獻(xiàn)[12]借用相變的工具分析上述壓縮感知重建策略的稀疏重建能力，其結(jié)果顯示，具有非凸罰函數(shù)的正則化策略具有更好地稀疏重建能力.基于此，文獻(xiàn)[9]提出了L1/2正則化方法，實(shí)現(xiàn)了更高效的正則化方法：

以及張海等提出的基于SCAD方法的壓縮感知策略[12].

上述模型可以統(tǒng)一為如下正則化框架進(jìn)行研究：

其中P(λ；x)為懲罰函數(shù)，λ為正則化參數(shù)，用來(lái)控制模型的復(fù)雜度，從而有效的達(dá)到某種優(yōu)化均衡.

本文研究的Log型稀疏正則化方法的模型如下：

顯然，上述模型為非凸正則化問(wèn)題，其解往往具有更稀疏的結(jié)果，如圖1所示.

圖1　L1，L1/2及Log型稀疏正則化方法解的幾何表示

由圖1可以看出，Log型正則化方法在無(wú)窮遠(yuǎn)處更平坦，從而更有效逼近L0正則化方法.

3　Log型正則化方法閾值表示理論

閾值迭代算法是一種高效、快速、重建精度高的重構(gòu)算法，其迭代步驟簡(jiǎn)單，且可以單分量處理，使得它迅速被大家所認(rèn)可.閾值迭代算法包括：Blumensath和Davies[13]為求解L0問(wèn)題而提出的Hard閾值迭代算法，Daubechies等[14]為求解L1(Lasso)[12]問(wèn)題而提出的Soft閾值迭代算法，徐宗本等[9]提出的求解L1/2的Half閾值迭代算法.

定義3.1如果對(duì)于閾值t?＞0，fd為t的實(shí)函數(shù)，滿足

稱h為一個(gè)閾值函數(shù).由定義可知，閾值函數(shù)h是由閾值t和函數(shù)fd表達(dá)的.

定義3.2若對(duì)所有i，hi(x)唯一依賴于xi，并且hi是非線性的，則稱映射

是對(duì)角非線性的.

定義3.3當(dāng)映射H是由閾值函數(shù)h得到的，稱映射H(x)是閾值算子.

定義 3.4如果一個(gè)閾值函數(shù)h對(duì)正則化問(wèn)題的任意解x都可以表示成為：

那么稱上式為正則化問(wèn)題的閾值表達(dá).其中，H是由h構(gòu)成的閾值算子，B是從RN到RN的仿射算子.可以看出，如果正則化問(wèn)題有閾值表達(dá)，則正則化的所有解都可以由算子H和B來(lái)表示.

定義3.5如果正則化問(wèn)題有閾值表達(dá)，那么迭代式

稱為該正則化問(wèn)題的閾值迭代算法.

3.1預(yù)解算子的表示

Log型正則化的模型如下，

其中

記

引入變量z，則Q(x)可以整理為：

整理得，

當(dāng)固定變量z時(shí)，極小化上式等價(jià)于

其中

3.2定理及證明

定理3.1極小化問(wèn)題

由定理3.1易知，如果函數(shù)xi可以有如上表示，那么xi可以看做一個(gè)Log型正則化閾值算子用于閾值計(jì)算.

證明

3.3 Log型正則化閾值迭代算法

由定理2.1可知，可以設(shè)計(jì)Log型正則化的閾值算法，

基于Log閾值函數(shù)的形式，根據(jù)定義5，則Log閾值迭代算法為：

這里λn是第n次迭代的閾值，X(n)是第n次迭代的估計(jì)值.

4　實(shí)驗(yàn)

本節(jié)通過(guò)變量選擇和稀疏信號(hào)重建兩個(gè)問(wèn)題說(shuō)明Log型正則化閾值迭代算法的有效性.

4.1變量選擇實(shí)驗(yàn)

考慮如下線性模型：

其中

ε為高斯噪聲，Eε=0，Dε=σ2.基于上述模型，本實(shí)驗(yàn)考慮樣本數(shù)n=500，訓(xùn)練樣本與測(cè)試樣本比例為1：1的變量選擇實(shí)驗(yàn).已知前10個(gè)變量不為零，

且Θi=0，10＜i≤p.樣本通過(guò)高斯隨機(jī)產(chǎn)生，噪聲方差為0.1.在實(shí)驗(yàn)中，令維數(shù)p從500取至2000.實(shí)驗(yàn)比較了Hard，Soft，Half，Log閾值迭代算法以及OMP正交匹配追蹤算法.實(shí)驗(yàn)結(jié)果如圖2.實(shí)驗(yàn)說(shuō)明，隨著變量維數(shù)的增加，Log型正則化閾值迭代方法誤差較低，變量選擇的準(zhǔn)確性較高，與其他幾種算法比較優(yōu)勢(shì)明顯.

圖2　Hard，Soft，Half，Log閾值迭代算法以及OMP正交匹配追蹤算法實(shí)驗(yàn)結(jié)果比較

4.2信號(hào)實(shí)驗(yàn)

本實(shí)驗(yàn)討論信號(hào)為考慮一個(gè)信號(hào)長(zhǎng)度N=256，稀疏度限制k=100的無(wú)噪聲實(shí)值信號(hào)x.使用高斯矩陣，取均勻采樣數(shù)T=180，利用Log型正則化閾值迭代算法，對(duì)原始信號(hào)進(jìn)行重建.原始信號(hào)圖如圖3所示，重建信號(hào)圖如圖4所示.信號(hào)重建實(shí)驗(yàn)說(shuō)明，Log型罰函數(shù)正則化方法較好的重建了原始信號(hào)，并可高效實(shí)現(xiàn).

5　結(jié)論

高維數(shù)據(jù)分析是當(dāng)前熱點(diǎn)研究方向之一.由于科學(xué)技術(shù)的不斷發(fā)展，各個(gè)學(xué)科均產(chǎn)生了大量的數(shù)據(jù).因此如何有效地從數(shù)據(jù)中提取信息是諸多學(xué)科任務(wù)重點(diǎn)之一.基于正則化方法的框架，本文研究具有Log型懲罰函數(shù)的稀疏正則化，給出一種新的非凸變量選擇及壓縮感知策略，并提出相應(yīng)的高效快速閾值迭代算法.并通過(guò)變量選擇和稀疏信號(hào)重建兩組實(shí)驗(yàn)，說(shuō)明了具有Log型懲罰函數(shù)的稀疏正則化方法的有效性及算法的準(zhǔn)確性.

圖3　原始信號(hào)圖

圖4　重建信號(hào)圖

[1]National Research Council of the National Academies.Frontiers in Massive Data Analysis[M].Washington：The National Academies Press，2013.

[2]Tibshiran R.Regression shrinkage and selection via the lasso[J].Journal of the Royal Statistical Society，Series B，1996，58：267-288.

[3]Candes E，Wakin M B，Boyd S.Enhancing sparsity by reweighted minimization[J].IEEE Signal Process. Lett.，2007，14：707-710.

[4]Negahban S，Ravikumar P，Wainwright M J，et al.A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers[J].Statistical Science，2012：27(4)：538-557.

[5]Zhang C H，Huang J.The sparsity and bias of the Lasso selection in high-dimensional linear regression[J]. The Annals of Statistics，2008：36(4)：1567-1594.

[6]Fan J，Li R.Statistical challenges with high dimensionality：Feature Selection in Knowledge Discovery[J]. Proceedings of the International Congress of Mathematicians，European Mathematical Society，2006：595-622.

[7]Zhang C H，Huang J.Nearly unbiased variable selection under minimax concave penalty Annals of Statistics[J].The Annals of statistics，2010：38(2)：894-942.

[8]Zou H.The adaptive lasso and its oracle properties[J].Journal of the American Statistical Association，2006：101，1418-1429.

[9]Xu Z B，Chang X Y，Xu F M，et al.L1/2Regularization：an iterative half thresholding algorithm[J].IEEE Trans.Neural Networks Learning Syst.，2012，23：1013-1027

[10]Chen S，Dohono D，Saunders M.Atomic decomposition by basis pursuit[J].SIAM J.on Sci.Comp.，1998，20：33-61

[11]Chartrand R，Exact reconstructions of sparse signals via nonconvex minimization[J].IEEE Signal Process. Lett.，2007，14：707-710.

[12]張海，梁勇，徐宗本，等.基于SCAD罰函數(shù)的有噪壓縮感知集[J].數(shù)學(xué)學(xué)報(bào)，2013：0583-1431.

[13]Blumensath T.Iterative hard thresholding for compressed sensing[J].Applied and Computational Harmonic Analysis，2009，27(3)：265-274.

[14]Daubechies I，Mefrise M，Mol C.An iterative thresholding algorithm for linear inverse problems with a sparse constraint[J].Communications on Pure and Applied Mathematics，2004，57(11)：1413-1457.

A sparse regularization approach with Log type penalty

Gao Ya，Zhang Hai
(College of Mathematics，Northwest University，Xi′an710127，China)

We study a sparse regularization approach with a Log type penalty function.A new strategy of nonconvex variable selection and compressive sensing is proposed with a alternative thresholding algorithm for fast solution.Then we use variable selection experiment and signal recovery experiment to prove the validity of the sparse regularization with Log type penalty.

compressive sensing，iterative thresholding algorithm，sparsity

O233

A

1008-5513(2015)01-0027-09

10.3969/j.issn.1008-5513.2015.01.004

2014-10-15.

國(guó)家自然科學(xué)基金(11171272).

高雅(1990-)，碩士生，研究方向：機(jī)器學(xué)習(xí).

2000 MSC:91D30