[!IMPORTANT]
本章学习时间：3天
本章配套视频教程：https://www.bilibili.com/video/BV1Mh411e7VU?p=17
11.1 子集搜索与评价
开篇给出了 "特征选择" 的概念, 并谈到特征选择与第 10
本节涉及 "子集评价" 的式(14.1)和式(14.2)与第 4 章的式(4.2)和式(4.1)相同,
11.1.1 式(11.1)的解释
此为信息增益的定义式，对数据集 D D D A A A A A A D D D V V V { D 1 , D 2 , … , D V } \left\{D^1, D^2, \ldots, D^V\right\} { D 1 , D 2 , … , D V } D D D D v D^v D v
11.1.2 式(11.2)的解释
Ent ( D ) = − ∑ i = 1 ∣ Y ∣ p k log 2 p k \operatorname{Ent}(D)=-\sum_{i=1}^{| \mathcal{Y |}} p_{k} \log _{2} p_{k} Ent ( D ) = − i = 1 ∑ ∣ Y ∣ p k log 2 p k
此为信息熵的定义式，其中p k , k = 1 , 2 , … ∣ Y ∣ p_k, k=1, 2, \dots \vert\mathcal{Y}\vert p k , k = 1 , 2 , … ∣ Y ∣ D D D i i i p k → 0 p_k\rightarrow 0 p k → 0 p k → 1 p_k\rightarrow 1 p k → 1 E n t ( D ) \mathrm{Ent}(D) Ent ( D ) p i = 1 , p \ i = 0 , i = 1 , 2 , … , ∣ Y ∣ p_i=1, p_{\backslash i}=0, i=1, 2, \dots, \vert\mathcal{Y}\vert p i = 1 , p \ i = 0 , i = 1 , 2 , … , ∣ Y ∣
11.2 过滤式选择
"过滤式方法先对数据集进行特征选择, 然后再训练学习器,
从式(11.3)可以看出, Relief 方法本质上基于δ j \delta^j δ j diff ( x i j , x i , n h j ) 2 \operatorname{diff}\left(x_i^j, x_{i, \mathrm{nh}}^j\right)^2 diff ( x i j , x i , nh j ) 2 diff ( x i j , x i , n m j ) 2 \operatorname{diff}\left(x_i^j, x_{i, \mathrm{~nm}}^j\right)^2 diff ( x i j , x i , nm j ) 2 δ j \delta^j δ j
对于能处理多分类问题的扩展变量 Relief-F, 由于有多个异类,
11.2.1 包裹式选择
"与过滤式特征选择不考虑后续学习器不同,
图 11.1 11.1 11.1 E = ∞ E=\infty E = ∞ d = ∣ A ∣ d=|A| d = ∣ A ∣ ∣ A ∣ |A| ∣ A ∣ A A A E ′ < E E^{\prime}<E E ′ < E L \mathfrak{L} L A ′ A^{\prime} A ′ A A A ( E ′ = E ) ∨ ( d ′ < d ) \left(E^{\prime}=E\right) \vee\left(d^{\prime}<d\right) ( E ′ = E ) ∨ ( d ′ < d ) L \mathfrak{L} L A ′ A^{\prime} A ′ A A A A ′ A^{\prime} A ′ V V V t t t t t t
最后, 本节 LVW 算法基于拉斯维加斯方法框架,
蒙特卡罗算法------采样越多, 越近似最优解；
拉斯维加斯算法------采样越多, 越有机会找到最优解。
举个例子, 假如筐里有 100 个苹果, 让我每次闭眼拿 1 个,
11.3 嵌入式选择与L1正则化
"嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。"，具体可以对比本节式(11.7)的例子与前两节方法的本质区别，细细体会本节第一段的这句有关"嵌入式"的概念描述。
11.3.1 式(11.5)的解释
该式为线性回归的优化目标式，y i y_i y i i i i w ⊤ x i w^\top x_i w ⊤ x i
11.3.2 式(11.6)的解释
该式为加入了L 2 \mathrm{L}_2 L 2 λ \lambda λ w w w
11.3.3 式(11.7)的解释
该式将11.6中的L 2 \mathrm{L}_2 L 2 L 1 \mathrm{L}_1 L 1 L 2 \mathrm{L}_2 L 2 L 1 \mathrm{L}_1 L 1 L 1 \mathrm{L}_1 L 1
11.3.4 式(11.8)的解释
从本式开始至本节结束, 都在介绍近端梯度下降求解 L 1 L_1 L 1 f ( w ) = ∑ i = 1 m ( y i − w ⊤ x i ) 2 f(\boldsymbol{w})=\sum_{i=1}^m\left(y^i-\boldsymbol{w}^{\top} \boldsymbol{x}_i\right)^2 f ( w ) = ∑ i = 1 m ( y i − w ⊤ x i ) 2 w \boldsymbol{w} w x \boldsymbol{x} x f ( w ) f(\boldsymbol{w}) f ( w ) ∇ f ( w ) = − ∑ i = 1 m 2 ( y i − w ⊤ x i ) x i \nabla f(\boldsymbol{w})=-\sum_{i=1}^m 2\left(y^i-\boldsymbol{w}^{\top} \boldsymbol{x}_i\right) \boldsymbol{x}_i ∇ f ( w ) = − ∑ i = 1 m 2 ( y i − w ⊤ x i ) x i
11.3.5 式(11.9)的解释
该式即为 L L L
∥ ∇ f ( x ′ ) − ∇ f ( x ) ∥ 2 ∥ x ′ − x ∥ 2 ⩽ L , ( ∀ x , x ′ ) \frac{\left\|\nabla f\left(\boldsymbol{x}^{\prime}\right)-\nabla f(\boldsymbol{x})\right\|_2}{\left\|\boldsymbol{x}^{\prime}-\boldsymbol{x}\right\|_2} \leqslant L, \quad\left(\forall \boldsymbol{x}, \boldsymbol{x}^{\prime}\right) ∥ x ′ − x ∥ 2 ∥ ∇ f ( x ′ ) − ∇ f ( x ) ∥ 2 ⩽ L , ( ∀ x , x ′ )
进一步地, 若 x ′ → x \boldsymbol{x}^{\prime} \rightarrow \boldsymbol{x} x ′ → x
lim x ′ → x ∥ ∇ f ( x ′ ) − ∇ f ( x ) ∥ 2 ∥ x ′ − x ∥ 2 \lim _{\boldsymbol{x}^{\prime} \rightarrow \boldsymbol{x}} \frac{\left\|\nabla f\left(\boldsymbol{x}^{\prime}\right)-\nabla f(\boldsymbol{x})\right\|_2}{\left\|\boldsymbol{x}^{\prime}-\boldsymbol{x}\right\|_2} x ′ → x lim ∥ x ′ − x ∥ 2 ∥ ∇ f ( x ′ ) − ∇ f ( x ) ∥ 2
这明显是在求解函数 ∇ f ( x ) \nabla f(\boldsymbol{x}) ∇ f ( x ) f ( x ) f(\boldsymbol{x}) f ( x ) L L L L L L
"Lipschitz连续" 可以形象得理解为: 以陆地为例,
11.3.6 式(11.10)的推导
首先注意优化目标式和11.7x x x w w w L − L i p s c h i t z L\mathrm{-Lipschitz} L − Lipschitz
∣ ∇ f ( x ′ ) − ∇ f ( x ) ∣ ⩽ L ∣ x ′ − x ∣ ( ∀ x , x ′ ) \left\vert\nabla f\left(\boldsymbol{x}^{\prime}\right)-\nabla f(\boldsymbol{x})\right\vert \leqslant L\left\vert\boldsymbol{x}^{\prime}-\boldsymbol{x}\right\vert \quad\left(\forall \boldsymbol{x}, \boldsymbol{x}^{\prime}\right) ∣ ∇ f ( x ′ ) − ∇ f ( x ) ∣ ⩽ L ∣ x ′ − x ∣ ( ∀ x , x ′ )
移项得
∣ ∇ f ( x ′ ) − ∇ f ( x ) ∣ ∣ x ′ − x ∣ ⩽ L ( ∀ x , x ′ ) \frac{\left|\nabla f\left(\boldsymbol{x}^{\prime}\right)-\nabla f(\boldsymbol{x})\right|}{\vert x^\prime - x\vert}\leqslant L \quad\left(\forall \boldsymbol{x}, \boldsymbol{x}^{\prime}\right) ∣ x ′ − x ∣ ∣ ∇ f ( x ′ ) − ∇ f ( x ) ∣ ⩽ L ( ∀ x , x ′ )
由于上式对所有的x , x ′ x, x^\prime x , x ′ f ( x ) f(x) f ( x ) L L L
∇ 2 f ( x ) ⩽ L \nabla^2f(x)\leqslant L ∇ 2 f ( x ) ⩽ L
得到这个结论之后，我们来推导式11.10。x k x_k x k f ( x ) f(x) f ( x )
f ^ ( x ) ≃ f ( x k ) + ⟨ ∇ f ( x k ) , x − x k ⟩ + ∇ 2 f ( x k ) 2 ∥ x − x k ∥ 2 ⩽ f ( x k ) + ⟨ ∇ f ( x k ) , x − x k ⟩ + L 2 ∥ x − x k ∥ 2 = f ( x k ) + ∇ f ( x k ) ⊤ ( x − x k ) + L 2 ( x − x k ) ⊤ ( x − x k ) = f ( x k ) + L 2 ( ( x − x k ) ⊤ ( x − x k ) + 2 L ∇ f ( x k ) ⊤ ( x − x k ) ) = f ( x k ) + L 2 ( ( x − x k ) ⊤ ( x − x k ) + 2 L ∇ f ( x k ) ⊤ ( x − x k ) + 1 L 2 ∇ f ( x k ) ⊤ ∇ f ( x k ) ) − 1 2 L ∇ f ( x k ) ⊤ ∇ f ( x k ) = f ( x k ) + L 2 ( ( x − x k ) + 1 L ∇ f ( x k ) ) ⊤ ( ( x − x k ) + 1 L ∇ f ( x k ) ) − 1 2 L ∇ f ( x k ) ⊤ ∇ f ( x k ) = L 2 ∥ x − ( x k − 1 L ∇ f ( x k ) ) ∥ 2 2 + c o n s t \begin{aligned}
\hat{f}(\boldsymbol{x}) & \simeq f\left(\boldsymbol{x}_{k}\right)+\left\langle\nabla f\left(\boldsymbol{x}_{k}\right), \boldsymbol{x}-\boldsymbol{x}_{k}\right\rangle+\frac{\nabla^2f(x_k)}{2}\left\|\boldsymbol{x}-\boldsymbol{x}_{k}\right\|^{2} \\
&\leqslant
f\left(\boldsymbol{x}_{k}\right)+\left\langle\nabla f\left(\boldsymbol{x}_{k}\right), \boldsymbol{x}-\boldsymbol{x}_{k}\right\rangle+\frac{L}{2}\left\|\boldsymbol{x}-\boldsymbol{x}_{k}\right\|^{2} \\
&= f\left(\boldsymbol{x}_{k}\right)+\nabla f\left(\boldsymbol{x}_{k}\right)^{\top}\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)+\frac{L}{2}\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)^{\top}\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)\\
&=f(x_k)+\frac{L}{2}\left(\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)^{\top}\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)+\frac{2}{L}\nabla f\left(\boldsymbol{x}_{k}\right)^{\top}\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)\right)\\
&=f(x_k)+\frac{L}{2}\left(\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)^{\top}\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)+\frac{2}{L}\nabla f\left(\boldsymbol{x}_{k}\right)^{\top}\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)+\frac{1}{L^2}\nabla f(x_k)^\top\nabla f(x_k)\right) -\frac{1}{2L}\nabla f(x_k)^\top\nabla f(x_k)\\
&=f(x_k)+\frac{L}{2}\left(\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)+\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)\right)^{\top}\left(\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)+\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)\right)-\frac{1}{2L}\nabla f(x_k)^\top\nabla f(x_k)\\
&=\frac{L}{2}\left\|\boldsymbol{x}-\left(\boldsymbol{x}_{k}-\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)\right)\right\|_{2}^{2}+\mathrm{const}
\end{aligned} f ^ ( x ) ≃ f ( x k ) + ⟨ ∇ f ( x k ) , x − x k ⟩ + 2 ∇ 2 f ( x k ) ∥ x − x k ∥ 2 ⩽ f ( x k ) + ⟨ ∇ f ( x k ) , x − x k ⟩ + 2 L ∥ x − x k ∥ 2 = f ( x k ) + ∇ f ( x k ) ⊤ ( x − x k ) + 2 L ( x − x k ) ⊤ ( x − x k ) = f ( x k ) + 2 L ( ( x − x k ) ⊤ ( x − x k ) + L 2 ∇ f ( x k ) ⊤ ( x − x k ) ) = f ( x k ) + 2 L ( ( x − x k ) ⊤ ( x − x k ) + L 2 ∇ f ( x k ) ⊤ ( x − x k ) + L 2 1 ∇ f ( x k ) ⊤ ∇ f ( x k ) ) − 2 L 1 ∇ f ( x k ) ⊤ ∇ f ( x k ) = f ( x k ) + 2 L ( ( x − x k ) + L 1 ∇ f ( x k ) ) ⊤ ( ( x − x k ) + L 1 ∇ f ( x k ) ) − 2 L 1 ∇ f ( x k ) ⊤ ∇ f ( x k ) = 2 L x − ( x k − L 1 ∇ f ( x k ) ) 2 2 + const
其中c o n s t = f ( x k ) − 1 2 L ∇ f ( x k ) ⊤ ∇ f ( x k ) \mathrm{const}=f(x_k)-\frac{1}{2 L} \nabla f\left(x_{k}\right)^{\top} \nabla f\left(x_{k}\right) const = f ( x k ) − 2 L 1 ∇ f ( x k ) ⊤ ∇ f ( x k )
11.3.7 式(11.11)的解释
这个很容易理解，因为2范数的最小值为0，当x k + 1 = x k − 1 L ∇ f ( x k ) \boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}-\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right) x k + 1 = x k − L 1 ∇ f ( x k ) f ^ ( x k + 1 ) ⩽ f ^ ( x k ) \hat{f}(x_{k+1})\leqslant\hat{f}(x_k) f ^ ( x k + 1 ) ⩽ f ^ ( x k ) f ^ ( x k + 2 ) ⩽ f ^ ( x k + 1 ) , ⋯ \hat{f}(x_{k+2})\leqslant\hat{f}(x_{k+1}), \cdots f ^ ( x k + 2 ) ⩽ f ^ ( x k + 1 ) , ⋯ f ^ ( x ) \hat{f}(x) f ^ ( x )
11.3.8 式(11.12)的解释
注意 f ^ ( x ) \hat{f}(\boldsymbol{x}) f ^ ( x )
f ^ ( x k − 1 L ∇ f ( x k ) ) ⩽ f ^ ( x k ) \hat{f}\left(\boldsymbol{x}_k-\frac{1}{L} \nabla f\left(\boldsymbol{x}_k\right)\right) \leqslant \hat{f}\left(\boldsymbol{x}_k\right) f ^ ( x k − L 1 ∇ f ( x k ) ) ⩽ f ^ ( x k )
在式(11.10)推导中有f ( x ) ⩽ f ^ ( x ) f(\boldsymbol{x}) \leqslant \hat{f}(\boldsymbol{x}) f ( x ) ⩽ f ^ ( x )
f ( x k − 1 L ∇ f ( x k ) ) ⩽ f ^ ( x k − 1 L ∇ f ( x k ) ) f\left(\boldsymbol{x}_k-\frac{1}{L} \nabla f\left(\boldsymbol{x}_k\right)\right) \leqslant \hat{f}\left(\boldsymbol{x}_k-\frac{1}{L} \nabla f\left(\boldsymbol{x}_k\right)\right) f ( x k − L 1 ∇ f ( x k ) ) ⩽ f ^ ( x k − L 1 ∇ f ( x k ) )
在式(11.10)推导中还知道f ( x k ) = f ^ ( x k ) f\left(\boldsymbol{x}_k\right)=\hat{f}\left(\boldsymbol{x}_k\right) f ( x k ) = f ^ ( x k )
f ( x k − 1 L ∇ f ( x k ) ) ⩽ f ^ ( x k − 1 L ∇ f ( x k ) ) ⩽ f ^ ( x k ) = f ( x k ) f\left(\boldsymbol{x}_k-\frac{1}{L} \nabla f\left(\boldsymbol{x}_k\right)\right) \leqslant \hat{f}\left(\boldsymbol{x}_k-\frac{1}{L} \nabla f\left(\boldsymbol{x}_k\right)\right) \leqslant \hat{f}\left(\boldsymbol{x}_k\right)=f\left(\boldsymbol{x}_k\right) f ( x k − L 1 ∇ f ( x k ) ) ⩽ f ^ ( x k − L 1 ∇ f ( x k ) ) ⩽ f ^ ( x k ) = f ( x k )
也就是说通过迭代x k + 1 = x k − 1 L ∇ f ( x k ) \boldsymbol{x}_{k+1}=\boldsymbol{x}_k-\frac{1}{L} \nabla f\left(\boldsymbol{x}_k\right) x k + 1 = x k − L 1 ∇ f ( x k ) f ( x ) f(\boldsymbol{x}) f ( x )
同理, 对于函数g ( x ) = f ( x ) + λ ∥ x ∥ 1 g(\boldsymbol{x})=f(\boldsymbol{x})+\lambda\|\boldsymbol{x}\|_1 g ( x ) = f ( x ) + λ ∥ x ∥ 1 g ^ ( x ) = f ^ ( x ) + λ ∥ x ∥ 1 \hat{g}(\boldsymbol{x})=\hat{f}(\boldsymbol{x})+\lambda\|\boldsymbol{x}\|_1 g ^ ( x ) = f ^ ( x ) + λ ∥ x ∥ 1 g ^ ( x ) = f ^ ( x ) + λ ∥ x ∥ 1 ∘ \hat{g}(\boldsymbol{x})=\hat{f}(\boldsymbol{x})+\lambda\|\boldsymbol{x}\|_{1^{\circ}} g ^ ( x ) = f ^ ( x ) + λ ∥ x ∥ 1 ∘
以上优化方法被称为Majorization-Minimization。可以搜索相关资料做详细了解。
11.3.9 式(11.13)的解释
这里将式11.12的优化步骤拆分成了两步，首先令z = x k − 1 L ∇ f ( x k ) z=x_{k}-\frac{1}{L} \nabla f\left(x_{k}\right) z = x k − L 1 ∇ f ( x k ) z z z
11.3.10 式(11.14)的推导
令优化函数
g ( x ) = L 2 ∥ x − z ∥ 2 2 + λ ∥ x ∥ 1 = L 2 ∑ i = 1 d ∥ x i − z i ∥ 2 2 + λ ∑ i = 1 d ∥ x i ∥ 1 = ∑ i = 1 d ( L 2 ( x i − z i ) 2 + λ ∣ x i ∣ ) \begin{aligned}
g(\boldsymbol{x}) &=\frac{L}{2}\|\boldsymbol{x}-\boldsymbol{z}\|_{2}^{2}+\lambda\|\boldsymbol{x}\|_{1} \\
&=\frac{L}{2} \sum_{i=1}^{d}\left\|x^{i}-z^{i}\right\|_{2}^{2}+\lambda \sum_{i=1}^{d}\left\|x^{i}\right\|_{1} \\
&=\sum_{i=1}^{d}\left(\frac{L}{2}\left(x^{i}-z^{i}\right)^{2}+\lambda\left|x^{i}\right|\right)
\end{aligned} g ( x ) = 2 L ∥ x − z ∥ 2 2 + λ ∥ x ∥ 1 = 2 L i = 1 ∑ d x i − z i 2 2 + λ i = 1 ∑ d x i 1 = i = 1 ∑ d ( 2 L ( x i − z i ) 2 + λ x i )
这个式子表明优化g ( x ) g(\boldsymbol{x}) g ( x ) x \boldsymbol{x} x x i x^i x i
g ( x i ) = L 2 ( x i − z i ) 2 + λ ∣ x i ∣ g\left(x^{i}\right)=\frac{L}{2}\left(x^{i}-z^{i}\right)^{2}+\lambda\left|x^{i}\right| g ( x i ) = 2 L ( x i − z i ) 2 + λ x i
求导得
d g ( x i ) d x i = L ( x i − z i ) + λ s g n ( x i ) \frac{d g\left(x^{i}\right)}{d x^{i}}=L\left(x^{i}-z^{i}\right)+\lambda s g n\left(x^{i}\right) d x i d g ( x i ) = L ( x i − z i ) + λ s g n ( x i )
其中
sign ( x i ) = { 1 , x i > 0 − 1 , x i < 0 \operatorname{sign}\left(x^{i}\right)=\left\{\begin{array}{ll}
{1,} & {x^{i}>0} \\
{-1,} & {x^{i}<0}
\end{array}\right. sign ( x i ) = { 1 , − 1 , x i > 0 x i < 0
称为符号函数[1]，对于x i = 0 x^i=0 x i = 0 ∣ x i ∣ \vert x^i \vert ∣ x i ∣ x i = 0 x^i=0 x i = 0 d g ( x i ) d x i = 0 \frac{d g\left(x^{i}\right)}{d x^{i}}=0 d x i d g ( x i ) = 0
x i = z i − λ L sign ( x i ) x^{i}=z^{i}-\frac{\lambda}{L} \operatorname{sign}\left(x^{i}\right) x i = z i − L λ sign ( x i )
此式的解即为优化目标g ( x i ) g(x^i) g ( x i ) x i x^i x i
（1）当z i > λ L z^i>\frac{\lambda}{L} z i > L λ x i < 0 x^i<0 x i < 0 sign ( x i ) = − 1 \operatorname{sign}(x^i)=-1 sign ( x i ) = − 1 x i = z i + λ L > 0 x^i=z^i+\frac{\lambda}{L}>0 x i = z i + L λ > 0 x i > 0 x^i>0 x i > 0 sign ( x i ) = 1 \operatorname{sign}(x^i)=1 sign ( x i ) = 1 x i = z i − λ L > 0 x^i=z^i-\frac{\lambda}{L}>0 x i = z i − L λ > 0 x i = z i − λ L x^i=z^i-\frac{\lambda}{L} x i = z i − L λ g ( x i ) g(x^i) g ( x i ) x i > 0 x^i>0 x i > 0
d g ( x i ) d x i = L ( x i − z i ) + λ \frac{d g\left(x^{i}\right)}{d x^{i}}=L\left(x^{i}-z^{i}\right)+\lambda d x i d g ( x i ) = L ( x i − z i ) + λ g ( x i ) g(x^i) g ( x i )
d 2 g ( x i ) d x i 2 = L \frac{d^2 g\left(x^{i}\right)}{{d x^{i}}^2}=L d x i 2 d 2 g ( x i ) = L
由于L L L x i = z i − λ L x^i=z^i-\frac{\lambda}{L} x i = z i − L λ g ( x i ) g(x^i) g ( x i )
（2）当z i < − λ L z^i<-\frac{\lambda}{L} z i < − L λ x i > 0 x^i>0 x i > 0 sign ( x i ) = 1 \operatorname{sign}(x^i)=1 sign ( x i ) = 1 x i = z i − λ L < 0 x^i=z^i-\frac{\lambda}{L}<0 x i = z i − L λ < 0 x i < 0 x^i<0 x i < 0 sign ( x i ) = − 1 \operatorname{sign}(x^i)=-1 sign ( x i ) = − 1 x i = z i + λ L < 0 x^i=z^i+\frac{\lambda}{L}<0 x i = z i + L λ < 0 x i = z i + λ L x^i=z^i+\frac{\lambda}{L} x i = z i + L λ g ( x i ) g(x^i) g ( x i )
（3）当− λ L ⩽ z i ⩽ λ L -\frac{\lambda}{L} \leqslant z^i \leqslant \frac{\lambda}{L} − L λ ⩽ z i ⩽ L λ x i > 0 x^i>0 x i > 0 sign ( x i ) = 1 \operatorname{sign}(x^i)=1 sign ( x i ) = 1 x i = z i − λ L ⩽ 0 x^i=z^i-\frac{\lambda}{L}\leqslant 0 x i = z i − L λ ⩽ 0 x i < 0 x^i<0 x i < 0 sign ( x i ) = − 1 \operatorname{sign}(x^i)=-1 sign ( x i ) = − 1 x i = z i + λ L ⩾ 0 x^i=z^i+\frac{\lambda}{L}\geqslant 0 x i = z i + L λ ⩾ 0
（4）最后讨论x i = 0 x^i=0 x i = 0 g ( x i ) = L 2 ( z i ) 2 g(x^i)=\frac{L}{2}\left({z^i}\right)^2 g ( x i ) = 2 L ( z i ) 2 ∣ z i ∣ > λ L \vert z^i\vert>\frac{\lambda}{L} ∣ z i ∣ > L λ g ( x i ) g(x^i) g ( x i ) x i = z i − λ L x^i=z^i-\frac{\lambda}{L} x i = z i − L λ
g ( x i ) ∣ x i = 0 − g ( x i ) ∣ x i = z i − λ L = L 2 ( z i ) 2 − ( λ z i − λ 2 2 L ) = L 2 ( z i − λ L ) 2 > 0 \begin{aligned}
g(x^i)\vert_{x^i=0}-g(x^i)\vert_{x^i=z^i-\frac{\lambda}{L}}
&=\frac{L}{2}\left({z^i}\right)^2 - \left(\lambda z^i-\frac{\lambda^2}{2L}\right)\\
&=\frac{L}{2}\left(z^i-\frac{\lambda}{L}\right)^2\\
&>0
\end{aligned} g ( x i ) ∣ x i = 0 − g ( x i ) ∣ x i = z i − L λ = 2 L ( z i ) 2 − ( λ z i − 2 L λ 2 ) = 2 L ( z i − L λ ) 2 > 0
因此当∣ z i ∣ > λ L \vert z^i\vert>\frac{\lambda}{L} ∣ z i ∣ > L λ x i = 0 x^i=0 x i = 0 g ( x i ) g(x^i) g ( x i ) − λ L ⩽ z i ⩽ λ L -\frac{\lambda}{L} \leqslant z^i \leqslant \frac{\lambda}{L} − L λ ⩽ z i ⩽ L λ Δ x ≠ 0 \Delta x\neq 0 Δ x = 0
g ( Δ x ) = L 2 ( Δ x − z i ) 2 + λ ∣ Δ x ∣ = L 2 ( ( Δ x ) 2 − 2 Δ x ⋅ z i + 2 λ L ∣ Δ x ∣ ) + L 2 ( z i ) 2 ≥ L 2 ( ( Δ x ) 2 − 2 Δ x ⋅ z i + 2 λ L Δ x ) + L 2 ( z i ) 2 ≥ L 2 ( Δ x ) 2 + L 2 ( z i ) 2 > g ( x i ) ∣ x i = 0 \begin{aligned}
g(\Delta x) &=\frac{L}{2}\left(\Delta x-z^{i}\right)^{2}+\lambda|\Delta x| \\
&=\frac{L}{2}\left((\Delta x)^{2}-2 \Delta x \cdot z^{i}+\frac{2 \lambda}{L}|\Delta x|\right)+\frac{L}{2}\left(z^{i}\right)^{2} \\
&\ge\frac{L}{2}\left((\Delta x)^{2}-2 \Delta x \cdot z^{i}+\frac{2 \lambda}{L}\Delta x\right)+\frac{L}{2}\left(z^{i}\right)^{2}\\
&\ge\frac{L}{2}\left(\Delta x\right)^2+\frac{L}{2}\left(z^{i}\right)^{2}\\
&>g(x^i)\vert_{x^i=0}
\end{aligned} g ( Δ x ) = 2 L ( Δ x − z i ) 2 + λ ∣Δ x ∣ = 2 L ( ( Δ x ) 2 − 2Δ x ⋅ z i + L 2 λ ∣Δ x ∣ ) + 2 L ( z i ) 2 ≥ 2 L ( ( Δ x ) 2 − 2Δ x ⋅ z i + L 2 λ Δ x ) + 2 L ( z i ) 2 ≥ 2 L ( Δ x ) 2 + 2 L ( z i ) 2 > g ( x i ) ∣ x i = 0
因此x i = 0 x^i=0 x i = 0 g ( x i ) g(x^i) g ( x i )
综上所述，11.14成立。
该式称为软阈值(Soft Thresholding)函数，很常见，建议掌握。另外，常见的变形是式(11.13)中的L = 1 L=1 L = 1 L = 2 L=2 L = 2
11.4 稀疏表示与字典学习
稀疏表示与字典学习实际上是信号处理领域的概念。本节内容核心就是K-SVD算法。
11.4.1 式(11.15)的解释
这个式子表达的意思很容易理解，即希望样本x i x_i x i α i \boldsymbol{\alpha}_i α i B \mathbf{B} B x i x_i x i α i \boldsymbol{\alpha}_i α i
11.4.2 式(11.16)的解释
为了优化11.15，我们采用变量交替优化的方式(有点类似EM算法)，首先固定变量B \mathbf{B} B m m m α i u α i v ( u ≠ v ) \alpha_{i}^{u} \alpha_{i}^{v}(u \neq v) α i u α i v ( u = v ) α i \boldsymbol{\alpha}_i α i
11.4.3 式(11.17)的推导
这是优化11.15的第二步，固定住α i , i = 1 , 2 , … , m \boldsymbol{\alpha}_i, i=1, 2,\dots,m α i , i = 1 , 2 , … , m min B ∑ i = 1 m ∥ x i − B α i ∥ 2 2 \min _{\mathbf{B}} \sum_{i=1}^{m}\left\|\boldsymbol{x}_{i}-\mathbf{B} \boldsymbol{\alpha}_{i}\right\|_{2}^{2} min B ∑ i = 1 m ∥ x i − B α i ∥ 2 2 min B ∥ X − B A ∥ 2 2 \min _{\mathbf{B}}\|\mathbf{X}-\mathbf{B} \mathbf{A}\|_{2}^{2} min B ∥ X − BA ∥ 2 2 F F F min B ∥ X − B A ∥ F 2 \min _{\mathbf{B}}\|\mathbf{X}-\mathbf{B} \mathbf{A}\|_{F}^{2} min B ∥ X − BA ∥ F 2
11.4.4 式(11.18)的推导
这个公式难点在于推导B A = ∑ j = 1 k b j α j \mathbf{B}\mathbf{A}=\sum_{j=1}^k\boldsymbol{b}_j\boldsymbol{\alpha}^j BA = ∑ j = 1 k b j α j b j α j \boldsymbol{b}_{j} \boldsymbol{\alpha}^{j} b j α j B A \mathbf{B}\mathbf{A} BA B A \mathbf{B}\mathbf{A} BA k k k
B A = [ b 1 1 b 2 1 ⋅ ⋅ ⋅ b k 1 b 1 2 b 2 2 ⋅ ⋅ ⋅ b k 2 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ b 1 d b 2 d ⋅ ⋅ ⋅ b k d ] d × k ⋅ [ α 1 1 α 2 1 ⋅ ⋅ ⋅ α m 1 α 1 2 α 2 2 ⋅ ⋅ ⋅ α m 2 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ α 1 k α 2 k ⋅ ⋅ ⋅ α m k ] k × m = [ ∑ j = 1 k b j 1 α 1 j ∑ j = 1 k b j 1 α 2 j ⋅ ⋅ ⋅ ∑ j = 1 k b j 1 α m j ∑ j = 1 k b j 2 α 1 j ∑ j = 1 k b j 2 α 2 j ⋅ ⋅ ⋅ ∑ j = 1 k b j 2 α m j ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ∑ j = 1 k b j d α 1 j ∑ j = 1 k b j d α 2 j ⋅ ⋅ ⋅ ∑ j = 1 k b j d α m j ] d × m \begin{aligned}
\boldsymbol B\boldsymbol A
& =\begin{bmatrix}
b_{1}^{1} &b_{2}^{1} & \cdot & \cdot & \cdot & b_{k}^{1}\\
b_{1}^{2} &b_{2}^{2} & \cdot & \cdot & \cdot & b_{k}^{2}\\
\cdot & \cdot & \cdot & & & \cdot \\
\cdot & \cdot & & \cdot & &\cdot \\
\cdot & \cdot & & & \cdot & \cdot \\
b_{1}^{d}& b_{2}^{d} & \cdot & \cdot &\cdot & b_{k}^{d}
\end{bmatrix}_{d\times k}\cdot
\begin{bmatrix}
\alpha_{1}^{1} &\alpha_{2}^{1} & \cdot & \cdot & \cdot & \alpha_{m}^{1}\\
\alpha_{1}^{2} &\alpha_{2}^{2} & \cdot & \cdot & \cdot & \alpha_{m}^{2}\\
\cdot & \cdot & \cdot & & & \cdot \\
\cdot & \cdot & & \cdot & &\cdot \\
\cdot & \cdot & & & \cdot & \cdot \\
\alpha_{1}^{k}& \alpha_{2}^{k} & \cdot & \cdot &\cdot & \alpha_{m}^{k}
\end{bmatrix}_{k\times m} \\
& =\begin{bmatrix}
\sum_{j=1}^{k}b_{j}^{1}\alpha _{1}^{j} &\sum_{j=1}^{k}b_{j}^{1}\alpha _{2}^{j} & \cdot & \cdot & \cdot & \sum_{j=1}^{k}b_{j}^{1}\alpha _{m}^{j}\\
\sum_{j=1}^{k}b_{j}^{2}\alpha _{1}^{j} &\sum_{j=1}^{k}b_{j}^{2}\alpha _{2}^{j} & \cdot & \cdot & \cdot & \sum_{j=1}^{k}b_{j}^{2}\alpha _{m}^{j}\\
\cdot & \cdot & \cdot & & & \cdot \\
\cdot & \cdot & & \cdot & &\cdot \\
\cdot & \cdot & & & \cdot & \cdot \\
\sum_{j=1}^{k}b_{j}^{d}\alpha _{1}^{j}& \sum_{j=1}^{k}b_{j}^{d}\alpha _{2}^{j} & \cdot & \cdot &\cdot & \sum_{j=1}^{k}b_{j}^{d}\alpha _{m}^{j}
\end{bmatrix}_{d\times m} &
\end{aligned} B A = b 1 1 b 1 2 ⋅ ⋅ ⋅ b 1 d b 2 1 b 2 2 ⋅ ⋅ ⋅ b 2 d ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ b k 1 b k 2 ⋅ ⋅ ⋅ b k d d × k ⋅ α 1 1 α 1 2 ⋅ ⋅ ⋅ α 1 k α 2 1 α 2 2 ⋅ ⋅ ⋅ α 2 k ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ α m 1 α m 2 ⋅ ⋅ ⋅ α m k k × m = ∑ j = 1 k b j 1 α 1 j ∑ j = 1 k b j 2 α 1 j ⋅ ⋅ ⋅ ∑ j = 1 k b j d α 1 j ∑ j = 1 k b j 1 α 2 j ∑ j = 1 k b j 2 α 2 j ⋅ ⋅ ⋅ ∑ j = 1 k b j d α 2 j ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ∑ j = 1 k b j 1 α m j ∑ j = 1 k b j 2 α m j ⋅ ⋅ ⋅ ∑ j = 1 k b j d α m j d × m
b j α j = [ b j 1 b j 2 ⋅ ⋅ ⋅ b j d ] ⋅ [ α 1 j α 2 j ⋅ ⋅ ⋅ α m j ] = [ b j 1 α 1 j b j 1 α 2 j ⋅ ⋅ ⋅ b j 1 α m j b j 2 α 1 j b j 2 α 2 j ⋅ ⋅ ⋅ b j 2 α m j ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ b j d α 1 j b j d α 2 j ⋅ ⋅ ⋅ b j d α m j ] d × m \begin{aligned}
\boldsymbol b_{\boldsymbol j}\boldsymbol \alpha ^{\boldsymbol j}
& =\begin{bmatrix}
b_{j}^{1}\\ b_{j}^{2}
\\ \cdot
\\ \cdot
\\ \cdot
\\ b_{j}^{d}
\end{bmatrix}\cdot
\begin{bmatrix}
\alpha _{1}^{j}& \alpha _{2}^{j} & \cdot & \cdot & \cdot & \alpha _{m}^{j}
\end{bmatrix}\\
& =\begin{bmatrix}
b_{j}^{1}\alpha _{1}^{j} &b_{j}^{1}\alpha _{2}^{j} & \cdot & \cdot & \cdot & b_{j}^{1}\alpha _{m}^{j}\\
b_{j}^{2}\alpha _{1}^{j} &b_{j}^{2}\alpha _{2}^{j} & \cdot & \cdot & \cdot & b_{j}^{2}\alpha _{m}^{j}\\
\cdot & \cdot & \cdot & & & \cdot \\
\cdot & \cdot & & \cdot & &\cdot \\
\cdot & \cdot & & & \cdot & \cdot \\
b_{j}^{d}\alpha _{1}^{j}& b_{j}^{d}\alpha _{2}^{j} & \cdot & \cdot &\cdot & b_{j}^{d}\alpha _{m}^{j}
\end{bmatrix}_{d\times m} &
\end{aligned} b j α j = b j 1 b j 2 ⋅ ⋅ ⋅ b j d ⋅ [ α 1 j α 2 j ⋅ ⋅ ⋅ α m j ] = b j 1 α 1 j b j 2 α 1 j ⋅ ⋅ ⋅ b j d α 1 j b j 1 α 2 j b j 2 α 2 j ⋅ ⋅ ⋅ b j d α 2 j ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ b j 1 α m j b j 2 α m j ⋅ ⋅ ⋅ b j d α m j d × m
求和可得：
∑ j = 1 k b j α j = ∑ j = 1 k ( [ b j 1 b j 2 ⋅ ⋅ ⋅ b j d ] ⋅ [ α 1 j α 2 j ⋅ ⋅ ⋅ α m j ] ) = [ ∑ j = 1 k b j 1 α 1 j ∑ j = 1 k b j 1 α 2 j ⋅ ⋅ ⋅ ∑ j = 1 k b j 1 α m j ∑ j = 1 k b j 2 α 1 j ∑ j = 1 k b j 2 α 2 j ⋅ ⋅ ⋅ ∑ j = 1 k b j 2 α m j ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ∑ j = 1 k b j d α 1 j ∑ j = 1 k b j d α 2 j ⋅ ⋅ ⋅ ∑ j = 1 k b j d α m j ] d × m \begin{aligned}
\sum_{j=1}^{k}\boldsymbol b_{\boldsymbol j}\boldsymbol \alpha ^{\boldsymbol j}
& = \sum_{j=1}^{k}\left (\begin{bmatrix}
b_{j}^{1}\\ b_{j}^{2}
\\ \cdot
\\ \cdot
\\ \cdot
\\ b_{j}^{d}
\end{bmatrix}\cdot
\begin{bmatrix}
\alpha _{1}^{j}& \alpha _{2}^{j} & \cdot & \cdot & \cdot & \alpha _{m}^{j}
\end{bmatrix} \right )\\
& =\begin{bmatrix}
\sum_{j=1}^{k}b_{j}^{1}\alpha _{1}^{j} &\sum_{j=1}^{k}b_{j}^{1}\alpha _{2}^{j} & \cdot & \cdot & \cdot & \sum_{j=1}^{k}b_{j}^{1}\alpha _{m}^{j}\\
\sum_{j=1}^{k}b_{j}^{2}\alpha _{1}^{j} &\sum_{j=1}^{k}b_{j}^{2}\alpha _{2}^{j} & \cdot & \cdot & \cdot & \sum_{j=1}^{k}b_{j}^{2}\alpha _{m}^{j}\\
\cdot & \cdot & \cdot & & & \cdot \\
\cdot & \cdot & & \cdot & &\cdot \\
\cdot & \cdot & & & \cdot & \cdot \\
\sum_{j=1}^{k}b_{j}^{d}\alpha _{1}^{j}& \sum_{j=1}^{k}b_{j}^{d}\alpha _{2}^{j} & \cdot & \cdot &\cdot & \sum_{j=1}^{k}b_{j}^{d}\alpha _{m}^{j}
\end{bmatrix}_{d\times m} &
\end{aligned} j = 1 ∑ k b j α j = j = 1 ∑ k b j 1 b j 2 ⋅ ⋅ ⋅ b j d ⋅ [ α 1 j α 2 j ⋅ ⋅ ⋅ α m j ] = ∑ j = 1 k b j 1 α 1 j ∑ j = 1 k b j 2 α 1 j ⋅ ⋅ ⋅ ∑ j = 1 k b j d α 1 j ∑ j = 1 k b j 1 α 2 j ∑ j = 1 k b j 2 α 2 j ⋅ ⋅ ⋅ ∑ j = 1 k b j d α 2 j ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ∑ j = 1 k b j 1 α m j ∑ j = 1 k b j 2 α m j ⋅ ⋅ ⋅ ∑ j = 1 k b j d α m j d × m
得证。
将矩阵B \mathbf{B} B b j , j = 1 , 2 , … , k \boldsymbol{b}_j,j=1,2,\dots,k b j , j = 1 , 2 , … , k min B ∥ … B … ∥ F 2 \min\limits_\mathbf{B}\Vert\dots\mathbf{B}\dots\Vert^2_F B min ∥ … B … ∥ F 2 min b i ∥ … b i … ∥ F 2 \min\limits_{b_i}\Vert\dots\boldsymbol{b}_i\dots\Vert^2_F b i min ∥ … b i … ∥ F 2
11.5 K-SVD算法
本节前半部分铺垫概念，后半部分核心就是K-SVD。作为字典学习的最经典的算法，K-SVD[2]自2006年发表以来已逾万次引用。理解K-SVD的基础是SVD，即奇异值分解，参见"西瓜书"附录A.3。
对于任意实矩阵 A ∈ R m × n \mathbf{A} \in \mathbb{R}^{m \times n} A ∈ R m × n A = U Σ V ⊤ \mathbf{A}=\mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^{\top} A = U Σ V ⊤ U ∈ R m × m , V ∈ R n × n \mathbf{U} \in \mathbb{R}^{m \times m}, \mathbf{V} \in \mathbb{R}^{n \times n} U ∈ R m × m , V ∈ R n × n m m m n n n U ⊤ U = I , V ⊤ V = I \mathbf{U}^{\top} \mathbf{U}=\mathbf{I}, \mathbf{V}^{\top} \mathbf{V}=\mathbf{I} U ⊤ U = I , V ⊤ V = I Σ ∈ R m × n \boldsymbol{\Sigma} \in \mathbb{R}^{m \times n} Σ ∈ R m × n ( Σ ) i i = σ i (\boldsymbol{\Sigma})_{i i}=\sigma_i ( Σ ) ii = σ i σ i \sigma_i σ i A \mathrm{A} A
正如西瓜书附录 A.3 所述, K-SVD 分解中主要使用 SVD
We shall call this algorithm \"K-SVD\" to parallel the nameK \mathrm{K} K
具体来说, 就是原文献中的字典共有 K \mathrm{K} K K \mathrm{K} K K \mathrm{K} K K \mathrm{K} K K \mathrm{K} K
K-SVD算法伪代码详如图11-1所示, 其中符号与本节符号有差异。具体来说,D \mathbf{D} D B \mathrm{B} B x i \mathbf{x}_i x i α i \boldsymbol{\alpha}_i α i Y \mathbf{Y} Y X \mathrm{X} X
在初始化字典矩阵D以后, K-SVD 算法迭代过程分两步: 第 1 步 Sparse CodingD \mathbf{D} D D \mathbf{D} D k k k d k \mathbf{d}_k d k
∥ Y − D X ∥ F 2 = ∥ Y − ∑ j = 1 K d j x T j ∥ F 2 = ∥ ( Y − ∑ j ≠ k d j x T j ) − d k x T k ∥ F 2 = ∥ E k − d k x T k ∥ F 2 . \begin{aligned}
\|\mathbf{Y}-\mathbf{D X}\|_F^2 & =\left\|\mathbf{Y}-\sum_{j=1}^K \mathbf{d}_j \mathbf{x}_T^j\right\|_F^2 \\
& =\left\|\left(\mathbf{Y}-\sum_{j \neq k} \mathbf{d}_j \mathbf{x}_T^j\right)-\mathrm{d}_k \mathbf{x}_T^k\right\|_F^2 \\
& =\left\|\mathbf{E}_k-\mathbf{d}_k \mathrm{x}_T^k\right\|_F^2 .
\end{aligned} ∥ Y − DX ∥ F 2 = Y − j = 1 ∑ K d j x T j F 2 = Y − j = k ∑ d j x T j − d k x T k F 2 = E k − d k x T k F 2 .
注意, 矩阵 d k x T k \mathbf{d}_k \mathbf{x}_T^k d k x T k x T k \mathbf{x}_T^k x T k X \mathbf{X} X k k k k k k x k \mathbf{x}_k x k E k \mathbf{E}_k E k d k x T k \mathbf{d}_k \mathbf{x}_T^k d k x T k E k \mathbf{E}_k E k E k = U Δ V ⊤ \mathbf{E}_k=\mathbf{U} \Delta \mathbf{V}^{\top} E k = U Δ V ⊤ Δ \Delta Δ Δ ( 1 , 1 ) \Delta(1,1) Δ ( 1 , 1 ) d k x T k = U 1 Δ ( 1 , 1 ) V 1 ⊤ \mathbf{d}_k \mathbf{x}_T^k=\mathbf{U}_1 \boldsymbol{\Delta}(1,1) \mathbf{V}_1^{\top} d k x T k = U 1 Δ ( 1 , 1 ) V 1 ⊤ U 1 , V 1 \mathbf{U}_1, \mathbf{V}_1 U 1 , V 1 U , V \mathbf{U}, \mathbf{V} U , V d k = U 1 \mathbf{d}_k=\mathbf{U}_1 d k = U 1 x T k = Δ ( 1 , 1 ) V 1 ⊤ \mathbf{x}_T^k=\boldsymbol{\Delta}(1,1) \mathbf{V}_1^{\top} x T k = Δ ( 1 , 1 ) V 1 ⊤
为了保证第 1 步中得到的稀疏系数的稀疏性, K-SVD 并不直接对 E k \mathbf{E}_k E k x T k \mathbf{x}_T^k x T k x T k \mathrm{x}_T^k x T k x T k \mathbf{x}_T^k x T k E k \mathbf{E}_k E k SVD \operatorname{SVD} SVD E k R = U Δ V ⊤ \mathbf{E}_k^R=\mathbf{U} \Delta \mathrm{V}^{\top} E k R = U Δ V ⊤
d ~ k = U 1 , x ~ T k = Δ ( 1 , 1 ) V 1 ⊤ \tilde{\mathbf{d}}_k=\mathbf{U}_1, \quad \tilde{\mathbf{x}}_T^k=\boldsymbol{\Delta}(1,1) \mathbf{V}_1^{\top} d ~ k = U 1 , x ~ T k = Δ ( 1 , 1 ) V 1 ⊤
即得到更新后的 d ~ k \tilde{\mathbf{d}}_k d ~ k x ~ T k \tilde{\mathbf{x}}_T^k x ~ T k x ~ T k \tilde{\mathbf{x}}_T^k x ~ T k x T k \mathbf{x}_T^k x T k x T k \mathbf{x}_T^k x T k D ~ \tilde{\mathbf{D}} D ~ K − S V D \mathrm{K}-\mathrm{SVD} K − SVD x ~ T k \tilde{\mathbf{x}}_T^k x ~ T k d ~ k \tilde{\mathbf{d}}_k d ~ k d ~ k \tilde{\mathbf{d}}_k d ~ k
11.6 压缩感知
虽然压缩感知与稀疏表示关系密切, 但它是彻彻底底的信号处理领域的概念。
11.6.1 式(11.21)的解释
将式(11.21)进行变形
( 1 − δ k ) ⩽ ∥ A k s ∥ 2 2 ∥ s ∥ 2 2 ⩽ ( 1 + δ k ) \left(1-\delta_k\right) \leqslant \frac{\left\|\mathbf{A}_k \boldsymbol{s}\right\|_2^2}{\|\boldsymbol{s}\|_2^2} \leqslant\left(1+\delta_k\right) ( 1 − δ k ) ⩽ ∥ s ∥ 2 2 ∥ A k s ∥ 2 2 ⩽ ( 1 + δ k )
注意不等式中间, 若 s s s ∥ s ∥ 2 2 \|\boldsymbol{s}\|_2^2 ∥ s ∥ 2 2 ∥ A k s ∥ 2 2 \left\|\mathrm{A}_k \boldsymbol{s}\right\|_2^2 ∥ A k s ∥ 2 2 δ k \delta_k δ k A \mathrm{A} A
11.6.2 式(11.25)的解释
该式即为核范数定义: 矩阵的核范数（迹范数）为矩阵的奇异值之和。
有关 "凸包" 的概念, 引用百度百科里的两句原话: 在二维欧几里得空间中,
个人理解, 将 rank ( X ) \operatorname{rank}(\mathbf{X}) rank ( X ) X \mathbf{X} X ∥ X ∥ ∗ \|\mathbf{X}\|_* ∥ X ∥ ∗ ∥ X ∥ ∗ \|\mathbf{X}\|_* ∥ X ∥ ∗ rank ( X ) \operatorname{rank}(\mathbf{X}) rank ( X ) ∥ X ∥ ∗ \|\mathbf{X}\|_* ∥ X ∥ ∗ rank ( X ) \operatorname{rank}(\mathbf{X}) rank ( X ) f ( x ) f(\boldsymbol{x}) f ( x )
参考文献
[1] Wikipedia contributors. Sign function, 2020.
[2] Michal Aharon, Michael Elad, and Alfred Bruckstein. K-svd: An algorithm for designing overcomplete
[3] 杨孝春. 欧氏空间中的等距变换与等距映射. 四川工业学院学报, 1999.
