An Introduction To Compressive Sampling 阅读笔记

通常我们讲的采样都要求采样率至少两倍于带宽,这是香农在1948年就提出了的。而本文讲的则恰恰相反,本文试图介绍如何使用压缩感知(Compressive Sampling/Sencing)的方式,使用尽量少的样本,刻画出信号本身。

从实用性角度来看,尽管本文的所有算法都可以拓展至连续信号,但是本文将单纯讲述离散信号在欠采样时的CS,毕竟这才是对工业界最有意义的。因为在离散前采样的信号中,有一个很重要的问题——

压缩感知的原理

假设有一个离散信号f \in R^n,是否有可能构造出m \ll n个波形,能够“几乎”完整刻画原来f所携带的信息?

首先向讲一讲关于稀疏性(Sparsity)的问题,令f =  \Psi x,其中\Psi是一个n\times n的矩阵。我们可以理解为将f使用特征x进行表征,而倘若我们提取x中前S大的值,而将其他位置强行置0(这样便于压缩,且不会显著对于结果产生影响),则称呼得到的向量x_S为S稀疏向量(S-sparse). 此时,我们可以通过x_S计算出f_S  = \Psi x_S

那么,接下来,m的取指大概为多少可以保证信号能够被“几乎”完整恢复呢?论文通过一系列推导,给出了一个式子

m \geq C \cdot \mu^2(\Phi, \Psi) \cdot S \cdot log n

其中\mu函数表征了感知基\Phi和表征基\Psi的相关程度,S是指x是S-sparse向量,C是某个常数。

而上述公式带入实际的图像压缩中,每一个缺失项倘若对应至少四个不连续的采样点,就能准确恢复原来的图像。

若干难题

文中提出并解决了基于上述算法的两个问题——

  1. 对于极其欠采样的样本,是否可以恢复如此高的分辨率?
  2. 实际的检测设备都存在噪音,噪音将如何影响该算法?

为了解决上述两个问题,作者提出了一个叫做restricted isometry property(RIP)的限制条件,倘若条件满足,不仅欠采样样本可以被完整恢复,而且还可以将误差限制在一个较小的区间中。而RIP的细节这里不叙述。

感知基的选择

感知基选择非常随便,只要满足RIP准则就可以。而文中提到了在单位球体上面随机取点,或者使用标准正交基与一个随机矩阵的乘积生成。

应用

  1. 数据压缩
  2. 信道编码
  3. 数据获取

等等

参考文献

  • E. J. Candès and M. B. Wakin, An introduction to compressive sampling, IEEE Signal Processing Magazine, 21-30, March 2008.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据