压缩感知（Compressive Sensing）学习之（二）
zouxy09@qq.com
上一回粗略的引入了压缩感知。
下面就针对自己的了解，具体总结下压缩感知理论。由于自己也是这几天看到那个《Real-Time Compressive Tracking》
~cslzhang/CT/CT.htm
其涉及到的理论就是压缩感知（或者稀疏表达）。然后感觉不错，了解了解（后面会对这个跟踪算法做介绍，具体见博客更新）。所以接触时间有限，理解未免出错，望各位不吝指正。
简单地说，压缩感知理论指出：只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。
在该理论框架下，采样速率不再取决于信号的带宽，而在很大程度上取决于两个基本准则：稀疏性和非相关性，或者稀疏性和等距约束性。
压缩感知理论主要包括三部分：
（1）信号的稀疏表示；
（2）设计测量矩阵，要在降低维数的同时保证原始信号x的信息损失最小；
（3）设计信号恢复算法，利用M个观测值无失真地恢复出长度为N的原始信号。
理论依据：
（1）设长度为N的信号X在某个正交基Ψ上是K-稀疏的（即含有k个非零值）；
（2）如果能找到一个与Ψ不相关（不相干）的观测基Φ；
（3）用观测基Φ观测原信号得到长度M的一维测量值M个观测值Y，K<M<<N；
（4）那么就可以利用最优化方法从观测值Y中高概率恢复X。
数学表达：
。Φ的每一行可以看作是一个传感器（Sensor），它与信号相乘，拾取（Acquisition）了信号的一部分信息。而这一部分信息足以代表原信号，并能找到一个算法来高概率恢复原信号。
一般的自然信号x本身并不是稀疏的，需要在某种稀疏基上进行稀疏表示，x=Ψs，Ψ为稀疏基矩阵，s为稀疏系数（s只有K个是非零值（K<<N）。
压缩感知方程为y=Φx=ΦΨs=Θs。
将原来的测量矩阵Φ变换为Θ=ΦΨ（称之为传感矩阵），解出s的逼近值s’，则原信号x’ = Ψs’。
1、信号的稀疏表示
信号的稀疏性简单理解为信号中非0元素数目较少，，或者说大多数系数为0（或者绝对值较小）。
自然界存在的真实信号一般不是绝对稀疏的，而是在某个变换域下近似稀疏，即为可压缩信号。或者说从理论上讲任何信号都具有可压缩性，只要能找到其相应的稀疏表示空间，就可以有效地进行压缩采样。信号的稀疏性或可压缩性是压缩感知的重要前提和理论基础。
我们知道，长度为N的信号X可以用一组基ΨT=[Ψ1,…, ΨM]的线性组合来表示：
x=Ψs，Ψ为稀疏基NxN矩阵，s为稀疏系数（N维向量），当信号X在某个基Ψ上仅有 K<<N个非零系数或远大于零的系数s时，称Ψ为信号X的稀疏基。我们需要做的就是合理地选择稀疏基，使得信号的稀疏系数个数尽可能少。
再啰嗦点的话：如果长度为N的信号X，在变换域Φ中只有K个系数不为零（或者明显大于其他系数），且K<<N，那么可以认为信号X在Φ域中是稀疏的并可称为K-稀疏（不是严格的定义）。那么在该域下，我们如果只保留这M个大系数，丢弃其他的系数，则可以减小储存该信号需要的空间，达到了压缩（有损压缩）的目的。同时，以这M个系数可以重构原始信号X，不过一般而言得到的是X的一个逼近。
我们应该熟悉JPEG跟JPEG2000的区别吧，JPEG的核心算法是DCT，而后者是DWT，本质上，这两种处理方法都是将信号从一个域变换到另外一个域（把坐标系进行旋转，将信号投影到不同的基上），从而获得信号的稀疏表示，即用最少的系数来表示信号，不过DWT比DCT更加稀疏而已。信号不同，对应最稀疏表达的基也会不同，比如，对于一维信号可能小波基是最稀疏的，而对于图像而言，可能那些Curvelet和contourlet是最优的，对于有些信号，也有可能需要将几种基结合起来才是最优的。稀疏分解是找到信号的最稀疏最有效的表达。
信号在某种表示方式下的稀疏性，是压缩感知应用的理论基础，经典的稀疏化的方法有离散余弦变换（DCT）、傅里叶变换（FFT）、离散小波变换（DWT）等。
最近几年，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。 这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子。目前信号在冗余字典下的稀疏表示的研究集中在两个方面：一是如何构造一个适合某一类信号的冗余字典，二是如何设计快速有效的稀疏分解算法。目前常用的稀疏分解算法大致可分为匹配追踪（Matching Pursuit）和基追踪（Basis Pursuit）两大类。
2、信号的观测矩阵
下午某时，天气晴，我在某地，想念你。
