UA MATH567 高維統計專題1 稀疏信號及其恢復2 用L1-norm作為L0-norm的convex relexation

• • $L_1$-norm minimization
  • • $L_1$-norm是$L_0$-norm的凸包絡
    • $L_1$-norm minimization的full recovery

上一講我們在無噪聲的設定下討論了稀疏信號的恢復，假設$y$是我們對稀疏信號的測量，$y=A{x}_o$，系數$A$已知，目標是從測量中還原出信號$x_o$，一種可行的操作是在$y=Ax$的解集中找到最稀疏的向量，以此作為sparse signal的估計，所以要求解的問題是：
$$\begin{gathered} \min {\Vert x\Vert }_0 \\ s.t.y=Ax \end{gathered}$$

用Exhaustive Search可以求解這個問題，當$x_o$足夠sparse的時候（${\Vert x_o\Vert }_0\le \frac{1}{2}krank(A)$），$L_0$-norm minimization可以把$x_o$準確還原出來，其中$krank(A)$為矩陣$A$的Kruskal rank，任意$krank(A)$個$A$的列向量線性無關，但存在$krank(A)+1$個$A$的列向量線性相關。遺憾的是，$L_0$-norm minimization是NP-hard問題，我們無法保證求解$L_0$-norm minimization的算法會在多久以后收斂，因此$L_0$-norm minimization的實用價值不大。

這一講我們討論，既然實踐中無法使用$L_0$-norm minimization，那能不能設計一些近似的算法，讓我們在時間復雜度與近似誤差之間有做取舍的余地？

---

$L_1$-norm minimization

可以簡單回憶一下，在凸優化中我們討論過的優化問題的relaxation，因為凸優化是多項式時間復雜度問題，所以我們可以找$L_0$-norm minimization的convex relaxation作為它的近似。上一講我們討論了$L_p$-norm中$p$最小的鄰域為凸集的是$L_1$-norm，因為$p$越小，鄰域中的向量越sparse，所以我們有理由相信，$L_1$-norm minimization是$L_0$-norm minimization的一種優秀convex relaxation。同樣考慮無噪聲的情況：

$$\begin{gathered} \min {\Vert x\Vert }_1=\sum _{i=1}^n|x_i| \\ s.t.y=Ax \end{gathered}$$

我們稱這個問題為basis pursuit。

$L_1$-norm是$L_0$-norm的凸包絡

考慮$B_{\infty }=\{x:{\Vert x\Vert }_{\infty }=1\}$，$L_1$-norm是$L_0$-norm的凸包絡的含義是，對任意凸函數$f:B_{\infty }\to \mathbb{R}$，如果$?x\in B_{\infty }$，$f(x)\le {\Vert x\Vert }_0$，則$f(x)\le {\Vert x\Vert }_1$。引入Hamming cube上的向量$\sigma \in \{0,1{\}}^n$，則$?x\in B_{\infty }$，我們可以用Hamming cube中的向量作為$x$的基：
$$x=\sum _{i=1}^N{\lambda }_i{\sigma }_i$$

$f(x)\le {\Vert x\Vert }_0$說明
$$f({\sigma }_i)\le {\Vert {\sigma }_i\Vert }_0$$

Hamming cube上的向量滿足${\Vert {\sigma }_i\Vert }_0={\Vert {\sigma }_i\Vert }_1$，所以我們用Jensen不等式：
$$\begin{gathered} f(x)=f(\sum _{i=1}^N{\lambda }_i{\sigma }_i)\le \sum _{i=1}^N{\lambda }_{i}f({\sigma }_i)\le \sum _{i=1}^N{\lambda }_i{\Vert {\sigma }_i\Vert }_0 \\ =\sum _{i=1}^N{\lambda }_i{\Vert {\sigma }_i\Vert }_1\le \sum _{i=1}^N|{\lambda }_i|{\Vert {\sigma }_i\Vert }_1={\Vert x\Vert }_1 \end{gathered}$$

$L_1$-norm minimization的full recovery

我們知道$L_0$-norm minimization在signal足夠sparse的情況下可以把signal準確還原出來，也就是可以實現full recovery，那么$L_1$-norm minimization是否有類似的性質？

一種可能的情況：考慮$y=Ax$的解空間，因為$x_o$是一個特解，所以$y=Ax$的解空間為$x_o+Null(A)$，也就是基于核空間$Null(A)$做平移得到的一個線性流形，如果$x_o+Null(A)\cap \{x:{\Vert x\Vert }_1\le {\Vert x_o\Vert }_1\}=x_o$，那么
$$\underset{x\in x_o+Null(A)}{\mathrm{argmin}}{\Vert x\Vert }_1=x_o$$

