KNOWECON WIKI

ARTICLE

压缩感知

压缩感知 (Compressed Sensing / Compressive Sensing) 压缩感知（Compressed Sensing 或 Compressive Sensing，简称 CS）是一套关于从远少于传统采样定理所要求的测量数中精确恢复稀疏信号的数学理论与方法。该理论由 Emmanuel Candès、Justin Romberg、Tere

浏览 4 更新 2025-11-08

压缩感知 (Compressed Sensing / Compressive Sensing)

压缩感知（Compressed Sensing 或 Compressive Sensing，简称 CS）是一套关于从远少于传统采样定理所要求的测量数中精确恢复稀疏信号的数学理论与方法。该理论由 Emmanuel Candès、Justin Romberg、Terence Tao 和 David Donoho 于 2004–2006 年间奠基性地建立，其核心洞见是：如果一个信号在某个基（basis）下是稀疏的（即仅含少量非零系数），那么只需进行与稀疏度成比例的测量，再通过凸优化即可高概率地精确重构原信号。这一发现颠覆了 奈奎斯特-香农采样定理 所确立的"采样频率必须至少为信号带宽两倍"的经典教条，将采样负担从信号带宽转移到了信号的信息内容（稀疏度）上，因而被称为信号处理领域自香农以来的最重要突破。

问题设定与数学模型

考虑一个有限维实信号 x∈Rn \mathbf{x} \in \mathbb{R}^n 。我们无法直接观测 x \mathbf{x} ，而只能获得 m m 次线性测量：

y=Φx,\mathbf{y} = \Phi \mathbf{x},

其中 Φ∈Rm×n \Phi \in \mathbb{R}^{m \times n} 为测量矩阵（sensing matrix），y∈Rm \mathbf{y} \in \mathbb{R}^m 为测量向量。当 m≪n m \ll n 时，线性系统 y=Φx \mathbf{y} = \Phi \mathbf{x} 是严重欠定的：有无穷多个解，仅凭线性代数不足以唯一确定 x \mathbf{x} 。

关键的稀疏性假设是：x \mathbf{x} 在某个已知的标准正交基 Ψ \Psi 下是 s s -稀疏的，即：

x=Ψα,∥α∥0:=∣supp⁡(α)∣≤s≪n.\mathbf{x} = \Psi \boldsymbol{\alpha}, \quad \|\boldsymbol{\alpha}\|_0 := |\operatorname{supp}(\boldsymbol{\alpha})| \leq s \ll n.

等价地，可认为 x \mathbf{x} 本身在恒等基下即为稀疏。记 A=ΦΨ A = \Phi \Psi 为等效传感矩阵，则 y=Aα \mathbf{y} = A \boldsymbol{\alpha} ，目标是求解：

min⁡α∥α∥0s.t.Aα=y.(1)\min_{\boldsymbol{\alpha}} \|\boldsymbol{\alpha}\|_0 \quad \text{s.t.} \quad A \boldsymbol{\alpha} = \mathbf{y}. \tag{1}

然而 ℓ0 \ell_0 最小化是 NP-hard 的组合优化问题，无法在多项式时间内精确求解。压缩感知的核心理论贡献在于证明了：当测量矩阵满足特定条件时，用 ℓ1 \ell_1 范数替代 ℓ0 \ell_0 （凸松弛）不仅可以计算，而且其解精确等于最稀疏解。

核心理论：RIP 与 ℓ1 \ell_1 恢复保证

受限等距性质（Restricted Isometry Property, RIP）由 Candès 和 Tao 于 2005 年引入，是分析压缩感知恢复性能的核心工具。

定义

矩阵 A∈Rm×n A \in \mathbb{R}^{m \times n} 称为满足 s s 阶 RIP，若存在常数 δs∈(0,1) \delta_s \in (0, 1) ，使得对所有 s s -稀疏向量 v∈Rn \mathbf{v} \in \mathbb{R}^n ，均有：

(1−δs)∥v∥22≤∥Av∥22≤(1+δs)∥v∥22.(1 - \delta_s)\|\mathbf{v}\|_2^2 \leq \|A\mathbf{v}\|_2^2 \leq (1 + \delta_s)\|\mathbf{v}\|_2^2.

最小的此类 δs \delta_s 称为 s s 阶受限等距常数。

RIP 本质上是要求 A A 的任意 s s 列近似构成正交系：测量过程在稀疏信号子集上近似保持欧氏距离。直观上，这意味着不同的稀疏信号在经过 A A 后不会"混淆"得无法区分。

