› 压缩感知 L1 重构 模拟器 返回
信号处理·稀疏表示

压缩感知 L1 重构 模拟器

从远少于 Nyquist 采样定理要求的 M 次观测中，使用 L1 最小化恢复 N 维信号中仅有 K 个非零元素的"稀疏信号"的压缩感知（Compressive Sensing）体验工具。改变信号维度、观测数、观测矩阵、噪声、重构算法后，Candes-Tao 理论条件、RIP、重构误差可实时显示。

参数设置
信号维度 N
要恢复的信号 x 的采样数
稀疏数 K
非零元素的个数（K-稀疏中的 K）
观测数 M
压缩观测向量 y 的采样数
观测矩阵 Φ
选择满足 RIP 的矩阵，用更少的 M 就能重构
噪声标准差 σ
观测噪声 y = Φx + n（n ~ N(0, σ²)）
重构算法
BP=精确／IST=迭代／OMP=贪心
计算结果
—
压缩率 M/N (%)
—
理论最小 M (Candes-Tao)
—
信息比 M/M_req
—
RIP 常数 δ_2K
—
重构误差 ‖x̂−x‖₂
—
计算复杂度 log10(ops)
—
Φx → y → x̂ 流水线可视化

左：N 维稀疏信号 x（K 个脉冲），中央：M×N 观测矩阵 Φ，右：M 维压缩观测 y 和 L1 重构结果 x̂ 的比较。颜色深浅表示振幅，绿色=重构成功，红色=失败。

原始信号 vs 重构信号
重构成功率 vs 压缩率 M/N
理论·主要公式

$$\min_x \|x\|_1 \text{ s.t. } \|y - \Phi x\|_2 \leq \epsilon,\quad M \geq C\,K\,\log(N/K)$$

L1 最小化问题（基础追踪）和 Candes-Tao 理论观测数。y=观测向量(M×1)、Φ=观测矩阵(M×N)、x=稀疏信号(N×1)、ε=噪声容限、常数 C ≈ 2~5。

$$\text{RIP}: (1-\delta_{2K})\|x\|_2^2 \leq \|\Phi x\|_2^2 \leq (1+\delta_{2K})\|x\|_2^2$$

受限等距性（Restricted Isometry Property）。δ_2K < 0.4 时 L1 重构稳定成立。高斯/伯努利矩阵在 M ≥ 5K·log(N/K) 时渐近满足。

$$\|\hat{x} - x\|_2 \leq C_1 \sigma \sqrt{M}\,/\,\sqrt{M - C_2 K \log(N/K)}$$

含噪重构误差的上界。当观测数 M 接近理论最小值时，分母趋于零，误差爆炸。噪声放大率按 BP < IST < OMP 排序。

压缩感知（Compressive Sensing）— L1 重构

