Sparse Coding综述

Sparse Coding综述"/>

Sparse Coding综述

Sparse Coding学习笔记

• SC的提出
• • ISTA
  • Learned ISTA
• Convolutional Sparse Coding
• Learned Convolutional Sparse Coding
• 对CSC的近似学习
• • 学习Convolutional Dictionary(CD)

SC的提出

ISTA

\qquad 一种用于信号处理SC的经典方法是将其分解为许多atoms 的线性组合，稀疏编码的经典目标函数如下：
m i n ∥ z ∥ 0 , s . t . x = D z (1) min \parallel z \parallel_0 \ ,s.t. \ x=Dz \tag{1} min∥z∥0​ ,s.t. x=Dz(1)

其中 z ∈ R m \ z\in \mathbb{R^m}  z∈Rm是原信号 x ∈ R n \ x \in \mathbb{R^n}  x∈Rn对于 D ∈ R n × m \ D\in \mathbb{R^{n \times m}}  D∈Rn×m的稀疏编码(或叫做稀疏表示)

\qquad 然而，直接求解上式是一个组合问题，其复杂度随着 m m m呈指数增长。通常用 l 1 \ l_1  l1​正则来代替 l 0 \, l_0 l0​
arg min ⁡ D , z 1 2 ∥ x − D z ∥ 2 2 + λ ∥ z ∥ 1 (2) {\underset {D,z}{\operatorname {arg\,min} }} \frac{1}{2}\parallel x-Dz \parallel_2^2 + \lambda \parallel z \parallel_1 \tag{2} D,zargmin​21​∥x−Dz∥22​+λ∥z∥1​(2)

\qquad 最早优化上式的方法是 ISTA 迭代法：

z k + 1 = S λ / L ( z k + 1 L D T ( x − D z k ) ) (3) z_{k+1} = S_{\lambda /L }(z_{k} + \frac{1}{L}D^T(x-Dz_k)) \tag{3} zk+1​=Sλ/L​(zk​+L1​DT(x−Dzk​))(3)
其中 L ≤ σ m a x ( D T D ) L \leq \sigma_{max} (D^T D) L≤σmax​(DTD), σ m a x ( A ) \sigma_{max} (A) σmax​(A)是A的最大特征值， S θ ( x ) S_{\theta}(x) Sθ​(x)是 soft thresholding operator(软阈值函数)：
S θ ( x ) = s i g n ( x ) m a x ( ∣ x ∣ − θ , 0 ) (4) S_\theta(x) = sign(x)max(|x| - \theta, 0) \tag{4} Sθ​(x)=sign(x)max(∣x∣−θ,0)(4)
当满足定义的收敛准则时停止 ISTA 迭代

Learned ISTA

\qquad 在近似SC方面，可以建立非线编码器，该编码器可以被训练以产生给定信号的快速近似SC。

将 ISTA 迭代公式变换如下

z k + 1 = S λ / L ( ( I − 1 L D T D ) z k + 1 L D T x ) (5) z_{k+1} = S_{\lambda/L}((I-\frac{1}{L}D^TD)z_k + \frac{1}{L}D^Tx) \tag{5} zk+1​=Sλ/L​((I−L1​DTD)zk​+L1​DTx)(5)

化简
z 0 = 0 , k = 0 , … , K − 1 z k + 1 = S θ ( S z k + W e X ) (6) z_0 = 0, k=0,\dots,K-1 \\ z_{k+1} = S_\theta(Sz_k + W_e X) \tag{6} z0​=0,k=0,…,K−1zk+1​=Sθ​(Szk​+We​X)(6)

用网络结构来表示

Convolutional Sparse Coding

\qquad 与传统SC不同的是，CSC采用了卷积操作来代替矩阵相乘操作，用公式表示如下：
x = ∑ i = 0 m − 1 d i ∗ z i (7) x = \sum_{i=0}^{m-1} d_i \ \ast z_i \tag{7} x=i=0∑m−1​di​ ∗zi​(7)
其中， x ∈ R n 1 × n 2 x \in \mathbb{R}^{n_1 \times n_2} x∈Rn1​×n2​是 输入的信号， d i ∈ R k × k d_i \in \mathbb{R}^{k \times k} di​∈Rk×k 是局部的卷积核， z i ∈ R n 1 × n 2 z_i \in \mathbb{R}^{n_1 \times n_2} zi​∈Rn1​×n2​ 是对应于 d i d_i di​ 的稀疏特征图.

则CSC的 l 1 l_1 l1​ 最小化问题可以描述为：

