1 压缩感知的简介

1.1 提出

D． Donoho、E． Candes 及华裔科学家 T． Tao等人提出了一种新的信息获取理论 － 压缩感知（Compressive Sensing）

Donoho D L． Compressed sensing［J］ ． IEEE Transactions on Information Theory， 2006， 52( 4) : 1289 － 1306

1.2 评价

• 突破了香农-奈奎斯特采样定理的限制。
• 实现对信号采样的同时完成压缩的过程。
• 并不直接测量信号本身， 它使用非自适应线性投影（感知矩阵）来获得信号的整体构造从而直接得到重要的信息， 忽略那些在有损压缩中会被丢弃的信息。

1.3 主要过程

• 稀疏表示：信号稀疏域的选取，是压缩感知理论的基础和前提; （参考信号的稀疏性可以参考另一篇blog【压缩感知合集2】（背景知识）信号稀疏表示的数学推导和解释理解）
• 投影测量：已经证明大部分具有一致分布的随机矩阵都可以作为观测矩阵;
• 重构算法：由于压缩感知采用的是全局非自适应测量方法， 观测数量远远少于信号长度， 从而数据采集量大大减少。但是需要付出的代价是信号重建算法的软件成本。

1.4 简洁概括

如果信号是稀疏的，那么它可以由远低于采样定理要求的采样点重建恢复。

2 压缩感知的数学模型

给定输入信号$\mathbf{X}\in {\mathbb{R}}^{N\times 1}$，最终想要得到压缩信号$\mathbf{A}\in {\mathbb{R}}^{M\times 1}$，$K<<N$

2.1 压缩过程（感知过程）分为（稀疏变换和投影测量）

2.1.1 稀疏变换（稀疏表示、稀疏过程）

找到一个基或者过完备字典$\mathbf{\Psi }$，使得信号$\mathbf{X}$在$\mathbf{\Psi }$域是稀疏的，（参考补充材料稀疏）满足下面的公式
$$\mathbf{X}=\mathbf{\Psi }\mathbf{Y}$$
因为是规范正交基所以实现变换系数也就是压缩信号： $\mathbf{Y}={\mathbf{\Psi }}^T\mathbf{X}$，其中 $\mathbf{Y}$ 是 $\mathbf{X}$ 的等价或逼近的稀疏表示。变换基$\mathbf{\Psi }$的选择可以为某
种已被广泛应用的基，如小波基、傅里叶基、局部傅里叶基等。另外，可以使用紧框架（原子字典）来对信号进行稀疏表示， 如曲线波和轮廓波， 这两类变换基具有更好的方向性，并且各向异性，少量系数即可有效地捕捉图像的边缘轮廓，在边缘表示方面优于小波。

2.1.2 投影测量（测量过程）

观测矩阵 $\mathbf{\Phi }\in {\mathbb{R}}^{M\times N}$，观测矩阵也叫测量矩阵，感知矩阵，实现的功能是对信号进行降维和压缩
$$\mathbf{A}=\mathbf{\Phi }\mathbf{X}$$
同时也是对在$\mathbf{\Psi }$域上的稀疏投影$\mathbf{Y}$进行投影测量
$$\mathbf{A}=\mathbf{\Phi }\mathbf{\Psi }\mathbf{Y}$$
矩阵$\mathbf{\Phi }$需要满足的性质（需要保证稀疏向量 $\mathbf{Y}$ 从$N$维降到 $K$ 维时重要信息不被破坏。）

变换基$\mathbf{\Psi }$不相关（会在之后的blog中有叙述）

有限等距性（Restricted Isometry Property，RIP）（会在之后的blog中有叙述）

2.1.3 整个压缩过程总结

整个压缩过程也可以被称为感知过程
$$\mathbf{A}=\mathbf{\Phi }\mathbf{X}=\mathbf{\Phi }\mathbf{\Psi }\mathbf{Y}=\mathbf{\Theta }\mathbf{Y}$$

$\mathbf{\Theta }$即为感知过程的核心命名为感知矩阵

符号	含义	维度	属性
$\mathbf{X}$	输入信号；待压缩信号	${\mathbb{R}}^{N\times 1}$	未知，需要恢复
$\mathbf{\Phi }$	观测矩阵；测量矩阵	${\mathbb{R}}^{M\times N}$	已知（非自适应性）
$\mathbf{\Psi }$	变换矩阵；变换基矩阵；稀疏基矩阵；稀疏矩阵；正交基字典矩阵	${\mathbb{R}}^{N\times N}$	已知（非自适应性）
$\mathbf{Y}$	正交基变换后的稀疏表示	${\mathbb{R}}^{N\times 1}$	未知，需要恢复
$\mathbf{\Theta }$	感知矩阵	${\mathbb{R}}^{M\times N}$	已知（非自适应性）
$\mathbf{A}$	观测压缩所得到压缩信号	${\mathbb{R}}^{M\times 1}$	已知

2.2 恢复过程：重构算法的数学表示

在得到已经压缩完的采样信号$\mathbf{A}$后，根据确定的固定性观测矩阵$\mathbf{\Phi }$和稀疏矩阵$\mathbf{\Psi }$的先验信息进行恢复，数学表达如下
$$\check{\mathbf{X}}=f(\mathbf{A},\mathbf{\Theta })$$
若$N=M$，正定方程有唯一解

而$M<<N$，欠定方程

一般可以抽象为如下求解任务
$$\begin{gathered} \min {\Vert {\mathbf{\Psi }}^T\mathbf{X}\Vert }_0 \\ s.t.\mathbf{\Theta }\mathbf{X}=\mathbf{\Phi }\mathbf{\Psi }\mathbf{X}=\mathbf{A} \end{gathered}$$

注意

若$N=M$，则可轻松由$\mathbf{A}$解出$\mathbf{X}$和$\mathbf{Y}$

而$M<<N$，可根据稀疏表示下的信号$\mathbf{Y}$和矩阵所具有的RIP特性重构

LAST、参考文献

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