稀疏-AI总结

可以把这一节看成一条非常清晰的主线：

很多看起来很复杂的信号，其实只由少数几个“基本成分”组成。既然真正有用的信息很少，我们就没必要把所有数据都完整采下来；只采少量“混合测量”，再利用稀疏性把原信号恢复出来。

整节内容其实就是围绕这句话逐步展开的。文中先从”稀疏表示”讲起，再讲”稀疏编码”，最后把它应用到”压缩感知”和”人脸识别”。

---

1. 先理解最核心的东西：什么叫”稀疏”

稀疏向量就是：

$$\mathbf{x}=\left[\begin{array}{c}0\\ 0\\ 3\\ 0\\ 0\\ -2\\ 0\\ 0\end{array}\right]$$

8 个元素里面只有 2 个非零。

所以我们说它是”稀疏的”。

文中定义得很直接：

• 稀疏向量：大多数元素为 0；
• 稀疏表示：使用少量基本信号的线性组合表示目标信号。

关键不是”原始信号里面有很多 0”。

真正重要的是：

能不能找到一种表示方法，使得表示它的系数里面有很多 0。

---

2. 什么是”稀疏表示”？

先举一个最简单的例子。

假设有三个基本向量：

$${\mathbf{a}}_1=\left[\begin{array}{c}1\\ 0\end{array}\right],{\mathbf{a}}_2=\left[\begin{array}{c}0\\ 1\end{array}\right],{\mathbf{a}}_3=\left[\begin{array}{c}1\\ 1\end{array}\right]$$

现在有一个信号：

$$\mathbf{y}=\left[\begin{array}{c}3\\ 3\end{array}\right]$$

一种表示方法是：

$$\mathbf{y}=3{\mathbf{a}}_1+3{\mathbf{a}}_2$$

也就是系数：

$$\mathbf{x}=\left[\begin{array}{c}3\\ 3\\ 0\end{array}\right]$$

用了两个原子。

但还有一种：

$$\mathbf{y}=3{\mathbf{a}}_3$$

对应：

$$\mathbf{x}=\left[\begin{array}{c}0\\ 0\\ 3\end{array}\right]$$

只用了一个原子。

显然后一种更”稀疏”。

所以稀疏表示解决的问题就是：

$$\boxed{\text{用尽可能少的基本向量表示 }\mathbf{y}}$$

一般写成：

$$\mathbf{y}=\mathbf{A}\mathbf{x}$$

其中：

$$\mathbf{A}=[{\mathbf{a}}_1,{\mathbf{a}}_2,\cdots ,{\mathbf{a}}_n]$$

叫做字典，每一列叫一个原子。

$$\mathbf{x}$$

就是对应的系数。

文中接下来专门讨论了 $n>m$ 的情况，此时字典中的原子数量比信号维数还多，这叫”过完备字典”。

---

3. 为什么要故意弄一个”过完备字典”？

这一点第一次看特别容易疑惑。

例如二维空间只需要：

$$\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\end{array}\right]$$

两个基向量就够了。

为什么还要搞 100 个方向？

原因是：

可选择的基本模式越多，就越有可能只用极少几个模式描述当前信号。

可以想象你在拼乐高。

如果你只有：

• 方块；
• 长条。

想拼一辆车，就需要很多块。

但如果你的零件库还有：

• 轮子；
• 车窗；
• 车门；
• 车头；
• 底盘……

那么只需要少量零件就可以拼出来。

所以：

$$\mathbf{A}=[{\mathbf{a}}_1,\cdots ,{\mathbf{a}}_n],n>m$$

就相当于一个非常丰富的”零件库”。

这就是过完备字典。

文中指出，这种情况下

$$\mathbf{y}=\mathbf{A}\mathbf{x}$$

是欠定方程，因此通常存在无穷多组 $\mathbf{x}$。

---

4. 有无穷多个解，那到底选哪个？

这正是这一节第一次真正进入核心问题。

例如：

$$\mathbf{y}=\mathbf{A}\mathbf{x}$$

因为

$$n>m$$

未知数比方程多。

于是：

$$\mathbf{x}$$

可能有无穷多个。

那么我们就要加一个条件：

我不仅要求能解释 $\mathbf{y}$，还希望这个解释尽量简单。

