首页 > 代码库 > 压缩感知综合理解篇
压缩感知综合理解篇
进来看稀疏编码的问题，看的内容多了，跟压缩感知的知识有些混淆，好乱，偶然看了几篇博文，在这里澄清下他们之间的关系
实际上：压缩感知只是借用稀疏表示为工具，来实现信号重构，
压缩传感理论主要包括信号的稀疏表示、编码测量和重构算法等三个方面.信号的稀疏表示就是将信号投影到正交变换基时,可以将其看作原始信号的一种简洁表达.这是压缩传感的先验条件.在编码测量中,必须满足约束等距性条件,最后, 运用重构算法重构原始信号.:D
一、稀疏编码和压缩感知的对比
在压缩感知模型中： y=Ax+n （1）
x表示原始信号，A表示稀疏映射矩阵，n表示加性噪声，y表示压缩测量。在此模型中，如果原始信号x满足一定的稀疏特性时，通过稀疏映射矩阵A的作用，可以将其压缩到很小的向量空间里，即y的行数比x小得多，这也体现了稀疏理论的核心思想：将高维信号用低维信号来描述。
在稀疏表达模型里，我们用y表示原始信号，A表示字典，x表示原始信号在字典A下的稀疏表达，一般应用中，字典A是过完备的，即A的列数多余行数，这与压缩感知中的稀疏映射矩阵是相洽的，在不考虑噪声 的情况下: y=Ax （2）
将 x做自变量，可以看到这个方程未知数的个数多于方程个数，也即这个方程要么有无穷多个解（当增广矩阵[A,y]的秩=矩阵[A]的秩时），要么无解（当增广矩阵[A,y]的秩>矩阵[A]的秩时），我们当然是考虑有无穷多个解的情形。有无穷多个解哪个解是我们需要的呢？学者告诉我们应该找到最稀疏的那个解，也即中非零元素最少的那个解是我们需要的，也即优化下面一个问题： min J(x) s.t. y=Ax （4）
或者统一成一个表达式： argmin Power(||y-Ax||_2,2)+lambdaJ(x) (5)
前一项表示数据拟合项，后一项表示稀疏约束项，J(x)取x的L0范数，L0范数即是统计x中非零元素的个数，但是L0范数表示的函数是非凸的，我们不能保证得到最优解，但是在一些实际应用中，我们不需要得到最优解，比如在图像去噪应用中，我们就可以应用L0范数模型，虽然求得的x不一定是全局唯一最优的，但是仍然起到了去噪效果，并且效果达到了state-of-the-art，以以色列的Michael Elad为代表的学者用的是L0范数来建模的，如KSVD[1]和Double Sparsity模型[2]。或者我们退而求其次，考虑L1范数，虽然L1范数亦不能保证得到全局唯一的最优解，因为L1范数不是严格凸的，但是L1范数可以达到稀疏的效果，并且一般能够满足实际应用中的效果，如以法国的Julien Mairal,FrancisBach,Jean Ponce为代表的学者[3]就是以L1范数来建模的。这两个地方在稀疏表达方面的研究貌似是起到主导作用的，很多人都是根据他们的工作来进行扩展研究的。
从上面稀疏表达和压缩感知的模型中，可以看出它们的核心问题是相通的，即在压缩测量y或原始信号y已知的情况下，结合预先定义的感知矩阵A或者字典A，利用L0,L1范数模型（可以是它们的融合，甚至可以加上L2范数[3]），求解到原始的稀疏信号x或者稀疏表达x，但是在压缩感知中，感知矩阵A一般是事先定义好的，可以取成高斯随机矩阵，或者是只有0和1的稀疏矩阵（binary sparse matrix），如张智林老师在用BSBL_BO算法处理胎儿心电图信号时[4,5]用的就是后者，取得了很好的效果。但是在稀疏表达模型，比较主流的做法是通过学习的方法得到字典，这样的字典比预先定义的字典有更好的自适应性，这以思想应该可以借鉴到压缩感知的模型中。
从[4][5]两篇文章中可以看出，在考虑原始信号 的块内相关性的情况下，我们可以得到更高的压缩率，并且恢复的原始信号也更加真实、鲁棒，这在胎儿心电图信号和语音信号应用中得到了验证。在稀疏表达模型中，有些人一方面在考虑稀疏表达系数x的结构性，比如考虑张智林老师所展示的块内相关性或者块间相关性等等，另一方面很多人在考虑学习到的字典A的结构性，如文章[2]中就将字典A建模成了A=WD，其中D是一个稀疏矩阵，其每列有指定数目的非零元素，D通过学习得到， W为事先设定的矩阵，这样的话，D和x都是稀疏的，并且可以通过[2]中的算法统一求解得到。文章[3]讲述了根据特定任务构建特定字典的方法，这貌似在稀疏表达研究中是一个主流。
在张智林老师所提出的BSBL算法及其扩展中，原始信号x具有块结构，感知矩阵A的行数小于列数，这样可以将原始信号映射到一个更低维度的空间里，起到了采样的效果，采样率在一定条件下可以比奈奎斯特采样率低很多。在考虑原始信号x的块内元素相关性的情况下，通过实验可以证明，在信号恢复应用中达到了state-of-the-art的效果，也即在一个块内，各个元素之间一般不是独立的，如在图像中，一个像素一般会跟周围的几个像素有很大的关系，这也是MRF模型的假设基础。考虑这种相关性，应用贝叶斯模型进行建模，我们把每个块的相关性矩阵和均值矩阵给估计出来，最终恢复出原始信号，文章从分块个数已知和未知两个方面进行了分析。
[1]K-SVD:An Algorithm for Designing OvercompleteDictionaries for Sparse Representation.
[2]Double Sparsity:Learning Sparse Dictionaries forSparse Signal Approximation.
[3]Task-Driven Dictionary Learning.
[4]Extension of SBL Algorithms for the Recovery ofBlock Sparse Signals with Intra-Block Correlation.
[5]From Sparsity to Structrued Sparsity:BayesianPerspective(in Chinese).
二、压缩感知
简单地说，压缩感知理论指出：只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。
在该理论框架下，采样速率不再取决于信号的带宽，而在很大程度上取决于两个基本准则：稀疏性和非相关性，或者稀疏性和等距约束性。
压缩感知理论主要包括三部分：
（1）信号的稀疏表示；
（2）设计测量矩阵，要在降低维数的同时保证原始信号x的信息损失最小；
（3）设计信号恢复算法，利用M个观测值无失真地恢复出长度为N的原始信号。
理论依据：
（1）设长度为N的信号X在某个正交基Ψ上是K-稀疏的（即含有k个非零值）；
（2）如果能找到一个与Ψ不相关（不相干）的观测基Φ；
（3）用观测基Φ观测原信号得到长度M的一维测量值M个观测值Y，K<M<<N；
（4）那么就可以利用最优化方法从观测值Y中高概率恢复X。
数学表达：
设x为长度N的一维信号，稀疏度为k（即含有k个非零值），A为M×N的二维矩阵（M<N），y=Φx为长度M的一维测量值。压缩感知问题就是已知测量值y和测量矩阵Φ的基础上，求解欠定方程组y=Φx得到原信号x。Φ的每一行可以看作是一个传感器（Sensor），它与信号相乘，拾取（Acquisition）了信号的一部分信息。而这一部分信息足以代表原信号，并能找到一个算法来高概率恢复原信号。
一般的自然信号x本身并不是稀疏的，需要在某种稀疏基上进行稀疏表示，x=Ψs，Ψ为稀疏基矩阵，s为稀疏系数（s只有K个是非零值（K<<N）。
压缩感知方程为y=Φx=ΦΨs=Θs。
将原来的测量矩阵Φ变换为Θ=ΦΨ（称之为传感矩阵），解出s的逼近值s’，则原信号x’ = Ψs’。
1、信号的稀疏表示
信号的稀疏性简单理解为信号中非0元素数目较少，或者说大多数系数为0（或者绝对值较小）。
自然界存在的真实信号一般不是绝对稀疏的，而是在某个变换域下近似稀疏，即为可压缩信号。或者说从理论上讲任何信号都具有可压缩性，只要能找到其相应的稀疏表示空间，就可以有效地进行压缩采样。信号的稀疏性或可压缩性是压缩感知的重要前提和理论基础。
稀疏表示的意义：只有信号是K稀疏的（且K<M<<N），才有可能在观测M个观测值时，从K个较大的系数重建原始长度为N的信号。也就是当信号有稀疏展开时，可以丢掉小系数而不会失真。
我们知道，长度为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、信号的观测矩阵
观测矩阵（也称测量矩阵）MxN（M<<N）是用来对N维的原信号进行观测得到M维的观测向量Y，然后可以利用最优化方法从观测值Y中高概率重构X。也就是说原信号X投影到这个观测矩阵（观测基）上得到新的信号表示Y。
观测矩阵的设计目的是如何采样得到M个观测值，并保证从中能重构出长度为N的信号X或者稀疏基Ψ下等价的稀疏系数向量。
为了保证能够从观测值准确重构信号，其需要满足一定的限制：观测基矩阵与稀疏基矩阵的乘积满足RIP性质（有限等距性质）。这个性质保证了观测矩阵不会把两个不同的K稀疏信号映射到同一个集合中（保证原空间到稀疏空间的一一映射关系），这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。
在CS编码测量模型中并不是直接测量稀疏信号X本身， 而是将信号投影到一组测量矩阵Φ上而得到测量值y。即，用一个与变换矩阵不相关的MxN（M<<N）测量矩阵Φ对信号x进行线性投影，得到线性测量值y： y=Φx ;
测量值y是一个M维向量，这样使测量对象从N维降为M维。测量矩阵的设计要求信号从x转换为y的过程中，所测量到的K个测量值不会破坏原始信号的信息，以保证信号可以精确重构。
由于信号x是是可稀疏表示的: x=Ψs，上式可以表示为下式：
y=Φx=ΦΨs=Θs
其中Φ是一个MxN矩阵。上式中，方程的个数远小于未知数的个数，方程无确定解，无法重构信号。但是，由于信号是K稀疏，若上式中的Φ满足有限等距性质(Restricted Isometry Property，简称RIP)，则K个系数就能够从M个测量值准确重构（得到一个最优解）。RIP性质的等价条件是测量矩阵Φ和稀疏基Ψ不相关。
如果稀疏基和观测基不相关，则很大程度上保证了RIP性。CandeS和Tao等证明:独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。则一般用随机高斯矩阵作为观测矩阵。目前常用的测量矩阵还有随机贝努利矩阵、部分正交矩阵、托普利兹和循环矩阵和稀疏随机矩阵等，这里不一一列举了。
3、信号的重构算法
当矩阵Φ满足RIP准则时。压缩感知理论能够通过对上式的逆问题先求解稀疏系数s，然后将稀疏度为K的信号x从M维的测量投影值y中正确地恢复出来。解码的最直接方法是通过l0范数（0-范数，也就是向量yˆ中非零元素的个数）下求解的最优化问题：
从而得到稀疏系数s的估计s’。则原信号x’ = Ψs’。由于上式的求解是个NP难问题（在多项式时间内难以求解，甚至无法验证解的可靠性）。L1最小范数下在一定条件下和L0最小范数具有等价性，可得到相同的解。那么上式转化为L1最小范数下的最优化问题：
L1范数最小化是通过用L1范数来近似0范数，取1而不取1/2,2/3或者其他值，是因为1范数最小化是凸优化问题，可以将求解过程转化成有一个线性规划问题。L1最小范数下最优化问题又称为基追踪(BP)，其常用实现算法有：内点法和梯度投影法。内点法速度慢，但得到的结果十分准确：而梯度投影法速度快，但没有内点法得到的结果准确 。
目前，压缩感知的重构算法主要分为两大类：
（1）贪婪算法，它是通过选择合适的原子并经过一系列的逐步递增的方法实现信号矢量的逼近，此类算法主要包括匹配跟踪算法、正交匹配追踪算法、补空间匹配追踪算法等。
（2）凸优化算法，它是把0范数放宽到1范数通过线性规划求解的，此类算法主要包括梯度投影法、基追踪法、最小角度回归法等。
凸优化算法比贪婪算法所求的解更加精确，但是需要更高的计算复杂度。
从数学上来说，CS就是在一定的条件下求解欠定(不适定)方程，条件包括x要是稀疏的，测量矩阵要满足RIP条件，那么欠定(不适定)方程就会以很大的概率有唯一解。
参考转自：http://blog.csdn.net/caikehe/article/details/8510971
http://blog.csdn.net/zouxy09/article/details/8118329
压缩感知综合理解篇