Lasso回归理论的起源

第一章 稀疏复原

       稀疏信号复原是一个优化问题。本章将从一个简单不含噪线性观测情况开始，随后将其扩展为更为实际的含噪复原问题。问题的最终是寻找最稀疏解，即包含最少非零值的解，也称为 $l_0$ 范数解。但由于其非凸组合本质，在计算上是非常困难的，即 NP 难问题。因此，必须借助近似方法。在稀疏复原中，通常会使用两种主要的近似方法：一种是通过如贪婪搜索这样的近似方法，来解决 NP 难组合问题。另一种，用易于求解的凸松弛来代替棘手的原问题。换而言之，就是以近似方法解决问题，或者以精确方式解决近似问题。

1.1 不含噪稀疏复原

       假设 $\mathbf{x}=(x_1，\cdots ，x_n)\in R^n$ 为未观测的稀疏信号， $\mathbf{y}=(y_1，\cdots ，y_n)\in R^n$ 为观测值， A = { a i j } ∈ R m × n A=\{a_{ij}\} \in R^{m \times n} A={aij​}∈Rm×n 为设计矩阵。在不考虑噪声的情况下，稀疏信号复原可以形式化为线性方程组：
$$\mathbf{y}=A\mathbf{x}$$
       为了复原信号 $\mathbf{x}$ ，有必要进一步对问题进行约束或正则化。通常会引入一个目标函数或正则函数 $R(\mathbf{x})$，以对信号额外的性质进行编码来实现，该目标函数或正则函数在取得期望解时具有较低值。因此，信号复原问题可以表述如下约束优化问题：
$$\begin{gathered} \min R(\mathbf{x}) \\ s.t.\mathbf{y}=A\mathbf{x} \end{gathered}$$
       当我们希望得到的解具有稀疏性时，$R(\mathbf{x})$ 就可以定义为非零元素数量，或者 $R(\mathbf{x})$ 的势，也成为 $l_0$ 范数，记为 $||\mathbf{x}|{|}_0$ 。但 $l_0$ 范数并非严格意义上的范数，属于学术名词滥用。那么，不含噪线性观测值复原稀疏信号问题转变为如下形式：
$$\begin{gathered} P_0:\min ||\mathbf{x}|{|}_0 \\ s.t.\mathbf{y}=A\mathbf{x} \end{gathered}$$

1.2 近似

       由于 $P_0$ 问题是一个 NP 难问题，目前没有算法能够在多项式时间内对其进行高效求解。因此，有必要借助近似方法。目前，常用的两种近似方法为：启发式算法和松弛方法。
       启发式算法是以探寻的方式寻找 $P_0$ 问题的解。例如，从零向量开始，逐个增加非零坐标，在每一步中选择能够对目标函数带来最佳改进的坐标。一般地，这种启发式算法并不能保证能够找到全局最优解。不过这种算法易于实现，计算效率高，并且能够找到足够优的近似解。在特定条件下，还能复原稀疏信号。
       松弛法是用易于处理的目标函数或约束条件来替换难于处理的目标函数或约束条件。例如，凸松弛方法通过凸优化问题来近似非凸优化问题，也就是通过包含凸目标和凸约束来近似非凸优化问题。很显然，凸优化问题比较容易求解。

1.3 凸优化

       凸集是指集合 $S$ 中的任意两个元素的凸组合属于 $S$，那么该集合称为凸集，其数学表达式为：
$$\forall x_1，x_2\in S，\alpha x_1+(1-\alpha )x_2\in S$$
其中，$\alpha \in [0,1]$。
       凸函数是指定义在凸集 $S$ 上的函数，且满足如下条件：
$$f(\alpha x_1+(1-\alpha )x_2)\le \alpha f(x_1)+(1-\alpha )f(x_2)$$
注意：凸函数有一条重要的性质是任意局部最小值也为全局最小值，而且严格凸函数具有唯一全局最小值。