这里出现两种方法。

---

方法一：最小 $L_2$ 范数

求：

$$\min \Vert \mathbf{x}{\Vert }_2$$

满足：

$$\mathbf{A}\mathbf{x}=\mathbf{y}$$

这个方法的思想是：

从所有解里找”整体能量最小”的那个。

例如：

$${\mathbf{x}}_1=\left[\begin{array}{c}0.5\\ 0.5\\ 0.5\\ 0.5\end{array}\right]$$

可能比：

$${\mathbf{x}}_2=\left[\begin{array}{c}2\\ 0\\ 0\\ 0\end{array}\right]$$

的平方和更小。

所以 $L_2$ 最小化经常倾向于：

把贡献分散到很多元素上。

这恰恰与稀疏相反。

所以文中说它虽然解唯一、可以理解成最小能量解，但系数通常不是稀疏的。

---

5. 真正想要的是 $L_0$ 最小化

定义：

$$\Vert \mathbf{x}{\Vert }_0$$

表示：

$$\boxed{\mathbf{x}\text{ 中非零元素的数量}}$$

例如：

$$\left[\begin{array}{c}1\\ 0\\ 0\\ 4\end{array}\right]$$

有两个非零元素，所以：

$$\Vert \mathbf{x}{\Vert }_0=2$$

因此我们希望：

$$\boxed{\min \Vert \mathbf{x}{\Vert }_0}$$

满足：

$$\mathbf{A}\mathbf{x}=\mathbf{y}$$

翻译成人话就是：

在所有能够还原 $y$ 的方案里，找使用原子数量最少的方案。

比如：

方案 A：

$$y=2a_1+3a_2+4a_3$$

使用三个原子。

方案 B：

$$y=5a_7$$

只用了一个原子。

我们选 B。

这就是”最稀疏表示”。

---

6. 有噪声怎么办？

现实世界一般不会严格满足：

$$\mathbf{y}=\mathbf{A}\mathbf{x}$$

例如麦克风有噪声、摄像头有噪点、传感器有误差。

所以改成：

$$\Vert \mathbf{A}\mathbf{x}-\mathbf{y}{\Vert }_2\le \epsilon$$

也就是说：

不要求完全一模一样，只要误差足够小就行。

然后仍然要求：

$$\min \Vert \mathbf{x}{\Vert }_0$$

这时候叫稀疏逼近。

例如真实声音：

$$1000\text{ Hz}+2000\text{ Hz}$$

实际录到的声音：

$$1000\text{ Hz}+2000\text{ Hz}+\text{一点噪声}$$

我们不需要连噪声也精确拟合，只要找出：

主要就是 1000 Hz 和 2000 Hz 两个频率。

这就是稀疏逼近的思想。

---

7. 那”稀疏编码”和”稀疏表示”有什么区别？

这一节这里很重要。

前面我们是假设：

$$\mathbf{A}$$

已经知道。

然后求：

$$\mathbf{x}$$

例如：

给你一本字典，问你应该选择哪几个词来描述一句话。

而稀疏编码更进一步：

$$\boxed{\text{连字典 }A\text{ 都可以从数据里面学出来}}$$

文中写成：

$$\mathbf{X}\approx \mathbf{A}\mathbf{S}$$

其中：

• $\mathbf{X}$：大量原始数据；
• $\mathbf{A}$：学出来的字典；
• $\mathbf{S}$：稀疏系数。

并且 $\mathbf{S}$ 的每一列都是稀疏的。

---

8. 一个非常具体的稀疏编码例子：人脸图片

假设你给计算机 10000 张人脸图片。

一开始你什么都没告诉它：

• 什么叫眼睛；
• 什么叫鼻子；
• 什么叫嘴；
• 什么叫轮廓。

稀疏编码试图学习出一批基本模式，比如：

$$A=[a_1,a_2,\cdots ,a_{500}]$$

可能有一些原子学成了：

• 水平边缘；
• 垂直边缘；
• 眼睛附近的纹理；
• 鼻梁；
• 嘴部轮廓；
• 阴影。

对于某一张具体图片：

$$x_i\approx A{s}_i$$

可能：

$$s_i=[0,0,0.8,0,0,1.2,0,\cdots {]}^T$$