🙋
经常听说"压缩感知"，但它和普通的"数据压缩（像 ZIP 那样）"有什么不同呢？
🎓
好问题。ZIP 这样的压缩方式是先 完整观测 信号，再舍弃冗余部分。相比之下，压缩感知（CS）从一开始就只进行少量观测。本应采样 N 个样本的信号只采样 M（≪ N）次，之后用计算恢复 N 维。MRI 的话拍摄时间变成 1/4，单像素相机用 1 个像素就能拍照。2006 年 Candes、Tao、Donoho 证明了"在某些条件下可以概率 1 地完全恢复"，这才是革命性的。
🙋
等等，没有观测的部分也能用"计算恢复"？通常那是不定方程吧，有无穷多个解…
🎓
没错，线性代数上就是不定方程（无穷多解）。但加入信号是"K-稀疏"这个先验信息——即 N 个元素中仅 K 个非零，其余都是零——就能唯一确定。本工具的"稀疏数 K"就是这个概念。然后搜寻让 L1 范数最小 的解，即 ‖x‖₁ = Σ|xᵢ| 最小的 x，奇迹般地就能找到正确答案。而如果用 L2 最小化（普通最小二乘），所有元素都会沾上一点值，最后失败。L1 的"角"引导我们找到稀疏解。
🙋
那么观测数 M 最少要多少呢？上面的计算结果里出现了"信息比 M/M_req"。
🎓
Candes-Tao 发现的魔法公式是 M ≥ C·K·log(N/K)。假设 N=500、K=20，那么 M_req ≈ 129，N=10⁶、K=10⁴ 也只需 M ≈ 50,000。注意是对数而非线性增长，这是关键。默认的 M=100 实际上小于 M_req=129，所以"信息比 0.78"会显示"无法保证重构"。你试试把 M 滑块拉到 130 以上，verdict 就会变绿。
🙋
我把观测矩阵从高斯改成 Hadamard，RIP δ 变大了。这是什么意思？
🎓
RIP（受限等距性，Restricted Isometry Property）是说"把 Φ 作用在任意 2K-稀疏向量上，能量基本保持"的性质。δ_2K < 0.4 左右就能保证 L1 重构稳定。高斯/伯努利随机矩阵从理论上讲 RIP 最优，但实际应用中 Φ 往往由硬件决定，选不了。MRI 就用 DFT 行的随机子集，单像素相机用 Hadamard 等。RIP 变坏的弥补办法是增加 M。
🙋
最后，BP / IST / OMP 怎么选呢？计算复杂度 log10(ops) 差了 1-2 个数量级呢。
🎓
基础追踪（BP）把 L1 最小化当线性规划/锥规划严格求解。可以用 CVXPY、MOSEK 这样的求解器，但复杂度 N³，N=10⁴ 就差不多是上限了。MRI 这种 N=512²=262,144 的世界里，用 FISTA（IST 的加速版）是标配，复杂度只有 N·M·iter。OMP 在 K 较小（几十）且已知时最快，但一旦选错非零位置就回天乏术。研究标准流程是：先用 BP 量"最佳精度"作参考，然后本番用 FISTA 提速。

常见问答

不违反。Nyquist 定理说的是为了完全恢复"任意带限信号"所需的最少观测数。压缩感知把对象限制到"K-稀疏"或可压缩信号的特定类别，利用这个先验信息，就能把观测数降到 M = O(K·log(N/K))。Candes-Tao-Donoho 2006 年的成果表明，观测矩阵满足 RIP（受限等距性）时，L1 最小化以接近 1 的概率完全重构。不是 Nyquist 失效，而是适用范围不同。
从理论讲，高斯随机矩阵或伯努利 ±1 矩阵以接近最优的常数满足 RIP，需最少观测数重构。但实际中受物理可实现性制约。MRI 选 DFT（离散傅里叶）行的随机采样，单像素相机选 Hadamard/伯努利。本工具再现了 Gaussian → Bernoulli → DFT → Hadamard 顺序中 RIP 常数 δ_2K 恶化的趋势。实施时要与硬件协商，以 δ_2K < 0.4 为设计目标。
基础追踪（BP）将 L1 最小化严格作为线性规划/锥规划求解，以最少观测数获最佳精度，但需 N³ 阶计算复杂度。IST/FISTA 只反复进行软阈值，复杂度为 N·M·iter，适大规模问题（MRI 图像 256² 或 512²）。OMP（正交匹配追踪）贪心逐个选非零位，K 小且已知时最快，但选错位置无法纠正。本工具切换"重构算法"可观察噪声放大和复杂度的差异。
在满足条件下已实用化。MRI 中图像在小波域近似稀疏（K/N ≈ 5-10%），k 空间采样减 1/4 仍能重构诊断质量图像，已被 Siemens/GE/Philips 临床机验证。单像素相机由 Rice 大学 Baraniuk 等人 2008 年发表，仅 1 像素传感器、M=1638 观测（压缩率 40%）就能恢复 N=64×64 图像。地震波、无线通信、基因组学也广泛应用。但对不满足 K-稀疏假设的信号（如白噪声）完全无效。

实世界应用