核心恢复定理（Candès, Romberg \& Tao, 2006）：若 A A 满足 2s 2s 阶 RIP 且 δ2s<2−1 \delta_{2s} < \sqrt{2} - 1 ，则凸优化问题

min⁡α∥α∥1s.t.Aα=y(2)\min_{\boldsymbol{\alpha}} \|\boldsymbol{\alpha}\|_1 \quad \text{s.t.} \quad A \boldsymbol{\alpha} = \mathbf{y} \tag{2}

的解 α^ \hat{\boldsymbol{\alpha}} 满足：

∥α^−α∥2≤C0∥α−αs∥1s,\|\hat{\boldsymbol{\alpha}} - \boldsymbol{\alpha}\|_2 \leq C_0 \frac{\|\boldsymbol{\alpha} - \boldsymbol{\alpha}_s\|_1}{\sqrt{s}},

其中 αs \boldsymbol{\alpha}_s 是保留 α \boldsymbol{\alpha} 中绝对值最大的 s s 个分量的最佳 s s -稀疏逼近，C0 C_0 为与 δ2s \delta_{2s} 有关的常数。若信号本身即为精确 s s -稀疏，则恢复是精确的：α^=α \hat{\boldsymbol{\alpha}} = \boldsymbol{\alpha} 。

后续研究将 RIP 常数要求逐步放宽：Foucart 和 Lai（2009）将充分条件改进为 δ2s<0.4531 \delta_{2s} < 0.4531 ；Cai 和 Zhang（2014）进一步将界推至 δs<1/3 \delta_{s} < 1/3 附近。实际中更常用的分析工具是 互相关性（mutual coherence）条件，以及基于随机矩阵的高概率 RIP 构造。

随机测量与采样效率

RIP 理论中一个既深刻又实用的结果是：多种随机矩阵族以高概率满足 RIP，且所需测量数 m m 仅与稀疏度 s s 和信号维度 n n 成对数依赖关系。具体而言：

  • 高斯随机矩阵（Aij∼N(0,1/m) A_{ij} \sim \mathcal{N}(0, 1/m) ）：当 m≥Cslog⁡(n/s) m \geq C s \log(n/s) 时，以压倒性概率满足 δ2s≤δ \delta_{2s} \leq \delta ；
  • 伯努利随机矩阵（Aij=±1/m A_{ij} = \pm 1/\sqrt{m} 等概率）：同上；
  • 随机部分傅里叶矩阵（从 n×n n \times n 的 DFT 矩阵中随机选取 m m 行并归一化）：m≥Cslog⁡4n m \geq C s \log^4 n 即可。

这一结果的启示是深远的：在许多实际场景中，s≪n s \ll n 且 m≈3s–5s m \approx 3s\text{–}5s 即足以稳健恢复，这意味着测量数可以比信号维度小一个数量级以上。随机部分傅里叶矩阵的特殊重要性在于它直接催生了稀疏 MRI 等医学成像加速技术——在 MRI 中，每次测量耗时较长，减少扫描行数即为减少患者等待时间。

恢复算法：从凸优化到贪婪迭代

除 ℓ1 \ell_1 最小化（式 (2)）外，压缩感知的算法工具箱极为丰富，大致可分为三类：

第一类：凸优化方法。 对于含噪测量 y=Aα+e \mathbf{y} = A \boldsymbol{\alpha} + \mathbf{e} （∥e∥2≤ε \|\mathbf{e}\|_2 \leq \varepsilon ），典型形式为 LASSO 或 基追踪去噪（BPDN）：

min⁡α12∥Aα−y∥22+λ∥α∥1,\min_{\boldsymbol{\alpha}} \frac{1}{2}\|A\boldsymbol{\alpha} - \mathbf{y}\|_2^2 + \lambda \|\boldsymbol{\alpha}\|_1,

这正是 LASSO 回归的数学形式，也是压缩感知与 高维统计 之间最直接的理论桥梁。优化可用内点法、临近梯度法（ISTA/FISTA）或交替方向乘子法（ADMM）求解，在大规模问题中后者尤为常用。

第二类：贪婪算法。 包括匹配追踪（MP）、正交匹配追踪（OMP）、压缩采样匹配追踪（CoSaMP）、迭代硬阈值（IHT）等。这类方法以迭代方式逐步构建支撑集，每次选择与当前残差最相关的原子，计算量通常低于凸优化，但恢复保证稍弱于 ℓ1 \ell_1 方法。OMP 在 ∥α∥0=s \|\boldsymbol{\alpha}\|_0 = s 且互相关性 μ<1/(2s−1) \mu < 1/(2s-1) 时保证精确恢复。

