[!IMPORTANT]
参与组队学习的同学须知：
本章学习时间：3天
本章配套视频教程：https://www.bilibili.com/video/BV1Mh411e7VU?p=17
第11章 特征选择与稀疏学习
11.1 子集搜索与评价
开篇给出了 "特征选择" 的概念, 并谈到特征选择与第 10
章的降维有相似的动机。特征选择与降维的区别在于特征选择是从所有特征中简单地选出相关特征,
选择出来的特征就 是原来的特征; 降维则对原来的特征进行了映射变换,
降维后的特征均不再是原来的特征。
本节涉及 "子集评价" 的式(14.1)和式(14.2)与第 4 章的式(4.2)和式(4.1)相同,
这是因为 "决策树算法在构建树的同时也可看作进行了特征选择" (参见 "11.7
阅读材料")。 接下来在 11.2节、11.3 节、11.4
节分别介绍的三类特征选择方法: 过滤式(filter)、包裹
式(wrapper)和嵌入式(embedding)。
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 过滤式选择
"过滤式方法先对数据集进行特征选择, 然后再训练学习器,
特征选择过程与后续学习 器无关。这相当于先用特征选择过程对初始特征进行
'过滤', 再用过滤后的特征来训练模 型。", 这是本节开篇第一段原话,
之所以重写于此, 是因为这段话里包含了 "过滤"的概念,
该概念并非仅针对特征选择, 那些所有先对数据集进行某些预处理,
然后基于预处理结果再 训练学习器的方法 (预处理过程独立于训练学习器过程)
均可以称之为 "过滤式算法"。特 别地, 本节介绍的 Relief
方法只是过滤式特征选择方法的其中一种而已。
从式(11.3)可以看出, Relief 方法本质上基于
"空间上相近的样本具有相近的类别标记" 假设。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 包裹式选择
"与过滤式特征选择不考虑后续学习器不同,
包裹式特征选择直接把最终将要使用的学
习器的性能作为特征子集的评价准则。换言之,
包裹式特征选择的目的就是为给定学习器选 择最有利于其性能、"量身定做'
的特征子集。", 这是本节开篇第一段原话, 之所以重写于 此,
是因为这段话里包含了 "包裹" 的概念, 该概念并非仅针对特征选择,
那些所有基于学 习器的性能作为评价准则对数据集进行预处理的方法
(预处理过程依赖训练所得学习器的 测试性能）均可以称之为
"包裹式算法"。特别地, 本节介绍的 LVW 方法只是包裹式特征
选择方法的其中一种而已。
图 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 个,
挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个......我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多,
挑出的苹果就越大, 但我除非拿 100 次, 否则无法肯定挑出
了最大的。这个挑苹果的算法, 就属于蒙特卡罗算法一一尽量找好的,
但不保证是最好的。 而拉斯维加斯算法, 则是另一种情况。假如有一把锁, 给我
100 把钥匙, 只有 1 把是对 的。于是我每次随机拿 1 把钥匙去试,
打不开就再换 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连续" 可以形象得理解为: 以陆地为例,
Lipschitz连续就是说这块地上没有特别陡的坡; 其中最陡的地方有多陡呢?
这就是所谓的Lipschitz常数。
11.3.6 式(11.10)的推导
首先注意优化目标式和11.7
LASSO回归的联系和区别，该式中的x 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
解决低秩矩阵近似问题。之所 以称为 K-SVD, 原文献中专门有说明:
We shall call this algorithm "K-SVD" to parallel the name
K \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 Coding
Stage 就是普通的已知字典矩阵 D \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 压缩感知
虽然压缩感知与稀疏表示关系密切, 但它是彻彻底底的信号处理领域的概念。
"西瓜书"在本章有几个专业术语翻译与信号处理领域人士的习惯翻译略不一样：比如第
258 页的 Restricted Isometry Property (RIP)"西瓜书"翻译为 "限定等距性",
信号处理领域一般翻译为 "有限等距性质"; 第 259 页的 Basis Pursuit
De-Noising、第 261 页 的 Basis Pursuit 和 Matching Pursuit 中的
"Pursuit" "西瓜书"翻译为 "寻踪", 信号处理领域一般 翻译为 "追踪",
即基追踪降噪、基追踪、匹配追踪。
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
dictionaries for sparse representation. IEEE Transactions on signal processing, 54(11):4311–4322, 2006.
[3] 杨孝春. 欧氏空间中的等距变换与等距映射. 四川工业学院学报, 1999.
