UA MATH567 高维统计专题1 稀疏信号及其恢复3 Coherence与RIP简介

UA MATH567 高维统计专题1 稀疏信号及其恢复3 Coherence与RIP简介

• • Pairwise inc oherence
  • Mutual Coherence
  • RIP

前两讲介绍了L0-minimization
$$\begin{gathered} \min {\Vert x\Vert }_0 \\ s.t.y=Ax \end{gathered}$$

以及作为它的convex relaxation的L1-minimization
$$\begin{gathered} \min {\Vert x\Vert }_1 \\ s.t.y=Ax \end{gathered}$$

当二者取相同的角点解时，可以实现full recovery；并且$A$的性质越好(用Kruskal rank衡量)，能被recovery的$x$就可以越dense；现在我们尝试对$A$“性质好”这个说法给一个更准确的定义，从而给L1-minimization一个更准确的适用范围。

---

Pairwise inc oherence

定义矩阵$A\in {\mathbb{R}}^{m\times n}$的pairwise为
$$\delta (A)=\underset{j,k}{\max }\left|\frac{⟨A_j,A_k⟩}{m}-{\delta }_{jk}\right|$$

其中$A_j$表示$A$的第$j$列，$\delta$是Kronecker符号；定义这个量的思路是样本二阶原点矩为$A{A}^T/m$，在高维统计理论部分我们推导过，isotropic的随机向量样本二阶原点矩会concentrate到$I_n$；因此$\delta (A)$可以衡量矩阵$A$所代表的signal是否接近isotropic，如果$\delta (A)$非常小，那么signal就是接近isotropic的。

性质 如果$\delta (A)\le \frac{1}{3s}$，则对于所有满足$|S|\le s$的指标集$S$，矩阵$A$满足restricted nullspace property。

推论 如果$\delta (A)\le \frac{1}{3{\Vert x^{\ast }\Vert }_0}$，则对于所有满足$|S|\le {\Vert x^{\ast }\Vert }_0$的指标集$S$，矩阵$A$满足restricted nullspace property；再根据上一讲介绍的定理，$x^{\ast }$就是basis pursuit的唯一解。

证明 只需说明$A$满足restricted nullspace property即可。取$x\in Null(A)\setminus \{0\}$，则
$$\begin{gathered} Ax=0 \\ {A}_S{x}_X+A_{S^C}{x}_{S^C}=0 \end{gathered}$$

其中
$$\begin{gathered} A=\left[\begin{array}{cc}{A}_S& A_{S^C}\end{array}\right] \\ x=\left[\begin{array}{c}{x}_S\\ x_{S^C}\end{array}\right] \end{gathered}$$

同时左乘$A_S^T/m$，
$$\begin{gathered} \frac{A_S^T{A}_S}{m}{x}_S+\frac{A_S^T{A}_{S^C}}{m}{x}_{S^C}=0 \\ {\Vert \frac{A_S^T{A}_S}{m}{x}_S\Vert }_1={\Vert \frac{A_S^T{A}_{S^C}}{m}{x}_{S^C}\Vert }_1 \end{gathered}$$

其中
$$\begin{gathered} {\Vert \frac{A_S^T{A}_S}{m}{x}_S\Vert }_1={\Vert I{x}_S+\left(\frac{A_S^T{A}_S}{m}-I\right)x_S\Vert }_1 \\ \ge {\Vert x_S\Vert }_1-{\Vert \left(\frac{A_S^T{A}_S}{m}-I\right)x_S\Vert }_1 \end{gathered}$$

记$\frac{A_S^T{A}_S}{m}-I$的pairwise为${\delta }_S$，则
$${\Vert \left(\frac{A_S^T{A}_S}{m}-I\right)x_S\Vert }_1\le s{\delta }_S{\Vert x_S\Vert }_1\le \frac{1}{3}{\Vert x_S\Vert }_1$$

所以
$${\Vert \frac{A_S^T{A}_S}{m}{x}_S\Vert }_1\ge \frac{2}{3}{\Vert x_S\Vert }_1$$

另外，用同样的技巧可以说明，
$${\Vert \frac{A_S^T{A}_{S^C}}{m}{x}_{S^C}\Vert }_1\le s{\Vert \frac{A_S^T{A}_{S^C}}{m}\Vert }_{\infty }{\Vert x_S\Vert }_1\le \frac{1}{3}{\Vert x_S\Vert }_1$$

于是restricted nullspace property成立。

---

Mutual Coherence

Mutual Coherence与Pairwise in Coherence是类似的工具，都是描述$A$的性质的。定义$A$的Mutual Coherence为
$$\mu (X)=\underset{j\ne k}{\max }\left|⟨\frac{A_j}{{\Vert A_j\Vert }_2},\frac{A_k}{{\Vert A_k\Vert }_2}⟩\right|$$

它可以用来衡量$A$列向量spread out的程度，从统计的角度看，如果列向量是centered，那么$\mu (X)$实际上就是样本相关性系数矩阵减去单位阵之差的$L_{\infty }$-norm；

性质 如果$krank(A)\ge \frac{1}{\mu (A)}$，具体一点地说，如果${\Vert x^{\ast }\Vert }_0\le \frac{1}{2\mu (A)}$，则$x^{\ast }$就是L0-minimization的唯一解。

这个性质的相关叙述可以看Wright and Ma (2020)那本高维数据分析的第74-75页，Proposition 3.2的相关内容。

另一个性质 $A\in {\mathbb{R}}^{m\times n}$，并且${\Vert A_j\Vert }_2=1,\forall j$，如果
$$\Vert x^{\ast }\Vert \le \frac{1}{2}(1+\frac{1}{\mu (A)})$$

则$x^{\ast }$是basis pursuit的唯一解。

这个性质的证明可以参考Wright and Ma (2020)那本书的第76页，定理3.3以及评注3.4；原书中定理3.3的条件是
$$\Vert x^{\ast }\Vert \le \frac{1}{2\mu (A)}$$

上文“另一个性质”列的条件是评注3.4中提出的一个更为宽松的条件。

---

RIP

假设design matrix $A$的每一个元素都是iid标准正态的，那么上一讲介绍的Coherence方法就不适用了（因为coherence相关定理条件对Gauss随机矩阵来说比较严格）。这时就需要RIP, restricted isometry property，这个性质是由陶哲轩提出来的，作用是替代coherence作为full recovery的条件，因为Gauss随机矩阵具有RIP的条件比coherence的条件弱，所以RIP更适合design matrix随机（尤其是Gaussian）的情形。

RIP 称矩阵$A\in {\mathbb{R}}^{m\times n}$满足restricted isometry property of order $s$ with constant ${\delta }_s(A)>0$，如果
$${\Vert \frac{A_S^T{A}_S}{m}-I_S\Vert }_2\le {\delta }_s(A)$$

对所有满足$|S|\le s$的指标集均成立。

性质 如果${\delta }_s(A)<1/3$，则$A$满足restricted nullspace property，因此对满足$\Vert x^{\ast }\Vert \le s$的${\theta }^{\ast }$，它一定是basis pursuit的唯一解。

关于RIP与这个性质的完整叙述与推导，需要了解的同学可以看Wright and Ma (2020)的section 3.3

总结

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

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