UA MATH567 高维统计专题1 稀疏信号及其恢复5 LASSO的估计误差

UA MATH567 高维统计专题1 稀疏信号及其恢复5 LASSO的估计误差

• • Signal Recovery Noisy Setting
  • LASSO的估计误差

Signal Recovery Noisy Setting

前四讲算是把无噪声的情况讨论得差不多了，这一讲开始我们讨论含噪声的稀疏信号恢复问题。假设observations是
$$y=A{x}^{\ast }+w$$

其中$A\in {\mathbb{R}}^{n\times d}$是design matrix，$x^{\ast }\in {\mathbb{R}}^d$是true signal，$w$是noise；现在的问题是我们知道$y$和$A$，想要得到真实信号的一个估计量$\hat{x}$；关于这个问题有三种等价的分析框架：

Penalized Least Square
$$\underset{x}{\min }\frac{1}{2n}{\Vert y-Ax\Vert }_2^2+{\lambda }_n\varphi (x)$$

其中${\lambda }_n$是regularization parameter，$\varphi (x)$是penalty function，$\frac{1}{2n}{\Vert y-Ax\Vert }_2^2$是least square loss：

$\varphi (x)={\Vert x\Vert }_1$: LASSO

$\varphi (x)={\Vert x\Vert }_2$: Ridge regression

$\varphi (x)=\eta {\Vert x\Vert }_1+(1-\eta ){\Vert x\Vert }_2$: Elastic net

此外还有adaptive lasso, adaptive elastic net, SCAD (smoothly clipped absolute deviations), MCP (minimax concave penalty)等一系列通过设计penalty function得到能实现不同目的的penalized least square模型；

Constraint Least Square
$$\begin{gathered} \underset{x}{\min }\frac{1}{2n}{\Vert y-Ax\Vert }_2^2 \\ s.t.\varphi (x)\le R \end{gathered}$$

这与Penalized Least Square是完全等价的。

Relaxed Basis Pursuit或者Basis Pursuit Denoising

$$\begin{gathered} \underset{x}{\min }\varphi (x) \\ s.t.\frac{1}{2n}{\Vert y-Ax\Vert }_2^2\le b^2 \end{gathered}$$

这种一般在EECS的文献中比较常见，统计学一般用前两种（主要是第一种）框架。

---

LASSO的估计误差

在noisy setting下，full recovery自然是不可能的了，但我们希望估计误差$\Vert \hat{x}-x^{\ast }\Vert$尽可能小，下面我们讨论一下LASSO估计误差的下界。

在第二讲推导$L_1$-minimization时，为了构造$L_0$-norm的scale-invariant性质，我们引入了一个凸锥
$$C(S)=\{{\mathbb{R}}^d:{\Vert {\Delta }_{S^C}\Vert }_1\le {\Vert {\Delta }_S\Vert }_1\}$$

其中$S\subset \{1,2,\cdots ,d\}$是一个指标集；在讨论LASSO估计量时，我们需要再对这个凸锥做一点修正，考虑到LASSO估计量的特点是$L_1$-norm作为penalty提供sparse solution，没有被shrink to zero的那些observation会被proportional shrink，据此我们引入一个新的凸锥
$$C_{\alpha }(S)=\{{\mathbb{R}}^d:{\Vert {\Delta }_{S^C}\Vert }_1\le \alpha {\Vert {\Delta }_S\Vert }_1\}$$

Restricted Eigenvalue Condition
称design matrix $A$满足Restricted Eigenvalue Condition over index set $S$ with parameter $(\kappa ,\alpha )$如果
$$\frac{1}{n}{\Vert A\Delta \Vert }_2^2\ge \kappa {\Vert \Delta \Vert }_2^2,\forall \Delta \in C_{\alpha }(S)$$

通常将这个条件简单记为$RE(\kappa ,\alpha )$。

评注
如果$\kappa >0$，则$RE(\kappa ,\alpha )$说明
$$\frac{1}{n}{\Vert A\Delta \Vert }_2^2\ge \kappa {\Vert \Delta \Vert }_2^2>0,\forall \Delta \in C_{\alpha }(S)\setminus \{0\}$$

这说明
$$C_1(S)\cap Null(A)=\{0\}$$

也就是Restricted Null Property成立。

定理 如果$supp(x^{\ast })=S$，$|S|=s$，$A$满足$RE(\kappa ,\alpha )$ over $S$:

在Penalized Least Square形式的LASSO中，如果$${\lambda }_n\ge 2{\Vert \frac{A^{T}w}{n}\Vert }_{\infty }$$则$${\Vert \hat{x}-x^{\ast }\Vert }_2\le \frac{3}{\kappa }\sqrt{s}{\lambda }_n$$因此最小的上界为$\frac{6}{\kappa }\sqrt{s}{\Vert \frac{A^{T}w}{n}\Vert }_{\infty }$

在Constraint Least Square形式的LASSO中，如果$R={\Vert x^{\ast }\Vert }_1$，则$${\Vert \hat{x}-x^{\ast }\Vert }_2\le \frac{4}{\kappa }\sqrt{s}{\Vert \frac{A^{T}w}{n}\Vert }_{\infty }$$