簡單地說，就是可行域與目標函數的contour使得$L_1$-norm minimization取角點解時，$L_1$-norm minimization實現full recovery。

評注
$L_0$-norm不滿足正齊次性，所以變換$x$的單位、乘除一個常數不會影響$x$的$L_0$-norm；但是$L_1$-norm是一個范數，滿足正齊次性，所以變換$x$的單位、乘除一個常數會影響$x$的$L_1$-norm；那么在$L_1$-norm minimization的實踐中是否標準化$x$？在統計學文獻中，我們一般把隨機向量方差標準化，或者把隨機矩陣的列向量的方差標準化。

我們把上面那個簡單情況抽象化，定義指標集$S?\{1,?,n\}$，基于指標集定義一個cone：
$$C(S)=\{\Delta \in {\mathbb{R}}^n:{\Vert {\Delta }_{S^C}\Vert }_1\le {\Vert {\Delta }_S\Vert }_1\}$$

cone這種結構的好處是cone中的任一向量乘除一個常數后依然屬于這個cone，這樣就湊出了$L_0$-norm的scale-invariant的特點。稱矩陣$A$關于指標集$S$有restricted nullspace property如果
$$C(S)\cap Null(A)=\{0\}$$

定理 假設$x_o$非零的元素的指標構成指標集$S$，則basis pursuit的唯一解為$x_o$的充要條件是$A$關于指標集$S$有restricted nullspace property。

證明
$?$: 記$\hat{x}$為basis pursuit的解，則$y=A\hat{x}=A{x}_o$，并且${\Vert \hat{x}\Vert }_1\le {\Vert x_o\Vert }_1$，前者說明
$$\Delta ?\hat{x}?x_o\in null(A)$$

計算
$$\begin{gathered} {\Vert x_{oS}\Vert }_1={\Vert x_o\Vert }_1\ge {\Vert \hat{x}\Vert }_1={\Vert x_o+\Delta \Vert }_1 \\ ={\Vert x_o+{\Delta }_S+{\Delta }_{S^C}\Vert }_1\ge {\Vert x_o\Vert }_1?{\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(S)$$

根據restricted nullspace property，
$$C(S)\cap Null(A)=\{0\}$$

因為$S$是$x_o$的支撐集的指標集，所以上式等價于$$x_o+Null(A)\cap \{x:{\Vert x\Vert }_1\le {\Vert x_o\Vert }_1\}=x_o$$

因此
$$\underset{x\in x_o+Null(A)}{\mathrm{argmin}}{\Vert x\Vert }_1=x_o$$

$?$: $?x^{?}\in Null(A)?\{0\}$，考慮basis pursuit，
$$\min {\Vert x\Vert }_{1}s.t.Ax=A\left[\begin{array}{c}{x}_S^{?}\\ 0\end{array}\right]$$

根據假設，它的唯一解為
$$\hat{x}=\left[\begin{array}{c}{x}_S^{?}\\ 0\end{array}\right]$$

因為$A{x}^{?}=0$，也就是
$$A\left[\begin{array}{c}{x}_S^{?}\\ x_{S^C}^{?}\end{array}\right]=0?A\left[\begin{array}{c}{x}_S^{?}\\ 0\end{array}\right]=A\left[\begin{array}{c}0\\ ?x_{S^C}^{?}\end{array}\right]$$

也就是說$\left[\begin{array}{c}0\\ ?x_{S^C}^{?}\end{array}\right]$也是一個可行解，因此
$$\begin{gathered} {\Vert \left[\begin{array}{c}0\\ ?x_{S^C}^{?}\end{array}\right]\Vert }_1\ge {\Vert \left[\begin{array}{c}{x}_S^{?}\\ 0\end{array}\right]\Vert }_1 \\ {\Vert {\theta }_{S^C}^{?}\Vert }_1\ge {\Vert {\theta }_S^{?}\Vert }_1 \end{gathered}$$

所以${\theta }^{?}\in C(S)$

總結

以上是生活随笔為你收集整理的UA MATH567 高维统计专题1 稀疏信号及其恢复2 用L1-norm作为L0-norm的convex relexation的全部內容，希望文章能夠幫你解決所遇到的問題。

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