2、数学基础：稀疏表示、基追踪、正交匹配追踪、凸优化等核心数学工具与算法原理
压缩感知（Compressive Sensing, CS）之所以能突破奈奎斯特采样定理的限制，其数学根基在于三个关键命题：信号在某个变换域下具有稀疏性；测量矩阵与稀疏基之间满足受限等距性质（RIP）；以及通过凸优化或贪婪算法可以从远少于传统采样数的线性测量中精确重建信号。本章将围绕这四个核心工具展开，帮助你在光学成像系统的实际建模中，理解“如何表示稀疏”“如何设计测量”“如何求解逆问题”以及“如何评估重建质量”。
上图给出了压缩感知数学体系的整体框架。从信号模型出发，经过测量矩阵的线性投影，最终通过不同的重建算法恢复原始信号。下面我们逐一拆解每个模块的数学本质与工程实现要点。
2.1 稀疏表示：信号的结构化先验
核心原理：稀疏表示是压缩感知的前提。一个长度为 N 的离散信号 x，如果在某个正交基或冗余字典 Ψ 下，其系数向量 θ 中仅有 K 个非零元素（K ≪ N），则称 x 在 Ψ 域是 K-稀疏的。数学上写作 x = Ψθ，其中 Ψ 为 N×N 的基矩阵（或 N×D 的字典，D ≥ N），θ 的 ℓ₀ 范数（非零元素个数）≤ K。对于自然图像，小波基、曲波基或全变分（TV）模型都能提供良好的稀疏近似；对于光谱数据，DCT 基往往更有效；而对于视频或高光谱图像，则需要利用三维变换或张量分解来获得更好的稀疏性。
判断方法：在实际光学系统中，如何判断一个信号是否适合压缩感知？首先，计算信号在候选基下的变换系数，观察系数衰减曲线。若系数按幂律快速衰减（即大部分能量集中在少数大系数上），则说明该信号在该基下近似稀疏。其次，检查信号的“有效自由度”——例如，一个由少量点光源构成的场景，在空间域本身就是稀疏的；而一个自然场景在梯度域通常是稀疏的（因为边缘像素占少数）。
| 信号类型 | 推荐稀疏基 | 稀疏度 K/N | 典型应用 |
|---|---|---|---|
| 点光源/星场 | 空间域（单位基） | 0.1% - 1% | 天文成像、单像素相机 |
| 自然图像 | 小波基（Daubechies-8） | 5% - 15% | 可见光成像、遥感 |
| 医学影像（MRI） | 梯度域（TV） | 10% - 20% | MRI 加速采集 |
| 光谱数据 | DCT 基 | 3% - 8% | 高光谱成像 |
| 视频帧差 | 3D-DWT 或帧间差分 | 2% - 5% | 视频压缩感知 |
2.2 基追踪（Basis Pursuit）与凸优化
核心原理：基追踪是压缩感知中最经典的重建算法。其核心思想是将 ℓ₀ 范数最小化问题（NP-难）松弛为 ℓ₁ 范数最小化问题：
min ‖θ‖₁ subject to y = ΦΨθ其中 Φ 为 m×N 的测量矩阵，y 为 m 维测量向量。ℓ₁ 范数作为 ℓ₀ 的最紧凸松弛，在 RIP 条件满足时，其解与 ℓ₀ 解一致。基追踪本质上是一个线性规划问题，可以通过单纯形法或内点法求解。对于含噪情况，则使用基追踪去噪（BPDN）：
min ‖θ‖₁ subject to ‖y - ΦΨθ‖₂ ≤ ε操作流程：在实际工程中，使用基追踪求解压缩感知问题的标准流程为：① 构造测量矩阵 Φ（通常为随机高斯矩阵或随机伯努利矩阵）；② 选择稀疏基 Ψ，并计算感知矩阵 A = ΦΨ；③ 使用 CVX、SPGL1 或 YALL1 等工具包求解 ℓ₁ 最小化问题；④ 通过逆变换 x̂ = Ψθ̂ 得到重建信号。
2.3 正交匹配追踪（OMP）与贪婪算法
核心原理：与凸优化方法不同，正交匹配追踪（OMP）属于贪婪算法，通过迭代地识别支撑集（非零系数的位置）来逼近原始信号。其核心步骤为：在每次迭代中，选择与当前残差相关性最强的原子（感知矩阵 A 的列），将其加入支撑集，然后通过最小二乘更新系数估计，并更新残差。算法在达到预设稀疏度 K 或残差阈值时停止。
操作流程：OMP 的典型实现步骤如下：
- 初始化：残差 r₀ = y，支撑集 Λ₀ = ∅，迭代计数 t = 1；
- 相关计算：计算 Aᵀrₜ₋₁，找到值最大的索引 λₜ；
- 支撑集更新：Λₜ = Λₜ₋₁ ∪ {λₜ}；
- 系数更新：θ̂ₜ = argmin ‖y - A_Λₜ θ‖₂（最小二乘）；
- 残差更新：rₜ = y - A_Λₜ θ̂ₜ；
- 迭代判断：若 t < K 且 ‖rₜ‖₂ > ε，则 t = t+1 返回步骤②；否则停止。
OMP 的计算复杂度为 O(K·m·N)，远低于基追踪的 O(N³)。对于 K ≤ 100 的问题，OMP 在毫秒级即可完成重建，非常适合实时性要求高的光学系统（如视频帧重建）。
| 算法 | 类型 | 复杂度 | 重建质量 | 适用场景 |
|---|---|---|---|---|
| 基追踪（BP） | 凸优化 | O(N³) | 最优（全局解） | 离线处理、高精度需求 |
| OMP | 贪婪 | O(K·m·N) | 良好（次优） | 实时处理、K 较小 |
| CoSaMP | 贪婪 | O(K·m·N) | 接近 BP | K 较大时的快速重建 |
| ISTA/FISTA | 迭代阈值 | O(N·logN) | 良好 | 大规模问题、GPU 加速 |
| ADMM | 分裂 | O(N·logN) | 良好 | 含 TV 正则项的问题 |
2.4 凸优化理论：从 ℓ₁ 到全变分正则化
核心原理：凸优化是压缩感知重建的理论基石。除了 ℓ₁ 范数最小化，实际光学系统中更常用的是包含正则项的组合优化问题：
min_x (1/2)‖y - Φx‖₂² + λ·R(x)其中 R(x) 为正则项。当 R(x) = ‖Ψᵀx‖₁ 时，即为稀疏正则化；当 R(x) = TV(x)（全变分）时，能更好地保持图像边缘。TV 正则化的定义为：
TV(x) = Σᵢⱼ √( (xᵢ₊₁,ⱼ - xᵢ,ⱼ)² + (xᵢ,ⱼ₊₁ - xᵢ,ⱼ)² )求解方法：对于 TV 正则化问题，常用的求解算法包括：① 原始-对偶算法（Chambolle-Pock）；② 分裂布雷格曼（Split Bregman）；③ ADMM（交替方向乘子法）。这些算法将复杂问题分解为若干子问题，每个子问题有闭式解或快速算法。
2.5 算法选择与工程实践总结
判断路径：在实际光学系统中选择重建算法时，应遵循以下决策流程：
- 信号维度与稀疏度：若 N < 10⁴ 且 K < 100，优先选择 OMP（实时性）；若 N > 10⁵，选择 FISTA 或 ADMM（内存友好）；
- 噪声水平：高 SNR（> 30 dB）时 OMP 足够；低 SNR 时选择 BP 或 TV 正则化；
- 实时性要求：视频帧率 > 30 fps 时，需使用 GPU 加速的 FISTA 或专用硬件实现 OMP；
- 图像特征：若图像边缘丰富，TV 正则化优于 ℓ₁ 稀疏正则化；若图像在变换域高度稀疏，则 ℓ₁ 更合适。
总结复盘：压缩感知的数学工具链可以概括为“一个前提、两个条件、三类算法”。一个前提是信号的稀疏表示；两个条件是 RIP 条件和测量数下界；三类算法分别是凸优化（BP、ADMM）、贪婪算法（OMP、CoSaMP）和迭代阈值算法（ISTA、FISTA）。在实际工程中，没有“万能”的算法，必须根据信号特性、系统约束和计算资源进行权衡。建议在项目初期建立一个小型仿真平台，对比不同算法在真实测量矩阵下的性能，再决定最终方案。