在Relaxed Basis Pursuit形式的LASSO中，如果$b^2\ge \frac{{\Vert w\Vert }_2^2}{2n}$，则$${\Vert \hat{x}-x^{\ast }\Vert }_2\le \frac{4}{\kappa }\sqrt{s}{\lambda }_n{\Vert \frac{A^{T}w}{n}\Vert }_{\infty }+\frac{2}{\sqrt{\kappa }}\sqrt{b^2-\frac{{\Vert w\Vert }_2^2}{2n}}$$因此，当$b^2=\frac{{\Vert w\Vert }_2^2}{2n}$时，上界最小，为$\frac{4}{\kappa }\sqrt{s}{\Vert \frac{A^{T}w}{n}\Vert }_{\infty }$；

评注
从上面这几个结果来看，$\kappa$越大（restricted eigenvalue condition越严格），$s$越小（信号越系数），估计量的误差就越小；另外，上界的大小主要由${\Vert \frac{A^{T}w}{n}\Vert }_{\infty }$决定，其中$w$是noise term；如果$A$是固定的，$w{\sim }_{iid}N(0,{\sigma }^2)$，假设（标准化design matrix的列向量）
$$\frac{{\Vert A_j\Vert }_2}{n}=1$$

且$A$满足$RE(\kappa ,\alpha )$，则
$$\frac{A^{T}w}{n}\sim N(0,\frac{A^{T}A}{n^2}{\sigma }^2)$$

$\frac{A^{T}w}{n}$中每个元素的边缘分布为$N(0,{\sigma }^2/n)$，因此$\frac{A^{T}w}{n}$的$L_{\infty }$-norm其实就是$d$个$N(0,{\sigma }^2/n)$的最大值；根据UA MATH567 高维统计III 随机矩阵12 整数环上的区间的应用：拐点侦测的统计量及假设检验中介绍的最大值的概率不等式，
$$P({\Vert \frac{A^{T}w}{n}\Vert }_{\infty }\ge \sigma (\sqrt{\frac{2\log d}{n}}+\delta ))\le 2e^{-\frac{n{\delta }^2}{2}}$$

取$\frac{1}{\sqrt{n}}\lesssim \delta$，则$n{\delta }^2\to \infty$，从而以上概率的上界为0，这说明${\Vert \frac{A^{T}w}{n}\Vert }_{\infty }$依概率1满足
$${\Vert \frac{A^{T}w}{n}\Vert }_{\infty }=O(\sqrt{\frac{s\log d}{n}})$$

这是一个非常重要的结果，这时到目前为止的Frequentist Optimality；

证明第二条结论
考虑
$$\begin{gathered} \underset{x}{\min }\frac{1}{2n}{\Vert y-Ax\Vert }_2^2 \\ s.t.{\Vert x\Vert }_1\le R={\Vert x^{\ast }\Vert }_1 \end{gathered}$$

假设$\hat{\theta }$是它的解，$x^{\ast }$是true signal，定义$\Delta =\hat{x}-x^{\ast }$；根据解的定义，
$$\begin{gathered} {\Vert y-A\hat{x}\Vert }_2^2\le {\Vert y-A{x}^{\ast }\Vert }_2^2 \\ {\Vert A{x}^{\ast }+w-A\hat{x}\Vert }_2^2\le {\Vert w\Vert }_2^2 \\ {\Vert w-A\Delta \Vert }_2^2\le {\Vert w\Vert }_2^2 \\ {\Vert w\Vert }_2^2+{\Vert A\Delta \Vert }_2^2-2w^{T}A\Delta \le {\Vert w\Vert }_2^2 \\ {\Vert A\Delta \Vert }_2^2\le 2w^{T}A\Delta \end{gathered}$$

根据Cauchy不等式
$$\frac{{\Vert A\Delta \Vert }_2^2}{n}\le \frac{2w^{T}A\Delta }{n}\le 2{\Vert \frac{A^{T}w}{n}\Vert }_{\infty }{\Vert \Delta \Vert }_1$$

下面我们说明$\Delta \in C_1(S)\subset C_3(S)$：因为$x^{\ast }$是true signal，所以
$$\begin{gathered} \Vert x_S^{\ast }\Vert ={\Vert x^{\ast }\Vert }_1=R\ge {\Vert \hat{x}\Vert }_1={\Vert x^{\ast }+\Delta \Vert }_1 \\ ={\Vert x_S^{\ast }+{\Delta }_S\Vert }_1+{\Vert {\Delta }_{S^C}\Vert }_1\ge \Vert x_S^{\ast }\Vert -{\Vert {\Delta }_S\Vert }_1+{\Vert {\Delta }_{S^C}\Vert }_1 \end{gathered}$$

所以
$${\Vert {\Delta }_{S^C}\Vert }_1\le {\Vert {\Delta }_S\Vert }_1$$

也就是说$\Delta \in C_1(S)$；根据$RE(\kappa ,1)$，
$${\Vert \Delta \Vert }_2^2\le \frac{1}{n\kappa }{\Vert A\Delta \Vert }_2^2\le \frac{2}{\kappa }{\Vert \frac{A^{T}w}{n}\Vert }_{\infty }{\Vert \Delta \Vert }_1$$

其中
$${\Vert \Delta \Vert }_1={\Vert {\Delta }_S\Vert }_1+{\Vert {\Delta }_{S^C}\Vert }_1\le 2{\Vert {\Delta }_S\Vert }_1\le 2\sqrt{s}{\Vert {\Delta }_S\Vert }_2$$

代入上式中可得
$${\Vert \Delta \Vert }_2\le \frac{4}{\kappa }\sqrt{s}{\Vert \frac{A^{T}w}{n}\Vert }_{\infty }$$

，

总结

以上是生活随笔为你收集整理的UA MATH567 高维统计专题1 稀疏信号及其恢复5 LASSO的估计误差的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。