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^{?}\Vert }_0}$，則對于所有滿足$|S|\le {\Vert x^{?}\Vert }_0$的指標集$S$，矩陣$A$滿足restricted nullspace property；再根據上一講介紹的定理，$x^{?}$就是basis pursuit的唯一解。

證明 只需說明$A$滿足restricted nullspace property即可。取$x\in Null(A)?\{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=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^{?}\Vert }_0\le \frac{1}{2\mu (A)}$，則$x^{?}$就是L0-minimization的唯一解。

這個性質的相關敘述可以看Wright and Ma (2020)那本高維數據分析的第74-75頁，Proposition 3.2的相關內容。

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

則$x^{?}$是basis pursuit的唯一解。

這個性質的證明可以參考Wright and Ma (2020)那本書的第76頁，定理3.3以及評注3.4；原書中定理3.3的條件是
$$\Vert x^{?}\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^{?}\Vert \le s$的${\theta }^{?}$，它一定是basis pursuit的唯一解。

關于RIP與這個性質的完整敘述與推導，需要了解的同學可以看Wright and Ma (2020)的section 3.3

總結

以上是生活随笔為你收集整理的UA MATH567 高维统计专题1 稀疏信号及其恢复3 Coherence与RIP简介的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。