UA MATH567 高维统计专题1 稀疏信号及其恢复6 随机设计矩阵下LASSO的估计误差

UA MATH567 高维统计专题1 稀疏信号及其恢复6 随机设计矩阵下LASSO的估计误差

上一讲我们推导了noisy setting下LASSO估计误差的阶$O(\sqrt{s\log d/n})$，但它的假设是design matrix为常矩阵；这一讲我们放宽假设，推导随机设计矩阵下LASSO的估计误差。

定理 假设$A\sim {\mathbb{R}}^{n\times d}$，并且它的行向量iid服从$N(0,\Sigma )$，则存在常数$C_1<1<C_2$使得
$$\frac{{\Vert Ax\Vert }_2^2}{n}\ge C_1{\Vert \sqrt{\Sigma }x\Vert }_2^2-C_2{\rho }^2(\Sigma )\frac{\log d}{n}{\Vert x\Vert }_1^2$$

成立的概率不小于$1-\frac{e^{-n/32}}{1-e^{-n/32}}$，其中${\rho }^2(\Sigma )={\max }_i{\Sigma }_{ii}$

评注
这个定理的证明可以参考Manwright的high-dimensional statistics那本书的section 7.6 proof of theorem 7.16；

这个定理蕴涵Restricted Eigenvalue Condition，记${\gamma }_{\min }$为$\Sigma$的最小的特征值，
$$C_1{\Vert \sqrt{\Sigma }x\Vert }_2^2\ge C_1(\sqrt{{\gamma }_{\min }}{\Vert x\Vert }_2{)}^2=C_1{\gamma }_{\min }{\Vert x\Vert }_2^2$$

取$x\in C_{\alpha }(S)$，则
$$\begin{gathered} {\Vert x\Vert }_1={\Vert x_S\Vert }_1+{\Vert x_{S^C}\Vert }_1\le (1+\alpha ){\Vert x_S\Vert }_1 \\ \le (1+\alpha )\sqrt{s}{\Vert x_S\Vert }_2\le (1+\alpha )\sqrt{s}{\Vert x\Vert }_2 \end{gathered}$$

根据这个定理，
$$\begin{gathered} \frac{{\Vert Ax\Vert }_2^2}{n}\ge C_1{\gamma }_{\min }{\Vert x\Vert }_2^2-C_2{\rho }^2(\Sigma )\frac{\log d}{n}(1+\alpha {)}^{2}s{\Vert x\Vert }_2^2 \\ \ge \frac{C_1}{2}{\gamma }_{\min }{\Vert x\Vert }_2^2 \end{gathered}$$

只要
$$C_2{\rho }^2(\Sigma )\frac{\log d}{n}(1+\alpha {)}^{2}s{\Vert x\Vert }_2^2<\frac{C_1}{2}{\gamma }_{\min }{\Vert x\Vert }_2^2$$上式第二个不等号就成立，而这个条件实际上是对sparsity的限制（这个条件非常有趣，可以发现稀疏性的上界关于样本量$n$是线性的，关于特征数$d$是对数的，因此高维最小二乘模型中允许$d>n$的情况存在），
$$s\le \frac{C_1}{2}{\gamma }_{\min }\frac{n}{\log d}\frac{1}{C_2{\rho }^2(\Sigma )(1+\alpha {)}^2}$$

如果$\alpha =3$，这个上界为
$$\frac{C_1}{32}{\gamma }_{\min }\frac{n}{\log d}\frac{1}{C_2{\rho }^2(\Sigma )}$$

综上，当$x\in C_3(S)$时
$$\frac{{\Vert Ax\Vert }_2^2}{n}\ge \frac{C_1}{2}{\gamma }_{\min }{\Vert x\Vert }_2^2$$

对所有满足$|S|=s\le \frac{C_1}{32}{\gamma }_{\min }\frac{n}{\log d}\frac{1}{C_2{\rho }^2(\Sigma )}$的指标集$S$成立，因此这个定理蕴涵$RE(\frac{C_1}{2}{\gamma }_{\min },3)$。

---

Design Matrix的Dependence Structure
协方差矩阵$\Sigma$决定Design Matrix的Dependence Structure，在simulation study中，常用的dependence structure比如

$AR(1)$: $\rho$是自相关性系数
$$\Sigma =\left[\begin{array}{ccccc}1& \rho & {\rho }^2\cdots & & \\ & 1& \rho & \cdots & \\ \cdots & & & & \\ & & & & 1\end{array}\right]$$

也就是$AR(1)$序列的协方差矩阵；

Compound Symmetry：
$$\Sigma =(1-\rho )I_d+\rho 11^T$$

---

定理 对于Penalized Least Square形式的LASSO，如果${\lambda }_n\ge 2{\Vert \frac{A^{T}w}{n}\Vert }_{\infty }$，则对任意满足$$|S|\le \frac{C_1}{64C_2}\frac{\kappa }{{\rho }^2(\Sigma )}\frac{n}{\log d}$$的指标集$S$，
$${\Vert \hat{x}-x^{\ast }\Vert }_2^2\le \frac{144}{C_1^2}\frac{{\lambda }_n^2}{{\kappa }^2}|S|+\frac{16}{C_1}\frac{{\lambda }_n}{\kappa }{\Vert x_{S^C}^{\ast }\Vert }_1+\frac{32C_2}{C_1}\frac{{\rho }^2(\Sigma )}{\kappa }\frac{\log d}{n}{\Vert x_{S^C}^{\ast }\Vert }_1^2$$

这个上界可以由$|S|$与${\Vert {\theta }_{S^C}^{\ast }\Vert }_1$控制，当二者均比较小时，这个上界就会比较小，但它们是此消彼长的关系。

总结

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

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