arg min ⁡ d , z 1 2 ∥ x − ∑ i = 0 m − 1 d i ∗ z i ∥ 2 2 + λ ∑ i = 0 m − 1 ∥ z i ∥ 1 (8) {\underset {d,z}{\operatorname {arg\,min} }} \frac{1}{2} \parallel x-\sum_{i=0}^{m-1} d_i \ \ast z_i \parallel_2^2 + \lambda \sum_{i=0}^{m-1} \parallel z_i \parallel_1 \tag{8} d,zargmin​21​∥x−i=0∑m−1​di​ ∗zi​∥22​+λi=0∑m−1​∥zi​∥1​(8)

\qquad 值得注意的是，与传统的SC不同，输入x不再需要被分割成patches， CSC输入的是一个整体。CSC模型本质上是空间不变的，所以，我们学习出来特定边缘方向的atom可以代表整体图像的边缘方向。

\qquad 一个解决上式的方法是变换到频域，用Alternating Direction Method of Multipliers(ADMM) 进行优化

Learned Convolutional Sparse Coding

对CSC的近似学习

\qquad 由于卷积的线性性质，而且字典 D c o n v ∈ R ( n 1 n 2 ) × ( n 1 n 2 m ) D_{conv} \in \mathbb{R}^{(n_1n_2)\times(n_1n_2m)} Dconv​∈R(n1​n2​)×(n1​n2​m) 是Toepltiz矩阵的串联，所以CSC可以被看作传统SC的一种特殊情况。因此, (8)中的目标可以通过将 D D D替换为 D c o n v D_{conv} Dconv​来格式化为类似 (2)
\qquad 在这里不是直接在 D c o n v D_{conv} Dconv​ 上用标准的 LISTA ，而是重新构造 ISTA 的卷积形式，然后提出其 LISTA 版本。
\qquad CSC的ISTA迭代可以写成下面形式：
z k + 1 = S λ / L ( z k + 1 L d ⋆ ( x − d ∗ z k ) ) (9) z_{k+1} = S_{\lambda/L}(z_k + \frac{1}{L}d \star(x-d\ast z_k)) \tag{9} zk+1​=Sλ/L​(zk​+L1​d⋆(x−d∗zk​))(9)
其中， d ∈ R s × s × m d \in \mathbb{R}^{s \times s \times m} d∈Rs×s×m是一个含有 m个 s × s s \times s s×s卷积核的矩阵， d ⋆ x = [ f l i p ( d 0 ) ∗ x , … , f l i p ( d m − 1 ) ∗ x ] d \star x=[flip(d_0)\ast x, \dots,flip(d_{m-1})\ast x] d⋆x=[flip(d0​)∗x,…,flip(dm−1​)∗x], 以及 d ∗ z = ∑ i = 0 m − 1 d i ∗ z i d \ast z = \sum_{i=0}^{m-1} d_i \ast z_i d∗z=∑i=0m−1​di​∗zi​.操作 f l i p ( d i ) flip(d_i) flip(di​)是将输入 d i d_i di​的两个维度顺序颠倒过来.
\qquad 将（9）用相似的方法变成（6）得到 convolutional LISTA结构：
z k + 1 = S θ ( z k + W e ∗ ( x − W d ∗ z k ) ) (10) z_{k+1} = S_\theta(z_k+W_e \ast(x-W_d\ast z_k)) \tag{10} zk+1​=Sθ​(zk​+We​∗(x−Wd​∗zk​))(10)
其中， W e ∈ R s × s × c × m , W d ∈ R s × s × m × c W_e \in \mathbb{R}^{s\times s \times c \times m},W_d\in \mathbb{R}^{s\times s \times m \times c} We​∈Rs×s×c×m,Wd​∈Rs×s×m×c，即 W d = d , W e = f l i p ( W d ) W_d = d, W_e=flip(W_d) Wd​=d,We​=flip(Wd​)以及 θ ∈ R + m \theta \in \mathbb{R}_+^m θ∈R+m​是完全可训练的独立变量，注意到这里加上了多通道 c

学习Convolutional Dictionary(CD)

\qquad 我们通过approximate CSC (ACSC)希望产生一个 x ^ \hat{x} x^ ，尽可能地接近 x x x .所以在 convolutional ISTA的末尾，加上了一个由 d d d组成的线性编码器
z 0 = 0 , k = 0 , … , K − 1 z k + 1 = S θ ( z k + W e ∗ ( x − W d ∗ z k ) ) z A C S C = z K , x ^ = d ∗ z A C S C \begin{aligned} z_0=&0,\quad k=0,\dots,K-1\\ z_{k+1} =& S_\theta(z_k+W_e \ast(x-W_d\ast z_k)) \\ z_{ACSC} =& z_{K} , \quad \hat{x} =d*z_{ACSC} \end{aligned} z0​=zk+1​=zACSC​=​0,k=0,…,K−1Sθ​(zk​+We​∗(x−Wd​∗zk​))zK​,x^=d∗zACSC​​