压缩感知简介

1. 压缩感知

整个压缩感知体系是由Emmanuel Candés、Justin Romberg、Terence Tao和David Donoho建立的。

压缩感知理论指出稀疏的或具有系数表达的有限维数的信号可以利用远小于奈奎斯特采样数量的线性、非自适应的测量值无失真的重建出来。该理论一经提出，便在信息论、信号/图像处理、医疗成像、射电天文、模式识别、光学/雷达成像和信道编码等诸多领域引起广泛关注。¹

1.1 压缩感知的数学模型

首先介绍压缩感知的数学模型。对于一个一维信号$x∈R^N$，$x$中只包含$K$个非零元素。假设通过一个测量矩阵$Φ$获取$M$个线性测量值，即可通过下面的数学模型描述整个采样过程:

$$y = Φx \tag1$$

其中，$Φ$是一个大小为$M×N$的矩阵，$y$是采样得到的测量值，$y∈R^M$ 。可以看到矩阵$Φ$实际上表示了一个降维的投影操作，将$R^N$映射到$R^M$中，一般来说，矩阵$Φ$的列数远多于行数，即$K<M≪N$。矩阵$Φ$又被称为测量矩阵。这种数学模型就是对压缩感知框架的基本描述。
在现实世界中，很多实际的目标信号本身并不具有稀疏性。但是往往会在某个正交变换域中或者某个稀疏字典$Ψ$中具有稀疏性。例如，自然图像通常会在小波域中表现出稀疏特性。
为了增加压缩感知信号处理的普适性，尽管目标信号$x$本身不具有稀疏性，但是它在变换域Ψ中能体现出稀疏性，即$x=Ψs$，其中$s$信号具有较少的非零元素。矩阵$Ψ$被称为稀疏基矩阵。压缩感知方程这时可以表示为:

$$y = ΦΨs \tag2$$

假设合并矩阵$Φ$与$Ψ$，即$Θ=ΦΨ$。矩阵$Θ∈R^{M×N}$称为传感矩阵。那么压缩感知的数学模型最终可以表述为:

$$y = Θs \tag3$$

对于$ (1) $式，显然是一个欠定的方程组。在已知$y$和$Φ$的情况下常规方法是无法求解$x$的（要么有无穷多个解，要么无解）。在压缩感知体系下，如果满足两个前提条件，就可以近似恢复出原始信号$x$。

1. 原始信号$x$是稀疏的或者可压缩的。
2. 测量矩阵$Φ$或者传感矩阵$Θ$满足RIP。

1.2 约束等距特性RIP

整个压缩感知体系中有两个重要的问题。第一个就是如何构建合适的测量矩阵$ Φ $， 使得它在压缩采样过程中能能够保留目标信号$x$的主要信息。
E. Candés和T.Tao在2005年引入了约束等距特性²（restricted isometry property，RIP），用来描述现实环境中稀疏信号x可重构的条件，即测量矩阵Φ需要满足的充分条件。首先给出K阶约束等距特性的定义。

定义1： 如果存在$ \delta _k \in \left( 0,1\right) $，使得

$$\left( 1-\delta _{k}\right) \left\| x\right\| ^{2}_{ℓ_{2}}\leq \left\| \Phi x\right\| ^{2}_{ℓ_{2}}\leq \left( 1+\delta _{k}\right) \left\| x\right\| ^{2}_{ℓ_{2}} \tag4$$

对所有$K$阶稀疏向量$x$都成立，则称矩阵$\Phi$满足$K$阶约束等距特性。其中最小的$ \delta _k $称为约束等距常数RIC。
如果对于任意$K$阶稀疏信号$x_1$和$x_2$，其差值$x_1-x_2$是$2K$稀疏的，如果满足测量矩阵$Φ$满足

$$\left( 1-\delta _{2k}\right) \left\| x_1-x_2 \right\| ^{2}_{ℓ_{2}}\leq \left\| \Phi x_1-x_2 \right\| ^{2}_{ℓ_{2}}\leq \left( 1+\delta _{2k}\right) \left\| x_1-x_2 \right\| ^{2}_{ℓ_{2}} \tag5$$

就保证了不会出现不同的$x_1$与$x_2$，他们的观测值$Φx_1$与$Φx_2$相同的情况，即保证了测量值完全保持了原信号的特性。所以，矩阵满足$2K$阶RIP保证了能够把任意一个$K$稀疏信号$x$映射为唯一的$y$。

判断一个矩阵具有RIP特性或者确定其的RIC常数很难计算，导致无法在实际中使用该规则判断一个测量矩阵是否满足条件。Richard Barniuk³给出了RIP的等价条件。首先给出相关性与相关系数的定义。
定义2： 考虑一个字典$Θ=[ΦΨ]$, $Φ$和$Ψ$均是$n×n$的正交基，$μ(Φ,Ψ)$是相关系数，定义为：

$$\mu \left( \Phi ,\Psi \right) =\sqrt {n}\max _{i\leq k,j\leq n}\left| <\phi_k \psi_j >\right| \tag6$$

$μ(Φ,Ψ)∈[1,√n]$且$μ(Φ,Ψ)$越小，就表式越不相关。正交矩阵的相关系数为1，如果$μ(Φ,Ψ)=1$则表示$Φ$和$Ψ$不相关。
Richard Barniuk给出的RIP等价条件是，在目标信号$x$在经过某个稀疏变换$Ψ$后的信号是稀疏的前提下，传感矩阵$Θ=ΦΨ$满足RIP条件等价于$Φ$和$Ψ$不相关。或者表述为二者高度不相关，即$μ(Φ,Ψ)$接近1的时候，传感矩阵$Θ$很大概率上满足RIP条件。由于一定信号的稀疏基往往是固定的，RIP条件的满足就通过寻找合适的测量矩阵$Φ$来完成。
压缩感知采样是否存在普适的测量矩阵？E. Candés和T.Tao 证明了独立同分布的高斯随机测量矩阵⁴可以作为普适的压缩感知测量矩阵，其与绝大多数稀疏基矩阵均是不相关的。但是高斯矩阵需要较大的存储空间。在现在图像的压缩采样中，也经常采用扰乱和分块的哈达玛矩阵（Scrambled Block Hadamard Ensemble, SBHE）或者结构化的随机矩阵（Structurally Random Matrices，SRM）作为测量矩阵。

参考文献：

¹. 压缩感知浅析 李峰 郭毅 著 科学出版社 2015年10月第一版 ↩

². E. J. Candes and T. Tao, “Decoding by linear programming,” IEEE Trans. Inf. Theory, vol. 51, no. 12, pp. 4203–4215, 2005 ↩

³. R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, “A simple proof of the restricted isometry property for random matrices,” Constr. Approx., vol. 28, no. 3, pp. 253–263, 2008. ↩

⁴. E. J. Candès, J. K. Romberg, and T. Tao, “Stable signal recovery from incomplete and inaccurate measurements,” Commun. Pure Appl. Math. ,vol. 59, no. 8, pp. 1207–1223, 2006. ↩

参考链接：

形象易懂讲解算法II——压缩感知

[转载]压缩感知（Compressive Sensing）

压缩感知测量矩阵之有限等距性质（Restricted Isometry Property, RIP）