牛顿内点法求解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