牛頓內(nèi)點(diǎn)法求解l1正則化的最小二乘問題

王偵倪，邱歡

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

1 公式介紹

一個線性模型如下所示：

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

2 2l規(guī)則化最小二乘

防止過度擬合的標(biāo)準(zhǔn)技術(shù)或Tikhonov正則化[1]公式為：

當(dāng)正則化參數(shù)0λ＞時， Tikhonov正則化問題或2l規(guī)則化最小二乘問題（LSP）可轉(zhuǎn)化為下式求解：

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

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

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

3 1l規(guī)則化最小二乘

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

其中，；λ＞0是正則項(xiàng)，式（3）為調(diào)整最小二乘（LSP）。

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

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

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

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

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

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

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

最近，正規(guī)化的思想在信號處理和統(tǒng)計(jì)方面引起了學(xué)者很大的興趣。在信號處理中，正則化的思想主要體現(xiàn)在幾個方面，包括基礎(chǔ)追蹤去噪和不完全測量的信號恢復(fù)方法[6]。在統(tǒng)計(jì)學(xué)中，正則化的思想被用在眾所周知的Lasso算法中用于特征選擇及其擴(kuò)展，比如彈性網(wǎng)。……