转&压缩感知存在问题
很多人对于这项以稀疏表示理论为基础的技术还不了解。大约5，6年前，Candies，Tao，
Donoho几个人提出一种理论：如果一个信号可以用一个基（或是冗余基）稀疏表示，则可以用一个和这个基相关性很差的观测矩阵将信号随机投影到低维空间中，即压缩采样。通过凸优化的方法可以以很高的概率精确重构这个信号。
&这项技术现在火的不行。各个国家各个领域的各种人都在研究它或者想着把它用到某个工程领域中。像是rice大学DSP组的单像素照相机；图像信号的压缩；Faust用它做过心电信号采集器；据说清华通信专业有人用它做导频信号的压缩；到了上交还知道了在WSN中好像也有人在用。。。。。。
&但是，它真的这么好吗？真的这么有前途吗？~呵呵。
&&&运算复杂度高，重构算法速度慢是最大的瓶颈。目前大家多是用l1范数的最优化方法对重构信号进行求解（传说中的BP算法）。虽然也有TV和MARX这些方法对压缩后的信号进行重构，但是这些方法都是需要迭代的，这就造成了很大的运算开销。（什么Newton法呀，EM呀，跑起来都巨慢呀。。。。。。）
&&&迭代的另一个缺点是造成算法过程不可控，参数敏感。先说说过程不可控，迭代过程中往往涉及矩阵求逆，或是参数递归。而对于奇异或是近似奇异的矩阵求逆往往会得到病态解，而递归更是有可能将参数推到计算机的运算范围之外。再说说参数敏感，大家都知道，迭代的次数是由参数（残差容限，迭代上限等等）决定的，但是这些参数的取值往往是经验的，或是只适用于某一类信号，很难做到普适。
&至于观测矩阵和基的相关性无法保证这种顽疾，目前好像也没有非常有效的解决方法。尤其当基是单位矩阵时（即直接对空域信号进行压缩感知），即使观测矩阵时Gaussian随机阵也是无法使两者不相关的。
&上面这些都是很明显的问题，还有一些比较隐蔽的问题。一是数据扩张。虽然经过压缩感知信号被投影到低维空间，从数学角度上看数据是压缩了，但是数据的动态范围往往会增加（至少相关的实验结果是这样，有异议者欢迎反驳），原本uint8型的数据用gaussian阵投影须转成double型，用Bernoulli阵投影须转成uint16型。从计算机的角度看，数据量往往还有增加，所以压缩感知要真的实现压缩还是需要时日的。
&另外一点就是解的敏感性。即使重构信号本身不是病态解，这个解对于噪声，尤其是量化噪声是很敏感的。上述的数据扩张问题可能有人会想用量化的方法来解决。遗憾的是，有人这么做了，在量化参数为20的时候得到的解在视觉上就有很明显的量化噪声了。
&。。。。。。
&问题还有很多，这对于搞科研的人来说是“甜蜜的痛苦”吧。所以压缩感知在今后的3，5年内应该还会是signal领域的研究热点。上述的任何一个问题都是很好的研究课题。很多人现在也在为此努力，主要在算法加速方面。
&如果你觉得它还有其他问题，欢迎交流。如果你有解决上述问题的思路，欢迎交流。&
上篇说到了它的一些问题，这次就针对其中最重要的一点——观测矩阵，进行分析。众所周知，虽然仿真实验，以及实际中的后端恢复，观测矩阵都是用软件生成的，或是预先存储在RAM中。但实际上只有在信号采集的前端用硬件实现信号的压缩采集才有意义。也就是说观测矩阵是用硬件实现的。这样做的好处很明显——省钱+高速！以图像采集系统为例，如果我们采集N*N的图像时只需要远小于N的平方个传感器，那么就可以节省传感器的成本。因为数据量减少，传输所需的带宽也能被节省，传输速率也会更高。从模数转化的角度看，压缩感知提供了一种以低于Nyquist采样率的速率采样而无失真恢复信号的方法，这对于高频信号的采集可以说是革命——高频信号处理可以从采样速率的瓶颈中解放了，ADC的成本也会跟着下降。
说了这么多，到底怎么实现呢？对于1维模拟信号，目前我所知道的是由伪随机序列发生器和积分器组成的采样系统。模拟信号通过积分器后被伪随机序列采样，采得样本可以看作部分积分的结果。根据DCC2009的论文，Ti公司已经做出了名为“Xampling”的样板，对2.4GHz的信号使用200MHz速率采样并恢复。但从效果上看，还有待改进。
对于2维信号，通常是图像信号，情况变得稍稍有些复杂。研究的方向出现了分叉——一拨人天天想着怎么用硬件实现CS，而另伙人比较懒，他们想把压缩感知用在其他问题上，例如：去噪，超分辨率，去模糊，去抖等等。这类问题的共同点就是可以看作欠定方程组的求解问题，一般采用threshold
iteration来进行求解。
在硬件实现上，Rice大学做一个单像素照相机，利用反射角度可调的镜面阵列完成光学图像的矩阵运算，原理上和单发相机是一样的，只是所用的镜面不是平面的了。这种做法原理上是可行的，但是也许是设备精度问题，或是压缩比太大，恢复出的图像效果严重模糊，无法使用。而另一种则相对好实现，即CCD平动阵列——说是阵列，但实际上最少一行CCD就够了。原理上嘛~大家可以想一想指纹采集系统，这就是使用一行传感器采集一张图像的典型例子，只不过这是通过你手指的规则运动完成的。现实生活中这样的例子有很多，结合压缩感知的话，这时CCD的曝光时间会变成离散的（这样采样就减少了），顺序扫描过程也变成了部分积分的过程。对于采集设备和对象之间存在规则运动且采集传输速率要求很高的问题，这样做是很有必要的。
至于第二类应用方法，这里我只对超分辨率做一下说明——实际上当我们用数码相机对自然图像进行采集时，观测矩阵就已经有了——一个结构化的下采样矩阵。胶片相机的成像分辨率一般为6000万像素，如果以此作为自然图像，数码相机在分辨率上还是有差距的。用下采样矩阵得到的信号可以用压缩感知恢复吗？我目前的答案是可以被估计，但是不能被精确恢复。主要是因为此时的观测矩阵和字典之间的相关性一般还是比较大的，它们的乘积不满足被约束的各向异性（矩阵的奇异值近似服从0-1分布）。这样的问题在用CS解决去模糊，去抖时，相信也是存在的。对于这类问题，观测矩阵已经给定，寻找合适的字典就是这类问题的关键了。目前比较火的是wavelet基，尤其是curvelet基，对与图像的纹理部分的恢复还是很有效果的。但是在实验中，我也发现curvelet虽然对于细节，尤其是线型细节有着很好的描述，但是整体上的PSNR是不如传统的db小波的——恢复出的图像振铃效果较明显，感觉很有“油画”风格——像是用油彩沿边缘勾勒过一样~
&如同之前指出的，信号的可稀疏性和观测矩阵也字典的非相关性是压缩感知可行的两大必要条件。但是实际应用中，这两个条件相当苛刻，很难满足。一方面对于一些非平稳的随机信号，找到可以稀疏表示这种充满高频分量的怪物的字典是很困难的。另一方面，如何在模拟信号阶段进行压缩采样，即观测矩阵的物理实现是很困难的。
&就在所有人都在想着如何实现这两个约束时，Candies想的是可不可以放松这两个约束。于是，矩阵填补（matrix
completion）横空出世。
&同压缩感知一样，矩阵填补也是一个类似的反问题——能否预测矩阵中缺失的元素。对于这个问题，Candies给出的答案是：对一个N*N的矩阵进行随机的下采样，得到C*NlogN个样本并保证每一行每一列至少保留一个元素。如果原始矩阵时低秩的，那么可以通过求解矩阵的奇异值最小化问题（又称核范数规划）精确恢复原始矩阵。发现了吧？这个结论里没有稀疏性，没有字典，取而代之的是低秩这个条件——换句话说，我们不需要再去寻找可以稀疏表示信号的字典了，只需要知道信号组成的矩阵时低秩的即可。另外一个好处就是，观测矩阵的约束条件也得到了放松，不再需要去考虑和字典的非相关性——因为已经没有字典了。单纯的随机采样就足以满足条件，模拟端的积分器（电信号处理用），运动或反射模块（光信号处理用）都可以下岗了——世界从此和谐了。
&但这并不是说压缩感知可以光荣退役了。实际上目前矩阵填补理论主要用在信息检索领域，用于估计网络用户对于某些信息的反馈。因为这些信息组成的矩阵被认为是低秩的。现实世界中，很多自然信号仍然是满秩或近似满秩的。对于这类信号的压缩采样仍然是压缩感知的应用领域。下面就谈谈我对其应用的理解。
&在笔者看来，适合用压缩感知处理的信号应该是“窄带”高频的。之所以对窄带用引号是因为我所说的窄带，其实是可稀疏性的一种保证，它的本质是信号在频域是紧支撑的。也许有人会反驳我，说根据海森伯格测不准原理，即使信号在频域上频谱很宽，信号仍可以在时域或空域稀疏——那要说，这种信号往往在空域或者时域上用简单的下采样就能得到（即低秩信号）。另一个条件就是高频，即物理条件无法胜任这么高的采样速率要求，这时方能体现出压缩感知的优势，即低频采样，精确恢复。这也是为什么压缩感知最先在MRI图像重建上得到应用，因为那是一个要求采样速率非常高，而且越高越好的领域。在之前的第一篇小结中说过清华有人用压缩感知采集导频信号，想想导频信号的特点，不就是窄带高频吗？
&最后作者给出建议：航拍和MIMO是压缩感知的有前途的应用领域。有兴趣的看官可以多交流讨论。
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
压缩感知理论及其研究进展
下载积分：3000
内容提示：压缩感知理论及其研究进展
文档格式：PDF|
浏览次数：91|
上传日期： 22:30:21|
文档星级：
全文阅读已结束，如果下载本文需要使用
 3000 积分