只有几个值非零。

意思就是：

这张图只激活了少数几个特征。

这就是文中所说的：

对一个输入向量而言，基矩阵中只有少数基向量被激活。

---

9. 为什么”稀疏”这么有用？

你可以把它理解成一种：

$$\boxed{\text{抓主要矛盾}}$$

原始数据可能有：

$$10000$$

个数字。

但真正决定这个信号的可能只有：

$$20$$

个重要成分。

那么我们只需要处理这 20 个。

所以好处很多：

• 节省存储；
• 减少计算量；
• 压缩数据；
• 去除无关成分；
• 提取关键特征；
• 有利于分类和识别。

文中最后也特别强调，如果一个 $n$ 维向量只有 $K$ 个非零元素，就没必要存储和运算剩下的 $n-K$ 个零元素，因此计算复杂度更多取决于非零元素个数。

---

10. 接下来进入压缩感知

这才是这一节的第二个大核心。

传统采样理论说：

想还原一个信号，就得采足够多的点。

例如 Nyquist 定理：

如果信号最高频率是：

$$1\text{kHz}$$

那么至少：

$$2\text{kHz}$$

采样。

传统方案相当于：

$$\boxed{\text{先大量采集}\to \text{再压缩}}$$

例如一张图片原来：

$$20\text{ MB}$$

拍下来以后再 JPEG 压缩成：

$$2\text{ MB}$$

问题来了：

既然最后 18 MB 都扔掉了，我为什么一开始还非得把它们采下来？

这就是压缩感知提出的问题。

---

11. 压缩感知最核心的想法

压缩感知想做：

$$\boxed{\text{采样和压缩同时完成}}$$

传统：

$$x\to \text{完整采样}\to \text{压缩}$$

压缩感知：

$$x\to \text{少量测量 }y$$

其中：

$$\mathbf{y}=\mathbf{A}\mathbf{x}$$

假设：

$$x\in {\mathbb{R}}^{1000}$$

也就是完整信号有 1000 个数据。

压缩感知可能只采：

$$y\in {\mathbb{R}}^{100}$$

也就是说：

$$1000\to 100$$

但希望最后还能把 1000 维的 $x$ 恢复出来。

这正是文中所说的：从低维感知数据 $\mathbf{y}$ 恢复高维 Nyquist 采样数据 $\mathbf{x}$。

---

12. 等等：100 个方程怎么求 1000 个未知数？

这也是压缩感知最神奇的地方。

现在：

$$\mathbf{y}=\mathbf{A}\mathbf{x}$$

其中：

$$A\in {\mathbb{R}}^{100\times 1000}$$

只有 100 个方程，却有 1000 个未知数。

显然通常：

$$\boxed{\text{无穷多解}}$$

所以仅凭这个方程无法恢复 $x$。

文中也明确指出，因为 $m\ll n$，直接求解欠定方程不能可靠地恢复高维信号。

但如果我们知道一件额外的信息：

$$\boxed{x\text{ 是稀疏的，或者在某个变换域里是稀疏的}}$$

事情就不同了。

---

13. 很多信号本身不稀疏，但”换个角度看”就稀疏了

这是压缩感知非常重要的思想。

例如一段纯正弦信号：

$$x(t)=\sin (2\pi 1000t)$$

在时域看：

每个采样点几乎都不是 0。

所以：

$$x$$

一点也不稀疏。

但做 Fourier 变换后：

频谱中主要只有：

$$1000\text{ Hz}$$

附近有成分。

于是频域系数可能类似：

$$\alpha =[0,0,0,\cdots ,10,\cdots ,0]$$

一下变得非常稀疏。

所以写：

$$\mathbf{x}=\mathbf{\Psi }\mathbf{\alpha }$$

其中：

• $\Psi$：表示基/变换基；
• $\alpha$：稀疏系数。

文中称这种信号为可压缩信号，并列举 Fourier、小波、Gabor 等变换。

---

14. 把它代入压缩感知公式

有：

$$x=\Psi \alpha$$

而测量：

$$y=Ax$$

代进去：

$$y=A\Psi \alpha$$

令：

$$V=A\Psi$$

于是：

$$\boxed{y=V\alpha }$$

问题一下变成：