医疗成像（MRI 加速）：压缩感知最成功的实际应用。MRI 图像在小波域近似稀疏，因此即使将 k 空间采样（观测）间隔 1/2~1/4，也能通过 L1 最小化（CS-MRI）恢复诊断质量的图像。临床机器（Siemens 压缩感知 GRASP、GE HyperSense、Philips 压缩 SENSE）已搭载，缩短心脏 MRI 屏气时间、儿童 MRI 麻醉时间。CT 也在研究用于减少射线量。

单像素相机和特殊成像：Rice 大学 Baraniuk 等人 2008 年发表的单像素相机用 DMD（数字微镜）选择 Hadamard/伯努利模式光，仅需 1 个光电二极管就能拍照。对难以制造 CCD 阵列的太赫兹、红外、X 射线波段大有作用，近红外成像和量子成像已在实用化。

无线通信、雷达、地震信号：5G 毫米波的稀疏信道估计、认知无线电的宽带频谱监测、地中雷达和地震波的稀疏反射系数估计等，信号物理上由"少数到达波"组成的问题都标准应用 CS。CS 让 AD 转换器采样率降至 1/10 的亚奈奎斯特接收机已实现。

基因组学·集团测试：COVID-19 检测引起关注的"集团检验"本质是压缩感知。从 N 人感染状态（K 人阳性，K ≪ N）推估，用 M 个混合样本，问题在 CS 框架下形式化，能大幅减少检验试剂。单细胞 RNA-seq 的基因表达推估也有类似应用。

常见误区和注意点

最大陷阱是未验证"信号是否真正 K-稀疏"。CS 理论完全依赖"K-稀疏或 K-可压缩"假设。现实信号很少天然稀疏，需要在小波、DCT、曲波等合适变换域才稀疏。图像在小波域 K/N ≈ 5%、语音在 DCT 域 K/N ≈ 10% 左右是常见目标。完全是白噪声的信号对 CS 毫无效果。"选择恰当基（字典）"是应用工作的 90%。

其次，过高估计抗噪能力。从重构误差公式 ‖x̂−x‖₂ ≤ C·σ·√M / √(M−M_req) 可知，M 接近 M_req 时分母趋零，误差爆炸式增长。论文的"M = M_req 时完全重构"是无噪理想条件。实际应用需 M ≥ 1.5~3 倍 M_req，确保噪声裕度。SNR 低的系统（MRI 常≤20dB）尤其要增大 M。

最后，勿未估算计算量就大规模套用 BP。基础追踪虽理论优美，但 N³ 复杂度使得 N=10,000 时有 10¹² 运算，图像 512²=262,144 时有 10¹⁶ 运算，远超现实。实务中用 FISTA、ADMM、SPGL1 这些一阶法，或 LISTA（ISTA 的神经网展开）。研究原型先用 BP 测"能达到的精度上限"，本番实施时平衡速度与精度，这是标准两阶段流程。

使用指南

  1. 设置信号维度 N（如 1024）和稀疏度 K（如 32），改变观测数 M，验证 Candes-Tao 条件 M ≥ C·K·log(N/K)
  2. 从高斯随机矩阵或傅里叶部分矩阵选择观测矩阵，比较与 Candes-Tao 条件的关系
  3. 在 0~0.1 范围调节噪声，用 BP（基础追踪）、IST（迭代软阈值）、OMP（正交匹配追踪）三算法比较重构误差
  4. 验证 RIP 常数 δ_{2K} 不超过理论值 0.4，确认重构成功条件

具体计算例

N=512 维信号、K=16 稀疏、M=80 观测的情形：压缩率 M/N=15.6%，Candes-Tao 理论最小值 M_min=98（K·log(N/K)≈140）。用高斯随机观测矩阵 RIP δ_{2K}≈0.32，加白高斯噪声 σ=0.01 时，BP 重构误差 ‖x̂−x‖₂≈0.015、IST 约 0.018、OMP 约 0.022，可直观看出 BP 优势。

实务注意事项