下载此文档
该用户还上传了这些文档
压缩感知理论及其研究进展
官方公共微信进来看稀疏编码的问题，看的内容多了，跟压缩感知的知识有些混淆，好乱，偶然看了几篇博文，在这里澄清下他们之间的关系
压缩理论主要包括信号的稀疏表示、编码测量和重构算法等三个方面.信号的稀疏表示就是将信号到正交变换基时,可以将其看作原始信号的一种简洁表达.这是压缩传感的先验条件.在编码测量中,必须满足约束等距性条件,最后, 运用重构算法重构原始信号.: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在某个正交基&P上是K-稀疏的（即含有k个非零值）；
（2）如果能找到一个与&P不相关（不相干）的观测基&P；
（3）用观测基&P观测原信号得到长度M的一维测量值M个观测值Y，K&M&&N；
（4）那么就可以利用最优化方法从观测值Y中高概率恢复X。
数学表达：
& & & &设x为长度N的一维信号，稀疏度为k（即含有k个非零值），A为M&N的二维矩阵（M&N），y=&Px为长度M的一维测量值。压缩感知问题就是已知测量值y和测量矩阵&P的基础上，求解欠定方程组y=&Px得到原信号x。&P的每一行可以看作是一个传感器（Sensor），它与信号相乘，拾取（Acquisition）了信号的一部分信息。而这一部分信息足以代表原信号，并能找到一个算法来高概率恢复原信号。
& & & & 一般的自然信号x本身并不是稀疏的，需要在某种稀疏基上进行稀疏表示，x=&Ps，&P为稀疏基矩阵，s为稀疏系数（s只有K个是非零值（K&&N）。
& & & 压缩感知方程为y=&Px=&P&Ps=&Ts。
& & & &将原来的测量矩阵&P变换为&T=&P&P（称之为传感矩阵），解出s的逼近值s&，则原信号x& = &Ps&。
1、信号的稀疏表示
&&&&&&信号的稀疏性简单理解为信号中非0元素数目较少，或者说大多数系数为0（或者绝对值较小）。
自然界存在的真实信号一般不是绝对稀疏的，而是在某个变换域下近似稀疏，即为可压缩信号。或者说从理论上讲任何信号都具有可压缩性，只要能找到其相应的稀疏表示空间，就可以有效地进行压缩采样。信号的稀疏性或可压缩性是压缩感知的重要前提和理论基础。
& & & &稀疏表示的意义：只有信号是K稀疏的（且K&M&&N），才有可能在观测M个观测值时，从K个较大的系数重建原始长度为N的信号。也就是当信号有稀疏展开时，可以丢掉小系数而不会失真。
& & & 我们知道，长度为N的信号X可以用一组基&PT=[&P1,&, &PM]的线性组合来表示：
& & & &x=&Ps，&P为稀疏基NxN矩阵，s为稀疏系数（N维向量），当信号X在某个基&P上仅有 K&&N个非零系数或远大于零的系数s时，称&P为信号X的稀疏基。我们需要做的就是合理地选择稀疏基，使得信号的稀疏系数个数尽可能少。
& & & &再啰嗦点的话：如果长度为N的信号X，在变换域&P中只有K个系数不为零（或者明显大于其他系数），且K&&N，那么可以认为信号X在&P域中是稀疏的并可称为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或者稀疏基&P下等价的稀疏系数向量。
& & & &为了保证能够从观测值准确重构信号，其需要满足一定的限制：观测基矩阵与稀疏基矩阵的乘积满足RIP性质（有限等距性质）。这个性质保证了观测矩阵不会把两个不同的K稀疏信号映射到同一个集合中（保证原空间到稀疏空间的一一映射关系），这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。
在CS编码测量模型中并不是直接测量稀疏信号X本身， 而是将信号投影到一组测量矩阵&P上而得到测量值y。即，用一个与变换矩阵不相关的MxN（M&&N）测量矩阵&P对信号x进行线性投影，得到线性测量值y： y=&P
& & & &测量值y是一个M维向量，这样使测量对象从N维降为M维。测量矩阵的设计要求信号从x转换为y的过程中，所测量到的K个测量值不会破坏原始信号的信息，以保证信号可以精确重构。
& & & &由于信号x是是可稀疏表示的: x=&Ps，上式可以表示为下式：
&&&y=&Px=&P&Ps=&Ts
& & & &其中&P是一个MxN矩阵。上式中，方程的个数远小于未知数的个数，方程无确定解，无法重构信号。但是，由于信号是K稀疏，若上式中的&P满足有限等距性质(Restricted Isometry Property，简称RIP)，则K个系数就能够从M个测量值准确重构（得到一个最优解）。RIP性质的等价条件是测量矩阵&P和稀疏基&P不相关。
& & & & 如果稀疏基和观测基不相关，则很大程度上保证了RIP性。CandeS和Tao等证明:独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。则一般用随机高斯矩阵作为观测矩阵。目前常用的测量矩阵还有随机贝努利矩阵、部分正交矩阵、托普利兹和循环矩阵和稀疏随机矩阵等，这里不一一列举了。
3、信号的重构算法
& & & 当矩阵&P满足RIP准则时。压缩感知理论能够通过对上式的逆问题先求解稀疏系数s，然后将稀疏度为K的信号x从M维的测量投影值y中正确地恢复出来。解码的最直接方法是通过l0范数（0-范数，也就是向量y&中非零元素的个数）下求解的最优化问题：
& & & 从而得到稀疏系数s的估计s&。则原信号x& = &Ps&。由于上式的求解是个NP难问题（在多项式时间内难以求解，甚至无法验证解的可靠性）。L1最小范数下在一定条件下和L0最小范数具有等价性，可得到相同的解。那么上式转化为L1最小范数下的最优化问题：
& & & &L1范数最小化是通过用L1范数来近似0范数，取1而不取1/2,2/3或者其他值，是因为1范数最小化是凸优化问题，可以将求解过程转化成有一个线性规划问题。L1最小范数下最优化问题又称为基追踪(BP)，其常用实现算法有：内点法和梯度投影法。内点法速度慢，但得到的结果十分准确：而梯度投影法速度快，但没有内点法得到的结果准确 。
& & & &目前，压缩感知的重构算法主要分为两大类：
（1）贪婪算法，它是通过选择合适的原子并经过一系列的逐步递增的方法实现信号矢量的逼近，此类算法主要包括匹配跟踪算法、正交匹配追踪算法、补空间匹配追踪算法等。
（2）凸优化算法，它是把0范数放宽到1范数通过线性规划求解的，此类算法主要包括梯度投影法、基追踪法、最小角度回归法等。
& & & & 凸优化算法比贪婪算法所求的解更加精确，但是需要更高的计算复杂度。
& & & &从数学上来说，CS就是在一定的条件下求解欠定(不适定)方程，条件包括x要是稀疏的，测量矩阵要满足RIP条件，那么欠定(不适定)方程就会以很大的概率有唯一解。
参考转自：
阅读(...) 评论()如何理解压缩感知(compressive sensing)？ - 知乎598被浏览32499分享邀请回答1311 条评论分享收藏感谢收起浅谈压缩感知（十六）：感知矩阵之RIP - AndyJee - 博客园
随笔 - 325, 文章 - 0, 评论 - 24, 引用 - 0
在压缩感知中，总是看到"矩阵满足RIP"之类的字眼，没错，这是一个压缩感知绕不开的术语，有限等距性质（Restricted Isometry Property, RIP）。
注意：RIP性质针对的同样是感知矩阵而非测量矩阵。
0、相关概念与符号
1、RIP定义
（RIP）矩阵满足2K阶RIP保证了能够把任意一个K稀疏信号&K映射为唯一的y，也就是说要想通过压缩观测y恢复K稀疏信号&K，必须保证传感矩阵满足2K阶RIP，满足2K阶RIP的矩阵任意2K列线性无关。
边界解释：
上述定义中不等式边界关于1对称，其实这只是表示的方便而已，实际中可以考虑任意边界值。
2、RIP理解
理解1：能量说
向量的2范数的平方就是信号的能量，换成常见的公式：
RIP不等式：
这里的实际上是&，即输出信号的能量，&即输入信号的能量（稀疏变换x=&P&为正交变换，而正交变换保持能量不变，即信号理论中的Parseval定理）。
RIP其实可以看成刻画一个矩阵和标准正交阵的相似程度。其对于向量做变换后的 L2 能量（范数平方）相较于原向量的能量的变化不超过RIP。RIP对于Stability 的分析非常有效。RIP 是由Candes 和Tao 提出来的，可以看他们的提出这个概念的文章: Decoding by LinearProgramming。
其实取极限当&=0时（RIP要求0&&&1），RIP的不等式实际上表示的是观测所得向量y的能量等于信号x的能量，在线性代数中所讲的正交变换也具有这种性质，也称为等距变换（把信号将为二维或三维时2范数的平方可形象的理解为到原点的距离），当然这里的变换因为传感矩阵A不可能是正交矩阵（不是方阵），但当极限&=0时也能保持能量相等（也可以称为等距吧），而RIP要求0&&&1，所以不可能等距，所以就称为有限等距性质吧。
理解2：唯一映射说
在前一篇介绍spark常数的时候，已经提到了唯一映射说这一点，可以了解一下：
RIP性质（有限等距性质）保证了感知矩阵不会把两个不同的K稀疏信号映射到同一个集合中（保证原空间到稀疏空间的一一映射关系），要求从感知矩阵中抽取的每2K个列向量构成的矩阵是非奇异的。
当&2s&1时可以保证零范数问题有唯一的稀疏解，而当&2s&sqrt(2)-1时则可以保证零范数和1范数等价（零范数求解为NP-hard问题，在此前提下将其转化为1范数求最优化问题，这时是个凸优化问题）
3、RIP补充
上面我们谈到的都是感知矩阵，而实际中我们常常使用的是测量矩阵，那么怎么样才能让测量矩阵满足RIP要求呢？
前面解释中的能量说提到"RIP其实可以看成刻画一个矩阵和标准正交阵的相似程度"，如。
那么对于测量矩阵而言，需要满足的性质就是尽量保证其基向量与稀疏表示的基不相关，这个对于RIP来说比较通俗的理解，在实际中，有些矩阵如高斯随机矩阵、二值随机矩阵、局部傅里叶矩阵、局部哈达玛矩阵等都能够以很大的概率满足RIP。
关于矩阵中任意2K列都不相关的解释：
如果矩阵有2K列线性相关，则对于某一个2K稀疏的信号必然会有A&2K=0，又因为一个2K稀疏的信号可以写成两个K稀疏的信号相减（把2K稀疏信号的2K个非零项分成两部分，每部分分别包含K个非零项，其余部分填零长度与原2K稀疏信号保持不变，即得到了两个K稀疏信号，其中的一个K稀疏信号中的K个非零项乘负一，另一部分减这一部分必然等于2K稀疏信号），因此有A(&K1－&K2)=0，即A&K1=A&K2，也就是说对于两个不同的K稀疏信号&K1和&K2，压缩观测后得到了同一个y，即不能保证唯一映射，所以矩阵不能有2K列线性相关，否则将不能保证唯一映射。
4、参考文章