已知 $y$ 和 $V$，求一个最稀疏的 $\alpha$。

因为我们知道：

$$\alpha$$

只有少数非零。

恢复出：

$$\alpha$$

以后：

$$x=\Psi \alpha$$

就把原始信号恢复了。

这就是整个压缩感知的数学核心。文中也用 $\mathbf{V}=\mathbf{A}\mathbf{\Psi }$ 表示感知与表示组合后的字典。

你可以直接记成这一条链：

$$\boxed{x\underset{\text{压缩测量}}{\overset{A}{\to }}y}$$

而恢复时：

$$\boxed{y\to \alpha \to x}$$

其中：

$$x=\Psi \alpha$$

且：

$$\alpha \text{ 稀疏}$$

---

15. 一个超级直观的压缩感知例子

假设我告诉你：

有一个 1000 维向量：

$$x=[x_1,x_2,\dots ,x_{1000}]$$

但我同时告诉你：

里面实际上只有 3 个数不是 0。

那么你真正需要确定的其实不是 1000 个自由变量，而只是：

1. 哪三个位置非零；
2. 它们分别是多少。

所以真实信息量远远小于 1000。

这就是为什么：

有稀疏性作为额外先验后，即使测量数 $m<n$，也仍有可能恢复 $x$。

压缩感知利用的正是这一点。

---

16. 但采样矩阵 $A$ 不能乱选

接下来文中开始讲一个看起来抽象、实际上很好理解的东西：

非相干性

简单来说：

采样方式不能和信号的稀疏表示方式太像。

为什么？

假设信号在标准坐标系里稀疏：

$$x=[0,0,0,8,0,0{]}^T$$

如果你采样的时候刚好只看：

$$x_1,x_2,x_3$$

那么：

$$y=[0,0,0]$$

你根本不知道第 4 个位置有个 8。

这就是一个非常糟糕的测量。

相反，如果每次测量都把很多元素混在一起，例如：

$$y_1=x_1+2x_2-x_3+\cdots$$ $$y_2=3x_1-x_2+4x_3+\cdots$$

即使只做少量测量，每一个非零元素的信息都可能”扩散”到很多测量里面。

于是更容易恢复。

所以：

$$\boxed{\text{测量基和稀疏表示基越"不像"，越好}}$$

这就是非相干性的直觉。文中用相干度衡量列向量之间的相似程度：相干参数越小，列向量越接近正交；感知基与表示基越不相干，恢复所需的样本可以越少。

---

17. 为什么文中突然又从 $L_0$ 讲到 $L_1$？

因为：

$$\min \Vert \alpha {\Vert }_0$$

虽然最符合我们的目标：

非零元素越少越好。

但是它很难算。

因为原则上要不断尝试：

到底哪几个位置应该非零？

组合数量会爆炸。

所以压缩感知里经常转化为：

$$\boxed{\min \Vert \alpha {\Vert }_1}$$

其中：

$$\Vert \alpha {\Vert }_1=|{\alpha }_1|+\cdots +|{\alpha }_n|$$

文中给出的定理说明，在一定的稀疏性和非相干条件下，通过 $L_1$ 最小化可以以高概率精确恢复稀疏系数。

你现在先不用纠结证明。

只要记住：

$$\boxed{L_0：我真正想解决的问题}$$

但：

$$\boxed{L_1：实际中更容易解决的替代方案}$$

后面学稀疏优化时你会反复见到。

---

18. $m\ge C{\mu }^{2}K\log (n/\delta )$ 到底想表达什么？

这个公式第一次看很吓人：

$$m\ge C{\mu }^{2}K\log (n/\delta )$$

其实它只是想告诉你：

到底需要采多少个数据。

这里最值得理解的是关系。

$K$ 越大

说明信号越不稀疏。

需要：

$$m\uparrow$$

也就是采更多数据。

---

$K$ 越小

信号越稀疏。

只需要较少：

$$m$$

---

$\mu$ 越大

表示感知基和表示基越相关。

恢复越困难。

所以：

$$m\uparrow$$

---

$\mu$ 越小

越不相干。

恢复越容易：

$$m\downarrow$$

这就是文中的核心结论：

$$\boxed{\text{需要多少采样点，主要由稀疏程度和非相干性决定}}$$