1.4 问题 $P_0$ 松弛

       设 ${\mathbf{x}}_1$ 和 ${\mathbf{x}}_2$ 为 $\mathbf{y}=A\mathbf{x}$ 的两个可行解，则对于任意 $\alpha \in [0,1]$，有：
$$A(\alpha {\mathbf{x}}_1+(1-\alpha ){\mathbf{x}}_2)=\alpha A{\mathbf{x}}_1+(1-\alpha )A{\mathbf{x}}_2=\mathbf{y}$$
由此可知，约束集在凸组合下可行，因此是一个凸集。然而，原始问题 $P_0$ 的目标函数 $||\mathbf{x}|{|}_0$ 是一个非凸函数，导致整个优化问题 $P_0$ 为非凸函数。 为了使 $P_0$ 问题松弛为凸问题，通常做法是用一个凸函数来代替 $||\mathbf{x}|{|}_0$。
       在该问题中，我们很容易想到使用 $l_p$ 范数替代 $l_0$ 范数。更具体地说，研究 $l_p$ 范数的 $q$ 次幂，即函数 $||\mathbf{x}|{|}_q^q$。当 $q\ge 1$ 时，该函数为凸函数；当 $q<1$时，则为非凸函数。其中，$l_2$ 范数因其良好的数学性质而被优先考虑为 $l_0$ 范数的松弛形式，从而构造出如下优化问题：
$$\begin{gathered} P_2:\min ||\mathbf{x}|{|}_2^2 \\ s.t.\mathbf{y}=A\mathbf{x} \end{gathered}$$
使用该目标函数有以下优势：

• 该函数为凸函数，并且具有唯一最优解；
• 可通过解析方法求解，计算简便。

       为了求解问题 $P_2$ ，可构建其拉格朗日函数如下：
$$\mathcal{L}(\mathbf{x})=\Vert \mathbf{x}{\Vert }_2^2+{\lambda }^{\mathrm{T}}(\mathbf{y}-A\mathbf{x})$$
式中，$\lambda$ 为拉格朗日乘子。满足一阶最优性条件：
$$\frac{\partial \mathcal{L}(\mathbf{x})}{\partial \mathbf{x}}=2\mathbf{x}+A^T\lambda =0$$
可解的：
$${\mathbf{x}}^{\ast }=A^T(A{A}^T{)}^{-1}\mathbf{y}$$
       当 $A$ 的列数比行数多时，问题 $P_2$ 的这一解析解也称为 $\mathbf{y}=A\mathbf{x}$ 的伪逆解。
       尽管该方法在凸优化中具有良好的性质，但 $\Vert \mathbf{x}{\Vert }_2^2$ 目标函数存在一个严重的缺陷：最优解不具备稀疏性，无法满足稀疏信号恢复等任务中对稀疏性的需求。

1.5 $l_q$ — 正则函数对解稀疏性影响

       要理解为什么 $l_2$ 范数无法促进解的稀疏性而 $l_1$ 范数可以，要理解 $l_q$ 范数的凸性以及导致稀疏的性质，则需要研究问题 $P_q$ 的几何结构，其中 $\Vert \mathbf{x}{\Vert }_q^q$ 代替了原来的 $\Vert \mathbf{x}{\Vert }_0$：
