初步接触压缩感知，以此记录学习过程。内容均为自身理解，若有错误，欢迎指正~

一、什么是压缩感知（CS）

概括性描述：如果一个信号在某个变换域是稀疏的，便可用一个与变换基不相关的观测矩阵将变换所得的高维信号投影到一个低维空间上，然后通过求解一个优化问题，从少量的投影中以高概率重构原信号。

其提出是基于对奈奎斯特采样定理（采样后完整保留原始信号的信息，采样频率必须大于信号中最高频率的2倍）的质疑，大牛陶哲轩等人提出：如果信号是稀疏的，那么它可以由远低于采样定理要求的采样点重建恢复。
其主要分为两个部分：①信号的获取采样②信号的重构恢复
陶等的突破观点便在于采样方式，当涉及采样频率是便意味着做等间距采样，而压缩感知采用随机亚采样，举例如fig.1所示，原信号a在频域上是稀疏的，采用随机亚采样的方式，如图b中上方红点所示，得到c中的结果，最大的几个峰值仍依稀可见，只是一定程度上被干扰覆盖(此时频谱不再是整齐的搬移，而是小部分随机的搬移，导致频率泄露均匀分布再整个频域,但泄露值都会比较小，所以有了恢复的可能)。

之后便是对于原始信号的恢复，以MP（匹配追踪）为例：
(1) 由于原信号的频率非零值在亚采样后的频域中依然保留较大的值，其中较大的两个可以通过设置阈值，检测出来（图a）。
(2) 然后，假设信号只存在这两个非零值（图b），则可以计算出由这两个非零值引起的干扰（图c）。
(3) 用a减去c，即可得到仅由蓝色非零值和由它导致的干扰值(图d），再设置阈值即可检测出它，得到最终复原频域（图e）
(4) 如果原信号频域中有更多的非零值，则可通过迭代将其一一解出。

二、压缩感知的数学表示

如Fig.3所示，是压缩感知的数学表示示意图。其中压缩感知的数学表示即y=Φx，而由于信号x通常不是稀疏的，但在某个变换域Ψ是稀疏的，即x=Ψs，其中s是K稀疏的，则推出y=ΦΨs=As
下面对涉及符号进行一一说明：
x：大小为Nx1。稀疏度为K的原信号，即待恢复信号。未知。
y：大小为Mx1。观测所得向量，观测值。已知
s：K稀疏的，即x在某个变换域的稀疏表示。
Ψ：大小为NxN。稀疏基矩阵（部分文献称变换矩阵、变换基、稀疏矩阵、稀疏基、正交基字典矩阵等），即某个变换域的完备正交基，可用于表示x等。需要人为选取，一般可知，如频域中傅里叶变换中的正交基矩阵等。
Φ：大小为MxN。观测矩阵（部分文献称测量矩阵，观测基等），对应着亚采样这一过程。作用是将高维信号投影到低维中，是人为选择的，要求与稀疏基矩阵不相干（后面会讲到稀疏基矩阵）。已知
（注：当前已被证明的与任何基均不相干的有高斯分布或贝努力分布抽取的随机矩阵或部分傅里叶矩阵等。但由于此类矩阵存储复制困难，所以提出了确定性和结构化的测量矩阵设计，如循环矩阵等）
A：大小为MxN。传感矩阵（部分文献称测度矩阵、CS信息算子等），A=ΦΨ。

因此，压缩感知问题即在已知观测值y和传感矩阵A的基础上，求解欠定方程组y=As得到s，之后逆运算求得原信号x。
对应到开始的例子即fig.4。x就是三个正弦信号叠加在一起的原信号；稀疏矩阵Ψ就是傅里叶变换，将信号变换到频域S；而观测矩阵Φ就对应了我们采用的随机亚采样方式；y就是最终的采样结果。

三、完美重构的条件

在前述的过程中，可实现最终信号的恢复，满足了两个前提条件：
①信号在对应的变换域上是稀疏的（频域上只有三个非零值）；
②采用随机亚采样机制，因而使频率泄露均匀分布整个频域
以上两点分别对应CS的两个前提条件——稀疏性、非相干性
1、稀疏性
所谓稀疏性，即待恢复的信号需要在某一个变换域具有稀疏性（即在某个变换域只有少量非零值）。在实际中，只要信号近似满足稀疏性，即大部分值趋于零，便可认为该信号是可压缩信号，对其进行亚采样。
2、非相干性
之前提到采用随机亚采样才可实现信号恢复，而陶等大牛给出更为准确的要求，即观测矩阵Φ需要满足约束等距性条件（RIP）（学习压缩感知总会遇到的一个名词。。。相关数学理论较为复杂，之后单开一篇。。。）。其等价条件即观测矩阵Φ与稀疏表示基Ψ不相关。这就是压缩感知的第二个条件，非相干性。

四、当前常用重构算法分类

五、参考

感谢以下两篇文章：强推~
【1】知乎：形象易懂讲解算法II——压缩感知
【2】压缩感知重构算法之正交匹配追踪(OMP)