而不再单纯由信号带宽决定。

---

19. 最后的人脸识别其实是整节最漂亮的应用例子

假设现在数据库有三个人：

张三：

$$D_1=[d_{11},d_{12},d_{13}]$$

李四：

$$D_2=[d_{21},d_{22},d_{23}]$$

王五：

$$D_3=[d_{31},d_{32},d_{33}]$$

每一列都是这个人的一张训练照片。

把它们全部拼起来：

$$D=[D_1,D_2,D_3]$$

现在来了一张测试图片：

$$y$$

假设它实际上是李四。

那么理论上：

$$y$$

主要应该由李四的那些训练照片组合出来：

$$y\approx 0D_1+D_2{\alpha }_2+0D_3$$

于是整体系数：

$$\alpha =\left[\begin{array}{c}0\\ 0\\ 0\\ \ast \\ \ast \\ 0\\ 0\\ 0\\ 0\end{array}\right]$$

会表现出：

只有”李四对应的那部分”明显非零。

所以只要求：

$$y=D\alpha$$

中的稀疏解，就可以看：

非零系数集中在哪个人对应的训练样本上。

从而完成识别。文中正是把所有类别的训练图像组成总字典 $\mathbf{D}$，再通过求稀疏系数 ${\mathbf{\alpha }}_0$ 将人脸识别转化成线性求逆和 $L_0$ 最小化问题。

---

20. 现在把整节压缩成一个完整故事

你可以这样理解这一节。

假设有一个复杂信号：

$$x$$

第一步，我们发现：

虽然 $x$ 看起来复杂，但它可以由很少几个基本成分组成。

即：

$$x=\Psi \alpha$$

而且：

$$\alpha$$

非常稀疏。

于是就产生稀疏表示。

↓

接着我们发现：

甚至连这些”基本成分”是什么，都可以让机器从大量数据中自己学。

于是出现：

$$X\approx AS$$

这叫稀疏编码。

↓

进一步：

既然真正的信息只有少数几个非零系数，那为什么还要完整采集所有数据？

于是只采：

$$y=Ax,m\ll n$$

这叫压缩感知。

↓

由于：

$$x=\Psi \alpha$$

因此：

$$y=A\Psi \alpha$$

↓

然后解决：

$$\min \Vert \alpha {\Vert }_0$$

或者实际中常用：

$$\min \Vert \alpha {\Vert }_1$$

恢复稀疏系数。

↓

最后：

$$x=\Psi \alpha$$

恢复原始信号。

所以整节真正应该记住的是：

$$\boxed{\text{稀疏}\to \text{少量关键成分}\to \text{少量测量}\to \text{稀疏优化}\to \text{恢复原信号}}$$

---

你现阶段最值得真正搞懂的 5 个式子

第一：

$$\boxed{y=Ax}$$

字典中的少数原子组合成信号。

第二：

$$\boxed{\min \Vert x{\Vert }_0\text{s.t. }Ax=y}$$

从无穷多个表示中找最稀疏的那个。

第三：

$$\boxed{X\approx AS}$$

稀疏编码：字典 $A$ 和稀疏系数 $S$ 都从数据中学习。

第四：

$$\boxed{x=\Psi \alpha }$$

原始信号可能不稀疏，但在某个变换域下的 $\alpha$ 很稀疏。

第五：

$$\boxed{y=A\Psi \alpha }$$

这是压缩感知最核心的公式：

用少量测量 $y$，求稀疏的 $\alpha$，再恢复原始 $x$。

如果你把这五个公式之间的关系真正想明白，这一节大概已经掌握了 70%～80%。后面的相干性、$L_1$ 优化、RIP 等，本质上都是在回答一个问题：

$$\boxed{\text{凭什么这么少的数据还能保证把原信号找回来？}}$$

另外，你这份笔记第 188 行写的是”通过 $\mathbf{x}=\mathbf{A}\mathbf{\alpha }$ 重构”，但按照前文定义 $\mathbf{x}=\mathbf{\Psi }\mathbf{\alpha }$，这里的记号与前文并不一致；学习时建议你优先沿用前文的 $\mathbf{x}=\mathbf{\Psi }\mathbf{\alpha }$ 这条关系。