第三类：贝叶斯方法与消息传递。 近似消息传递（AMP）算法将压缩感知视为统计推断问题，在高维极限 n,m,s→∞ n, m, s \to \infty 且比率固定时可精确刻画相变（phase transition）边界，提供了ℓ1 \ell_1 方法与组合方法之间的性能参照系。

与经济学和计量经济学的关联

压缩感知与经济学之间的桥梁主要架设在 高维计量经济学 领域。现代经济数据——如个体层面的消费面板、合同文本语料、社交网络交互——的维度 p p 常常远超样本量 n n （即 p≫n p \gg n 设定）。传统的 普通最小二乘（OLS）在此失效，而压缩感知的 ℓ1 \ell_1 正则化思想为"从众多候选变量中筛选少数具有显著解释力的变量"提供了严格的数学框架。

具体而言，LASSO（Tibshirani, 1996）在高维稀疏线性回归中的应用与压缩感知共享几乎一致的理论基础。Belloni、Chernozhukov 和 Hansen（2014）将 LASSO 等后双重选择（post-double-selection）方法引入因果推断框架，利用 ℓ1 \ell_1 惩罚在高维控制变量中自动筛选混淆因子，从而在 p>n p > n 的设定下实现一致的平均处理效应估计。Chetty 等（2009）在超额收益预测的变量选择中使用了类似的稀疏建模策略。

此外，矩阵压缩感知的进展——特别是低秩矩阵恢复（Candès \& Recht, 2009）与鲁棒主成分分析——已渗透至 因子模型 估计和宏观经济预测中。面板数据中的交互固定效应模型、推荐系统中的矩阵补全问题（如 Netflix Prize），其数学本质都是重构具有低秩结构的数据矩阵，而压缩感知提供的核范数最小化框架正是处理此类问题的标准工具。

扩展方向与开放问题

在核心理论成熟之后，压缩感知的研究前沿已向多个方向延伸。

结构化稀疏性与模型驱动恢复是其中最富实践价值的分支。单纯的 s s -稀疏假设在多维信号（图像、视频、高光谱数据）中显得过于简单：自然图像的小波系数不仅稀疏，其非零系数往往聚集成树状结构；雷达信号的稀疏分量在时频平面上倾向于形成连续轨迹。利用这些结构先验（如分组稀疏、树稀疏、块稀疏）设计结构化惩罚项，可在相同测量数下显著提升恢复质量。

非凸替代是另一活跃方向。ℓ1 \ell_1 范数作为 ℓ0 \ell_0 的凸松弛，在高噪声或极低采样率下存在偏差——回归系数被系统性向零压缩。用 ℓp \ell_p （0<p<1 0 < p < 1 ）、平滑裁剪绝对偏差（SCAD）、极小极大凹惩罚（MCP）等非凸惩罚替代 ℓ1 \ell_1 ，可缓解此偏差，但代价是优化问题变为非凸，需借助迭代重加权 ℓ1 \ell_1 或局部线性逼近策略求解。

非线性压缩感知将线性测量假设 y=Φx \mathbf{y} = \Phi\mathbf{x} 推广至非线性前向算子，如相位恢复（yi=∣⟨ai,x⟩∣2 \mathbf{y}_i = |\langle \mathbf{a}_i, \mathbf{x}\rangle|^2 ）、单像素相机和深度学习驱动的逆问题。生成式压缩感知（Bora et al., 2017）利用预训练的 生成对抗网络（GAN）替代稀疏基，将信号约束在低维生成流形上而非稀疏子空间，以远少于经典 CS 理论的测量数实现令人瞩目的图像重建——但其理论保证仍处于初步阶段。

量子压缩感知利用量子态的希尔伯特空间结构，尝试以指数级减少的测量数完成量子态层析，是一个高度理论化但潜力巨大的方向。

在应用层面，压缩感知已被广泛部署于医学成像（加速 MRI、低剂量 CT）、射电天文学（干涉阵综合成像）、雷达成像与无线通信（稀疏信道估计）、以及单像素相机原型系统中。可以预见，随着传感硬件与算法的协同进化，压缩感知将在测量成本高昂或物理上不可增加测量次数的领域持续释放价值。