压缩感知
理解传统"先采样再压缩"的范式为什么在某些场景下本末倒置，以及稀疏性如何重写采样与重建的数学条件。掌握 RIP、$\ell_1$ 优化和字典学习的核心逻辑。
从课程脉络看：L04 的集成学习用"多样性"对抗高维复杂性，L05 则用"稀疏性"作为另一种结构先验。两者在高维数据处理中互为补充。同时，稀疏先验在 L07/L08 的神经网络剪枝和注意力稀疏化中会以新形式再次出现。
前置知识回顾
- 线性代数：矩阵运算、奇异值分解、欠定方程组。作用：测量模型 $y = \Phi x$ 本质上是一个欠定线性系统。去哪里补：L02 线性模型。
- 凸优化：$\ell_1$ 范数是凸函数，$\ell_0$ 范数不是。作用：理解为什么 $\ell_1$ 可以替代 $\ell_0$。去哪里补：Boyd & Vandenberghe《Convex Optimization》。
- 信号处理直觉：Nyquist 采样定理、频域表示。作用：理解压缩感知对传统采样率的突破。去哪里补：DSP 课程笔记。
传统数字信号采集遵循 Nyquist-Shannon 采样定理：采样频率必须达到信号最高频率的 2 倍以上才能无失真重建。按这个准则采集到的数据量往往极大。但随后，大多数信号又会被压缩编码——N 个采样值最终只保留 K 个主要系数。
这就引出了一个尖锐的问题：既然最终只保留 K 个系数，为什么一开始要采 N 个？
压缩感知的回答是：如果信号在某组基下是稀疏的（只有少数系数显著非零），那么可以在远低于 Nyquist 率的采样次数下直接获取压缩后的测量值，再通过优化算法从少量测量中精确重建原信号。
测量模型
设原始信号 $\mathbf{x} \in \mathbb{R}^N$ 在某组基 $\Psi$ 下可表示为 $\mathbf{x} = \Psi \mathbf{s}$，其中 $\mathbf{s}$ 是$k$-稀疏向量（至多 $k$ 个非零分量）。测量过程只保留 $M \ll N$ 个线性投影：
其中 $\Phi \in \mathbb{R}^{M \times N}$ 是测量矩阵，$A = \Phi \Psi \in \mathbb{R}^{M \times N}$。
这是一个典型的欠定线性系统（方程数 $M$ 少于未知数 $N$）。如果没有额外假设，解不唯一。但稀疏性恰好提供了所需的额外约束。
受限等距性质 (RIP)
测量矩阵 $A$ 满足 $k$-RIP，若存在常数 $\delta_k \in (0,1)$ 使得对任意 $k$-稀疏向量 $\mathbf{s}$：
RIP 要求测量矩阵在子空间上近似保持向量长度——即测量过程不会扭曲稀疏信号之间的距离关系。
最直接的想法是找最稀疏的解——用 $\ell_0$ "范数"（非零元素个数）做目标：
但 $\ell_0$ 优化是组合搜索问题，NP 难。$\ell_1$ 范数是 $\ell_0$ 最自然的凸松弛：
ℓ0-ℓ1 等价性定理（Candès-Tao, 2005）
若测量矩阵 $A$ 满足 $2k$-RIP 且 $\delta_{2k} < \sqrt{2} - 1$，则 $\ell_1$ 最小化的解精确等于 $\ell_0$ 最小化的解（即原始 $k$-稀疏信号 $\mathbf{s}$）。
直觉上可以这样理解：$\ell_1$ 范数在几何上对应菱形等高线，$\ell_0$ 对应坐标轴上的点。当解足够稀疏时，菱形的最顶端恰好会落在坐标轴上——凸松弛没有丢失最优解。
真实信号未必在固定的傅里叶基或小波基下稀疏。字典学习让稀疏表示从"选一个预设基"进化到"为数据量身学习表示"：
字典学习目标函数
给定 $N$ 个样本 $\{\mathbf{x}^{(i)}\}$，联合优化字典 $B$ 和稀疏系数 $\{\alpha^{(i)}\}$：
第一项保证重建精度，第二项（$\ell_1$ 正则）强制系数稀疏。优化策略为交替迭代：固定 $B$ 解 $\alpha$（LASSO 问题），固定 $\alpha$ 更新 $B$（最小二乘）。
稀疏性不只是采样理论，它还能直接驱动分类器。SRC 的核心想法非常优雅：将测试样本表示为全体训练样本的稀疏线性组合，非零系数自然指向正确的类别。
SRC 分类流程
- 将所有类的训练样本按列拼成矩阵 $A = [A_1, A_2, \ldots, A_C] \in \mathbb{R}^{d \times n}$。
- 求解 $\ell_1$ 最小化：$\hat{\mathbf{x}} = \arg\min \|\mathbf{x}\|_1$ s.t. $\|A\mathbf{x} - \mathbf{y}\|_2 \leq \varepsilon$（允许噪声容忍）。
- 对每个类别 $i$，计算残差 $r_i(\mathbf{y}) = \|\mathbf{y} - A \delta_i(\hat{\mathbf{x}})\|_2$，其中 $\delta_i$ 只保留第 $i$ 类对应的系数。
- 分类结果：$\hat{c} = \arg\min_i \, r_i(\mathbf{y})$。
| 方法 | 需要显式特征工程 | 对遮挡的鲁棒性 | 理论保证 |
|---|---|---|---|
| 最近邻分类器 | 是（距离度量选择） | 差 | 无 |
| SVM | 是（核选择） | 一般 | 间隔理论 |
| SRC | 否（稀疏系数自动选类） | 强（扩展矩阵 $[A, I]$ 吸收遮挡） | RIP + $\ell_1$ 等价性 |
例题：在二维空间中看 ℓ0 / ℓ1 / ℓ2 的等高线差异
题目：在 $\mathbb{R}^2$ 中，$\|\mathbf{s}\|_0 \leq 1$ 对应坐标轴上的点，$\|\mathbf{s}\|_1 \leq 1$ 对应菱形，$\|\mathbf{s}\|_2 \leq 1$ 对应圆形。为什么稀疏问题中 $\ell_1$ 菱形比 $\ell_2$ 圆更容易碰到坐标轴？
- 第一步：$\ell_2$ 约束的等高线是圆，与欠定系统的解空间（一条直线）相切时，切点几乎不会在坐标轴上。
- 第二步：$\ell_1$ 约束的等高线是菱形，菱形的顶点就在坐标轴上。当解空间直线与菱形相切时，切点很自然地落在顶点——即某个分量为零。
- 第三步：这正是 $\ell_1$ 产生稀疏解的几何原因。
答案： $\ell_1$ 的菱形形状使得优化解天然偏向坐标轴（稀疏解），而 $\ell_2$ 的圆形没有这种偏好。
例题：3 类人脸、稀疏系数如何自动指向正确类别
题目：假设有 3 类人脸，每类 2 张训练图片（每张压缩到 5 维向量）。训练矩阵 $A = [A_1 \,|\, A_2 \,|\, A_3] \in \mathbb{R}^{5 \times 6}$。测试样本 $\mathbf{y}$ 来自第 1 类。写出 SRC 的判断过程。
- 求解：$\hat{\mathbf{x}} = \arg\min \|\mathbf{x}\|_1$ s.t. $A\mathbf{x} = \mathbf{y}$。
- 理想情况：$\hat{\mathbf{x}}$ 只有对应 $A_1$ 的两个位置非零（如 $\hat{x}_1 = 0.6, \hat{x}_2 = 0.4$，其余为 0）。
- 计算残差：$r_1 = \|\mathbf{y} - A_1 \cdot [0.6, 0.4]^T\|_2 \approx 0$，$r_2, r_3$ 较大。
- 分类：$\hat{c} = \arg\min \{r_1, r_2, r_3\} = 1$。
答案：稀疏系数自然集中在第 1 类对应的列上，最小残差判对类别。整个过程无需手动设计特征或训练分类器。
后续用途 / 连接
- L06 采样方法：贝叶斯后验 $p(\mathbf{z}|\mathbf{x})$ 通常不可解析；稀疏先验（Laplace 分布）正是压缩感知中 $\ell_1$ 正则的概率解释。
- L07 神经网络：网络剪枝、稀疏激活（ReLU 只保留正半轴）都是稀疏性在深度学习中的体现。
- L08 Transformer：稀疏注意力（Sparse Attention）、混合专家（MoE）直接继承了"只激活少量关键组件"的思想。
复习速查
- 核心问题：传统"先采后压"范式浪费了采样资源。
- 稀疏性：信号在某组基下只有少数非零系数——这是压缩感知的理论基石。
- RIP：测量矩阵近似保持稀疏向量的长度，是 $\ell_1$ 重建有效的前提。
- ℓ1 替代 ℓ0：凸松弛 + RIP 保证 = 可高效计算的精确重建。
- 字典学习：从固定基到数据驱动的自适应表示。
- SRC：稀疏系数自动指向正确类别，无需显式分类器。
参考来源
- 课程课件：25C05 第 3–5 页（传统采样与压缩感知动机）
- 课程课件：25C05 第 9–11 页（RIP、稀疏性、$\ell_0/\ell_1$ 优化）
- 课程课件：25C05 第 12–14 页（字典学习）
- 课程课件：25C05 第 15–24 页（SRC 人脸识别完整流程）
- 公开参考：Princeton COS 521 Lecture 21（https://www.cs.princeton.edu/courses/archive/fall18/cos521/Lectures/lec21.pdf）
- 公开参考：IISc E9 203 课程讲义（https://ece.iisc.ac.in/~cmurthy/e9-203-compressed-sensing-and-sparse-signal-processing-video-lectures-and-notes-2/）