具有Log型懲罰函數的稀疏正則化

高雅，張海

(西北大學數學學院，陜西 西安　710127)

具有Log型懲罰函數的稀疏正則化

高雅，張海

(西北大學數學學院，陜西 西安710127)

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

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

1　引言

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

稀疏正則化方法是解決高維數據分析的有力工具之一.經典的變量選擇方法L0正則化方法最早用于變量選擇和特征提取，主要是以參數個數為約束，進而得到最優的變量選擇結果.但是L0正則化方法需要求解一個組合優化問題，即NP難問題，難度較大不易實現.1996年，Tibshirani[2]提出了 L1正則化方法，即 Lasso方法.Lasso方法求解的是一個凸優化問題，它在完成變量選擇的同時可估計出參數值.從而給出了一種全新的變量選擇方法.基于此，Lasso方法在上個世紀90年代后期開始廣泛應用于統計學及信號處理等領域.但是，Lasso方法的解不具有一致性，當數據之間有某種強相關性時，不能有效選擇正確變量.對于此問題有兩種研究方向.其一，研究在何種條件下，Lasso具有解的一致性.此方面研究見文獻[3-5].另一種研究方向為如何提出一種新的懲罰函數方法將問題解決，此方面研究見文獻[6-9].Candes在文中[3]提出一種加強L1正則化方法，同時給出一種重賦權Lasso方法，并猜測Log型懲罰函數會具有很好的稀疏信號重建能力.

基于Candes的研究工作，本文研究具有Log型的懲罰函數及其快速算法，并通過變量選擇和信號重建進行兩組實驗，說明具有Log型懲罰函數的正則化方法具有有效性.

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

本節首先給出一些記號，并給出Log型懲罰函數，并進一步給出一種快速高效的求解方法.

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

其中，Θ=ψ?稱為傳感矩陣.本文希望從觀測數據y恢復稀疏未知向量x，進而恢復信號w.

一般地，信號重建問題可以建立如下L0問題的數學模型進行求解：

其中∥x∥0為向量x中非零向量的個數.上述模型可以轉化為如下正則化表示方法：

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

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

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

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

上述模型可以統一為如下正則化框架進行研究：

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

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

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

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

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

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

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

定義3.1如果對于閾值t?＞0，fd為t的實函數，滿足

稱h為一個閾值函數.由定義可知，閾值函數h是由閾值t和函數fd表達的.

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

是對角非線性的.

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

定義 3.4如果一個閾值函數h對正則化問題的任意解x都可以表示成為：

那么稱上式為正則化問題的閾值表達.其中，H是由h構成的閾值算子，B是從RN到RN的仿射算子.可以看出，如果正則化問題有閾值表達，則正則化的所有解都可以由算子H和B來表示.

定義3.5如果正則化問題有閾值表達，那么迭代式

稱為該正則化問題的閾值迭代算法.

3.1預解算子的表示

Log型正則化的模型如下，

其中

記

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

整理得，

當固定變量z時，極小化上式等價于

其中

3.2定理及證明

定理3.1極小化問題

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

證明

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

由定理2.1可知，可以設計Log型正則化的閾值算法，

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

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

4　實驗

本節通過變量選擇和稀疏信號重建兩個問題說明Log型正則化閾值迭代算法的有效性.

4.1變量選擇實驗

考慮如下線性模型：

其中

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

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

圖2　Hard，Soft，Half，Log閾值迭代算法以及OMP正交匹配追蹤算法實驗結果比較

4.2信號實驗

本實驗討論信號為考慮一個信號長度N=256，稀疏度限制k=100的無噪聲實值信號x.使用高斯矩陣，取均勻采樣數T=180，利用Log型正則化閾值迭代算法，對原始信號進行重建.原始信號圖如圖3所示，重建信號圖如圖4所示.信號重建實驗說明，Log型罰函數正則化方法較好的重建了原始信號，并可高效實現.

5　結論

高維數據分析是當前熱點研究方向之一.由于科學技術的不斷發展，各個學科均產生了大量的數據.因此如何有效地從數據中提取信息是諸多學科任務重點之一.基于正則化方法的框架，本文研究具有Log型懲罰函數的稀疏正則化，給出一種新的非凸變量選擇及壓縮感知策略，并提出相應的高效快速閾值迭代算法.并通過變量選擇和稀疏信號重建兩組實驗，說明了具有Log型懲罰函數的稀疏正則化方法的有效性及算法的準確性.

圖3　原始信號圖

圖4　重建信號圖

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

國家自然科學基金(11171272).

高雅(1990-)，碩士生，研究方向：機器學習.

2000 MSC:91D30