牛頓內點法求解l1正則化的最小二乘問題

王偵倪，邱歡

（西安石油大學電子工程學院，陜西西安，710065）

1 公式介紹

一個線性模型如下所示：

其中，x ∈ Rn是未知向量，y∈Rm是觀測向量，v∈Rm是噪聲，A ∈ Rm×n是字典矩陣。

2 2l規則化最小二乘

防止過度擬合的標準技術或Tikhonov正則化[1]公式為：

當正則化參數0λ＞時， Tikhonov正則化問題或2l規則化最小二乘問題（LSP）可轉化為下式求解：

Tikhonov正則化的一些基本屬性有：

（1）直線性。它的解在線性函數里面不是線性的。

（2）限制性。隨著 λ → 0 ,xl2聚集在摩爾 - 彭羅斯解決方案里面，極限點滿足L2范數最小化的所有點，即 AT(A x?y) = 0。

3 1l規則化最小二乘

在1l規則化最小二乘（LS）中，本文用Tikhonov正則化中使用的平方和的絕對值之和來代替，使得：

其中，；λ＞0是正則項，式（3）為調整最小二乘（LSP）。

l1正則化的一些基本屬性：

(1)非線性。l1最小二乘產生一個向量，它在線性函數里面不是線性的。

(2)限制性。隨著λ→0,l1正則化顯示不同的限制性，在l1正則化中，限制點在所有滿足 l最小范數，即 AT(A x?y) = 0。

(3)隨著λ→∞，有限收斂為零。在 l1正則化中，λ的有限值決定趨向，即：

(4)正則化路徑。Tikhonov正則化問題的解 xl2變化平穩，相反，l1范數求解是分段線性解路徑特性[2]。

l1正則化（LS）通常會產生一個稀疏向量x，即具有相對較少的非零系數。

隨著λ逐漸減少，x有可能更傾向于稀疏[3,4]。相反，對于Tikhonov正則化問題的解 xl2通常具有所有的非零系數。

最近，正規化的思想在信號處理和統計方面引起了學者很大的興趣。在信號處理中，正則化的思想主要體現在幾個方面，包括基礎追蹤去噪和不完全測量的信號恢復方法[6]。在統計學中，正則化的思想被用在眾所周知的Lasso算法中用于特征選擇及其擴展，比如彈性網。

4 數值實驗

本文用截斷牛頓內點法的方法用來恢復稀疏信號。算法參數如下：

考慮信號 x ∈R1024的稀疏信號恢復問題，其由10個幅度為±1的峰值組成，如圖1（a）所示。假設：

其中，Ax給出m=128個頻率的x的離散余弦變換，從索引1上的布中選擇1...1024。

本文方法找到不低于1%次優的點，相對容差為0.01。將正則化參數取為 λ =0.01λmax，其中λmax的值使用（4）中給出的公式計算，與其他方法相比，截斷的牛頓內點方法對于這個中等問題是最有效的。

圖1 稀疏信號重構

5 實驗結論

圖1（c）所示的是通過求解BPDN問題獲得1lx 的信號，雖然測量的數量遠遠少于未知的數量，但是基于1l正則化的方法能夠確切地找到了原始信號中非零點的位置。最小能量重構方法根本不能識別非零位置。我們應用了廣泛的Tikhonov正則化參數的范圍來估計信號，可以實現信號重構。

參考文獻

[1]A.Neumaier,‘Solving ill-conditioned and singular linear systems:A tutorial on regularization’SIAM REV,vol.40,no.3,pp.636-666.

[2]B.Efron,T.Hastie,I.Johnstone,and R.Tibshirani,’Least angle regression,’’Ann.Statist,vol.32,no.2,pp.407-499,2004.

[3]T.Hastie,R.Tibshirani,and J.Firedman,The Elements of Statistical Learning.New York:Springer-Verlag,2011,Springer Series in Statistics.

[4]R.Tibshirani,’Regression shrinkage and selection via the lasso,’J. Roy.Statist.Soc,ser.B,vol.58,no.1,pp.267-288,1996.

[5]S.Chen,D.Donoho,and M.Saunders,’Atomic decomposition by basis pursuit,’SIAM Rev.,vol.43,no.1,pp.129-159,2011.

[6]E.Candes,’Compressive sampling,’Proc.Int.Conger.Mathematics,2006