$$\begin{gathered} P_q:\min ||\mathbf{x}|{|}_q^q \\ s.t.\mathbf{y}=A\mathbf{x} \end{gathered}$$
使得函数 $f(\mathbf{x})$ 具有相同值，即 $f(\mathbf{x})=a$ 的向量集合称为函数 $f(\mathbf{x})$ 的水平集。例如，$\Vert \mathbf{x}{\Vert }_q^q$ 函数水平集为具有相同 $l_q$ 范数的向量集合。图2.3（a）给出了对于若干 $q$ 值有水平集 $\Vert \mathbf{x}{\Vert }_q^q=1$ 的例子。满足 $\Vert \mathbf{x}{\Vert }_q^q\le r^q$ 的向量集合称为半径为 $r$ 的 $l_q$ 球，其表面为相应的水平集。注意，对于 $q\ge 1$ 来说，以水平集为边界的相应的 $l_q$ 球为凸的；对于 $0<q<1$ 来说，该球为非凸的点之间的线段并不总在球内。
       从几何的视角来看，求解优化问题等价以圆点为中心吹起的 $l_q$ 球，即从0开始增加 $l_q$ 球半径，直到与超平面 $\mathbf{y}=A\mathbf{x}$ 相交。相交点为最小 $l_q$ 范数向量，同时也为一可行解，即为 $P_q$ 的最优解。

       注意，当 $q\le 1$ 时，$l_q$ 球在坐标轴上有尖角，这些尖角的某坐标为0；但是， $q>1$ 时，$l_q$ 球无此性质。因此，对于 $q\le 1$，$l_q$ 球可能与超平面 $\mathbf{y}=A\mathbf{x}$ 在尖角处相交，从而产生稀疏解。
       总的来说，需要通过一个易于优化的函数近似难于处理的 $l_0$ 范数问题，同时又能产生稀疏解。在 $\Vert \mathbf{x}{\Vert }_q^q$ 函数族中，仅当 $q\ge 1$ 时函数为凸，同时仅当 $0<q\le 1$ 时可以产生稀疏解。那么，同时具有这两个性质的函数只有 $\Vert \mathbf{x}\Vert$ ，即 $l_1$ 范数。
       同时具有稀疏性和凸性组合这独一无二的性质，是 $l_1$ 范数在现代稀疏信号复原领域广泛使用的原因。在不含噪声情况下，难于处理的问题 $P_0$ 的 $l_1$ 范数松弛可以表述为下面的问题 $P_1$，并称为理论与算法研究的主要焦点：
$$\begin{gathered} P_1:\underset{\mathbf{x}}{\min }||\mathbf{x}|{|}_1 \\ s.t.\mathbf{y}=A\mathbf{x} \end{gathered}$$

1.6 含噪稀疏复原

       到目前为止，已经考虑的都是较为理想的不含噪观测情况。然而，在实际应用中，如图像处理或统计数据建模，观测噪声是不可避免的。因此，线性方程约束 $\mathbf{y}=A\mathbf{x}$ 必须被松弛，从而理想观测 $A\mathbf{x}$ 与实际含噪版本之间存在差异。通常用不等式 $\Vert \mathbf{y}-A\mathbf{x}{\Vert }_2\le \epsilon$ 来代替原线性模型，表明实际观测向量 $\mathbf{y}$ 与不含噪观测 $A\mathbf{x}$之间的距离在欧几里得范数下不高与 $\epsilon$。这样的松弛对于探究原始不含噪声问题 $P_0$ 的近似解是非常有帮助的。而且，当观测数量超过未知参数时，即 $A$ 的行数大于列数时，松弛是非常有必要的。在该情况下，线性方程组 $\mathbf{y}=A\mathbf{x}$ 可能无解，而且该问题是古典回归问题中经常要遇到的。含噪稀疏复原问题可以写为：
$$\begin{gathered} P_0^{\epsilon }:\underset{\mathbf{x}}{\min }||\mathbf{x}|{|}_0 \\ s.t.\Vert \mathbf{y}-A\mathbf{x}{\Vert }_2\le \epsilon \end{gathered}$$
$l_0$ 范数目标函数相应的 $l_1$ 范数松弛与不含噪声的情况下的方法类似，可以写为：
$$\begin{gathered} P_1^{\epsilon }:\underset{\mathbf{x}}{\min }||\mathbf{x}|{|}_1 \\ s.t.\Vert \mathbf{y}-A\mathbf{x}{\Vert }_2\le \epsilon \end{gathered}$$
利用恰当的拉格朗日乘子 $\lambda (\epsilon )$，将上述问题转化为一个无约束的最小化问题，即
$$P_1^{\lambda }：\underset{\mathbf{x}}{\min }\Vert \mathbf{y}-A\mathbf{x}{\Vert }_2^2+\lambda ||\mathbf{x}|{|}_1$$
或者，对