压缩感知的延伸.docx

《压缩感知的延伸.docx》由会员分享，可在线阅读，更多相关《压缩感知的延伸.docx（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、压缩感知的延长Yaakov Tsaig David L. Donoho二零零四年十月二十日修改于二零零五年四月二十六日摘要：我们争论了已提出的压缩感知(CS)的概念及相关工作，18, 3,4o这一概 念提出了一种信号或图像，虽然未知，但可通过已知转换压缩得到(例如，小波 或傅立叶)，少数的测量值会对它产生影响，但数据点的额定数的影响较大，然 而这种技术目前还未被精确重建。样本具有非适应性，并测量变换系数的“随机”线性组合。通过解决与测量数据全都的变换系数和得到的最小可能 11范数来得到近似重建。我们是在有利状况下提出最初的“概念验证”例子的，这时绝大多数的变换 系数为零。我们为Ip稀疏设置而连

2、续做了一系列的数值试验，试验中对象的全 部系数非零但系数在Ip范围内,p的取值范围为pe(0J)o重建误差遵循不等式 且符合理论，并且是良性常量。我们报告了几个等值“随机”线性组合的可行族，其中包括随机球形,随机的 迹象,部分傅里叶和部分阿达玛。下一步我们会争论如何将这些想法用到光谱和图像处理的模型问题中，并且 由合成实例可得，CS中的重建往往是视觉“噪音”。为了抑制这种噪声，我们通 过平移不变的后期处理来去噪，并发觉外观得到很大改善。我们也争论到多尺度调配压缩感知，其中进行了各种规模的分别并且CS分 别适用于每一个尺度；这比文字调配CS方法论的质量重建更好。该结果表明，在进行有利设置的适当调

3、配时，CS架构比传统的采样的保存更 有意义，并有基本思路的很多有用扩展。关键词和短语：基追踪。线性方程组欠定系统。线性规划。随机矩阵理论。致谢：来自 NSFDMS 00-77261,01-40698 (FRG)和 ONR-MURI 的部分支持。感谢迈克 尔桑德斯的优化建议，感谢Emmanuel Candies为自己的相关工作与J. Romberg 和工Tao进行争论。Raphy Coifman对常量的(L2)问题的寻根究底激发了这 份报告。1简介在现代多媒体饱和的世界里，“每个人都知道，全部人类可理解的数据是高度压 缩的。在采用这一事实，主要解决方法是先进行数据的采样，然后使用各种压缩 方案消

4、退冗余。这便产生了以下问题：为什么要用传统的方式来取样然后再压缩 数据呢？莫非不能直接获得一个压缩表示吗？明显，假如这是可能的，在不同领 域内的蕴涵会更快的从数据采集中扩展出来，这会提高采样率并降低通信负担。 最近有几篇论文口8, 3, 13, 4指出，不同假设下，直接获得压缩表示的的形式 是有可能的。本文将通过一系列压缩传感方案的有效性实例争论来验证这一猜想。1.1方法我们从13中采纳的语言和符号;这种方法比较抽象，但在很多潜在的应图6：重构误差与信号长度m,而固定数的测量结果为n =200： (l)p=0.5, (b) p=lo实线曲线为在20个伪随机复制误差。虚线曲线为准范围(3.2),

5、使用的 常数为表1中的Cp。一个裁判让我们比较范围(3.2)和观测到的10稀疏信号的信号特性， 这在上一节中争论过。对于长度为m且k非零，振幅A相同的信号来说，Ip范 数为Akl/p。这个值可以用在准范围(3.2)中，也可以用在表1估量(7p上, 对比图1中的实证重构误差。图7是p的好几个值。明显，10稀疏信号可以产 生任何范围(3.2)的更好的误差特性。4.CS矩阵中的不同集合在迄今所示的例子中，我们已经构建了如13所描述的匀称球形集合的CS 矩阵。其他CS矩阵建构的存在的可能行有很多。更为具体地解释，我们定义了 随机矩阵的四个具体集合 随机符号集合。这里ij有1/JN项的符号，全部的符号都

6、是独立选择且 符号有可能相等。 匀称的球形集合。数列为球行Sn-1上的随机匀称iid。 偏傅立叶集合。我们随便选出mXm傅立叶矩阵的n行，得到一个n行m 列的偏傅立叶矩阵。 偏阿达玛集合。我们随便选出mXm阿达玛矩阵的n行，得到一个n行m 列的偏Hadamard矩阵。(为此，我们只争论m = 2k)选择的灵感来自以下早期成果： 卡申21的成果，以及Garnaev和Gluskin17的成果，他们对n宽 Kolmogorov对偶问题随机符号集合，进行了隐式考虑。由于GeFfand和n宽 Kolmogorov (25)间的对偶关系，以及n宽GeFfand和压缩感测间的关系13, 26,这些矩阵在p=

7、l均适用。 多诺霍11, 12, 13争论了匀称的球形合奏。 Candes, Romberg, and Tao 3最近已经对展现随机偏傅立叶矩阵一些好玩 的特性上产生了极大的爱好，同时也解释了压缩感测4的可能用途。 偏Hadamard矩阵已知在某些特殊状况下可生成近似最优子空间，这些子空间与确定的n宽Kolmogorov的相关问题有关，他们都在相对于lm范数的 正八面体bl和m中；相见Pinkus的书25。(b)k= 100050100 1so 2002S03003504004S0500图7：重构误差与测量数n,对于固定的信号长度为m=1024和（a） k=50的非 零，（b） k =100的

8、非零。虚线：观测误差。实线：误差范围（3.2）o我们认为在偏傅立叶偏Hadamard矩阵的直接直接关系是很多好玩的实际应 用，例如在傅立叶变换图像和阿达玛转换光谱中。此外，由于矩阵底层转换的特 殊结构，这种矩阵的使用大大扩展了 CS方案的适用性，其数据容量大，可储存 2-D或3-D的数据。在图8中，我们比较准范围（3.2）,和刚才定义的不同矩阵集合中的实际误 差。这样，我们依据上一节的步骤。具体地，每一个集合中，我们争论定义在第 3节的对象，即一个m向量，其第k个最大振幅系数| 9 | （k）,且遵循（3.1）。 图4 （a）中一个典例便是这种状况。设置p=3/4, m=2048,并争论试验族

9、中的 n和不容测量数，对于每个n,我们应用CS架构，来测量12重建误差。在每个 （n,m,p）三元组中重复此试验20次，并且纪录最大误差。图8为误差与上述争 论的四个不同集合的样品n。我们展现了误差准范围（3.2）。此处的常数Cp是 从表1中得来的，即C3/4 % 0.09o图8提示了几点意见。首先，不同集合的模拟结果在（1.2）特性误差理论形 式的协定都是定性的。此外，关系（3.2）给出了实践观看中真是特性一个相当 不错的描述。或许最重要的是，我们争论不同的集合表现出了相像的行为。这表明，全部这些集合在实践中同样很好。在本文的其他部分，我们连续使用球形匀 称集合。图8：误差与测量数n, 合（

10、c）偏阿达玛集合;p =3/4, m =2048： （a）匀称球形集合（b）随机符号集 （d）偏分傅立叶集合。5降噪CS结果当对象采样不足，CS重建通常是嘈杂的。我们争论Wavelab软件包1中的 对象凸粒，渲染值为m =2048。如图9 （a）组所示，对象是平滑凸粒的叠加。（b） 组示为在每个尺度四周凸粒位置的大系数，并且（c）组所示为小波系数的对数 标度的降低重排。该表的线性外观是一种基律特性。我们采纳的CS架构，像 平常一样，是从一个匀称的球形分布中得来的，且,为Daubechies，symmlet8 ”过 滤器中的正交小波基。图10 （a）组所示为重建结果，其中n的测量结果为n =25

11、6 的。（b）组的结果为n = 512。明显两种结果都很“嘈杂”，但是可以理解，“更 嘈杂”的结果采样率较低。事实上，图3和图10的结果表明，在测量数削减时（即使数据在这些例子 并不嘈杂）“噪音”有时会消失。为了减轻这种现象，我们认为之前的试验案例， 即Blocks和Bumps,以及应用的重建“噪音”信号的平移不变小波去噪6。结 果示于图3和（c）组、（b）组以及图10的（d）组中。至少在视觉上，改进是 很大的。图10： (a) n = 256和(c) n = 512下的凸粒CS重建测量值。(b)、(d)中平移不变去噪。6噪声感知重建到目前为止，我们还没不能测量噪声，数字化的错误等。也就是说，

12、我们假 设原始测量值y的底层对象呈现完善观测线性组合-即便是在这种状况下，重建 也会很嘈杂，但不是由于系统中的任何“噪音”。现在我们状况实际上数据也很 嘈杂。我们留意到的理论目前是可以容纳少量噪声的，这是由13中的11稳定性得 出的。为更深化争论，与其假设Y=O)WTX,不如测量YN=O)WTX + Z的值, 其中z遵循z2 0,定义最优问题为(Ll,g) min /x/ 1 subject to yn-甲Tx2 W 8.这可以写成一个线性约束凸二次程序，并且它是有用的解决方法。在5中，在 nvm时,可以用胜利使用BPDN,或者当n = 8192 and m = 262144时。我们建 议处理

13、噪声数据可简洁测量yn=中Tx+噪声，然后在适当的噪声容限o 下，使用(Ll,)用。(裁判要求我们阐述了这个建议的理论支持。我们争论的10, 12的影响， 提出 Jean-Jacques Fuchs 和 Joel Tropp 16, 28的成果与之相关。10, 12中的 结果表明白对(LI, e )解决方案稳定重建的期望。假设我们观看到 y = OTT x0 + z(6.1)其中z是一个任意的干扰。在X0表示的充分稀疏下表明，假如 z2, (L1, e )的稀疏代表为稳定反演：对于和n有关的常数C, m和X0的稀疏性， x1-x02 W C/z/2.这激发压10稀疏缩传感对象的(L1, )采用

14、。那么LP稀疏怎么样呢？我们 留意到，对于一个系数为中TX6LP的对象，其最好的N末端靠近XN遵循 xN-x2 W Cp 中Txp-Nl/2l/p,N 0, (6.2)其中CP0,为通用常数。为应用该通用常数，假设我们发觉Y=中TX+Z0其中，TXeLP,我们可将其改写为y=WTxN + zO + zl。 Y=中TXN+Z0+Z1 其中 Zl = 6 WT (X-XN)。让 1 = 212(这由(6.2) 掌握)和0=z02,我们得到的模型(6.1)得到的实例中Z = ZO + Z1且 z 2W 0+ 1。更近期的工作31,34中也支持这种方法的稳定性;详情见9.4节。) (L1, )的性能可

15、知，我们的得出概念验证的结果。将测试信号块和凸粒， 分别示于图2和9中，并给其加入零均值白高斯噪声。噪声被重新调整，使得特 定噪声水平为z2=0.2。我们对嘈杂小波扩展使用了降噪(CSDN)压缩传感 方案。20(a) Nosy Sgna(b) Nosy wavelet ooecienls图11：块CSDN重建中，m= 2048, n =512信号和重建示于左侧数据中，与之相 应的小波扩展数据在右侧。为进行比较，我们还尝试了 CS重建正则图。结果在图11和12中。我们使用的 信号长度为m =2048,并尝试重建的信号长度为n =512。实际上，用CSDN实现 的重建了远远优于在这两种状况下的CS

16、重建。裁判已经说过（并且我们同意），为应用这种方法，重要的是要知道的噪声 水平，使得可被适当地指定。另一个裁判说（我们也同意），为了一些压缩目的，测量值y将被量化，在 争论过程中诱导量化噪声并提示使用的CSDN。幸运的是，在该设置中的噪声水 平是已知的。7双性别混合CS参考文献13中的光谱模型和成像问题，可从理论的角度来争论。目前本文 中的的CS部署方式是不同的-尤其是，它没有提出CS独自“承载全部负载”。 在该部署中，CS只能测试精度性能良好的信号，而一般的线性测量和重建被用 于获得信号的大尺度特性。更具体地说，该提案如下;我们的想法只适用于一维。扩展X0对象中的波基kk其中，jo具有特定的

17、大尺度，jl是最好的尺度，与0, k为大尺度阳性小波，且 力j，k为小尺度阴性小波。令a =（aj,k : jO W j W jl,0 W k v 2j）表示该组重全部的小波系数，并让B = (pj09k : 0 k2j0)表示阳性系数。现在争论一种 可用于两性a和6的方案。对于阳性大尺度系数来说，我们仅仅实行了直接测量 B 二(pjO,k,xO:0 k 2j0).图12：凸粒CSDN重建，m =2048, n =512。信号和重建示于左侧数据中，与之 相应的小波扩展数据在右侧。对于阴性小尺度系数，我们应用CS方案。令m = 2jl - 2j0,让2jlxm的矩阵中 的数列中，向量力j, K是

18、按某些标准挨次排列的。从mCS矩阵中取出一个n, 并定义日=甲T。这样一来，某种意义上说，数列己为数列中的“嘈杂”线性 组合。现在使N的测量值为Y = ExO。从这些观看中重建，定义。=三中并争论 基础追求最优化的问题5(BP) min |a|i subject to yn = Qa;(7.1)a(Ll)问题中的的次要重标记问题。调用回答a整体重建为企hy =、2自。木力水+ EE可泌由kj =jo k大尺度线性重建和大尺度非线性重建的结合是基于精尺度下的欠采样。当我们提 到这种方案时，当然，样本总数nhy = 2j0 + n是线性样本数加上压缩样本数目。 参考文献13中的衍生理论表明，这种混

19、合方案中，当应用的对象遵循肯定的束 缚(例如范围变化)，从而使精度在2-jl尺度下的线性样本中有可比性，只在使 用较少总样本的状况下适用。(c) Multiscale CS reconstruction, n = 2086020004000600080001 00001 20001400016000图13：信号块的重建，m =16384 (a) 512份样品的线性重建，xlin-x02=0.091; (b) 248份样本的混合CS重建(性别隔离)，xhy-x02=0.091; (c)208份样本 的多尺度 CS 重建，xms-x02=0.091。为数学计算便利，参考文献13中建议对CS进行性别

20、隔离部署，但在试验 中，它大大优于简洁的性别盲部署。由此，考虑如图13 (a)组所示的状信号, 其初始长度为m= 16384,是由信号长度为n = 512的线性样本中重建得到的， 其中，设置一个大尺度为j0= 5,以及最精尺度为jl=90(b)组所示重建有nhy=248 混合压缩样本(32个阳性样本，216个压缩阴性样本)。和以前一样，我们采纳 了匀称球形分布中的采样矩阵，且以及中的一个Haar小波基。精度明显具有 可比性，它远比图3 (b)组中的精度要高，(b)组所示结果为256例标准CS样 品的重建，m = 2048o现在争论图14中(a)组所示的凸粒信号，其初始长度为m= 16384,且

21、该 信号是从n= 1024的线性样本中重建出来的，这里我们设置个大尺度为j0= 5, 精度为我们采用混合重建，并再一次使用从匀称的球形分布中得到的采 样矩阵，以及中正交小波基和Daubechiessymmlet8 ”过滤器。(b)组所示为重 建结果，nhy=640混合压缩样本(32个阳性样品，608个压缩阴性样本)。再次， 重建精度具有可比性。它远比图10 (b)组中的精度要高，其显示了从512标准CS样品中的重建结果，其中m =2048。参考文献13中，性别隔离采样的想法在图像类不同范围上被扩展到更高的 维度。这些想法是1-D的状况下的直接扩展，我们将不再赘述。我们争论了混合 的CS采样的性

22、能，并将其应用到下面试验的图像数据上。图15所示为大小为 1024X1024的蒙德里安图像的重建结果，因此m=220。我们再次使用的Haar 小波扩张，这自然是适合这种类型的图像，其大尺度为j0=3,最精尺度为jl=6。 （a）组所示为n=4096样本时的线性重建结果，而（b）组为nhy = 1152下混合 压缩样本的混合CS方案的结果。（128个阳性样品，1024个压缩阴性样本）。重 建精度明显可比。图14：凸粒信号重建，m= 16384。（a） 1024个样本中的线性重建，xlin-x0 2=0.0404; （b） 640个样本中的混合CS重建（性别隔离），xhy - x02=0.0411

23、;（c） 544样本中的多尺度CS重建，xms-x02=0.0425。8多尺度压缩感知通过混合CS的明显作用，我们现在争论CS的完全多尺度部署。解释概念 最简洁的方法是使用我们的多尺度系统，它是一个标准一维正交小波系统。该想 法还可应用到其他多尺度系统和更高维度中。波基中对象X0的绽开力60 =水 + 52QjR财kkj=jo k现在考虑问题中的多级分层对象，分隔系数向量为(pjO,-), (ajO,-), (ajO+1,(ajl-1,-)然后我们应用一般线性采样来直接测量系数(由0)，然后一级一级地分别应用压 缩传感，采样数据yj与系数(aj,)有关，在j层时使用njx2jCS矩阵中j。我们

24、 从而共得到地样本数为 nms =2j0 +njO +njO+l +-+njl-l,与 m = 2j0 +2j0 +2j0+l +-+2jlT=2jl的系数相比，要得到重建，我们还应解决以下问题(BPj)mina 1 subjecttoyj =Dja,a -;为进行重建，我们设置，1一1企ms = %，物0比+ 砒)矽才 kj=jo k(当然，变化是有可能的，我们可能将集合大尺度jOJO+l,J0+1组在一起，并 从它们当中取得一个较大值。)(a) Linear reconstruction, n = 4096(b) Hytrid CS reconstruction, n = 1152(c)

25、Mu dscale CS reconstruction, n = 1048200 400 600 800 1000200 400 600 800 1000200 400 600 800 1000图15：蒙德里安图像重建，m =220 (a) 4096个样本中的线性重建，xlin-x0 /2=0.227; (b) U52个样本中的混合CS重建(性别隔离)，xhy - x02=0.228;(c) 1048个样品中的多尺度CS重建xms - x02=0.236。由图13(c)中使用多尺度CS所获得的结果的例子发觉，它显示了由nms=208 的压缩采样而重建得到的块信号重构信号块(nj0=32大尺度样

26、品，每一个具体 尺度j上的nj = min-1,48压缩样本，jO0, 中TxOp W R;详见13中该状况 的更多解释，其中规定了稀疏的变换系数中TxO。为了进行压缩测试，我们从m矩阵中中的n开头测试，其中nvm满意肯定 的条件，即CS1-CS3中的13。我们组成矩阵已二中WT,也可为n X m。依据 线性系统y=5x0,取n片测量信息y = (y(i) : 1 WiWn)。当nvm时，这 相当于测量值比信号x0自由度少。独立测量值的形式均为y(i) =( axO),例如每个测量值都是由争论对象x0 对核函数口测量值的积分得到的。这里的口是指三中的第i行。由公式己= 1PT和CS-matri

27、ces的已知性质，我们发觉口羊一个测量核函数都是一种基本小 元素的“随机”线性组合。所需矩阵中满意CSLCS3,证明白数列中的匀称分 布随机抽样是可构成的。下述13,在这种方式构成的矩阵集合，被称为匀速球 型集合。为重建一个近似的xO,我们应解决(LI) min / 甲 T x/l subject to y = Ex. (1.1)调用结果/ I, no xl, n的全部对象中产生的测量数据相同，测量数据的变 换系数为最小11范数。在13中提到，此重建过程可通过线性规划来实现，所 以可以认为是由于计算上易处理。事实上，在整个本文提出的试验中，我们使用 了原对偶障碍法这种线性规划解决方案，详情见5

28、。简言之，该方法涉及线性非适应性测量，然后是非线性近似重建。文献13中的误差范围说明尽管欠采样很明显(nvm),压缩对象还是可以 有高精度的重建。这些误差的形式表现为：xF,n - x0/2 W CpR(n/ log(m)l/2 - 1/p, n, m n0,(1.2)。当pv2时，该定义域内的大n的重建是精确 的，并且和m的关系不大。注释13把这些定义域解释为nCS和n二O(N logm 的测量值和已知N的最大转换系数一样好。实例描述了图像和光谱模型问题的 拙劣仿照。在当前相关工作中，相关理论的古典文学21,17,26 (Gel fand的n宽度 理论的进展)从多个抽象角度解决了近期相关问题

29、；详见13中的争论。在 如基础信息简单性这样的文献中，就已经提出了某些几类争论对象采样率很高， 是由于没有用点样品而是采纳了半随机线性组合一一详见24 争论中的单调功 能恢复例子。最近，Gilbert等人18争论用m-m傅立叶矩阵中的n个特殊行 来构成n-m矩阵，然而Candes, Romberg和Tao认为傅立叶矩阵中的随机儿 行来构成矩阵中。Candies, Romberg和Tao都认为这里可以用11的最小值，但 Gilbert等人却在争论不同非线性过程。此外，我们留意到，在修订时Candes, Romberg和Tao在文献13的概括部分得到了结论。最终，我们评价它为：更高程度的抽象，我们

30、在这里争论的是用11方法解 决欠定系统方程不断变稀疏的方法,这产生了大量的工作：5, & 10,11,12,14,15, 19,20,23,27,28.1.2问题读者可能要问了很多有关结果的问题(1.2),比如：考虑现在在这种曲波帧中有一例子适用于构架而不适用于邻位基础。使用 此框架来做卡通类图像的好处可能在13中提到。和波基一样，尺度参数J指定的是曲波框架元件的大小;我们考虑多尺度压缩 感知部署，它会在每一层中用到不同的nj。图16所示为在该方案中应用该熟识 Shepp- Logan 的结果。为了关心读者更深化地了解每一层的性能，我们比较图17中的图像系数和 重建系数。明显，在重建过程中由附

31、加噪声。尽管如此，这种噪声在整体的CS 重建中并不能被明显可见。(a) Original Image(a) Original Image(b) Linear Reconstruction(c) CS Reconstruction100200300400500100 200 300 400 500100 200 300 400 500100 200 300 400 500图16： （a） Shepp-Logan幻影图像，742400曲波系数;（b） 480256线性样品中 的重建，幻in-x02=0.142; （c）在103215多尺度压缩样品中采用曲波帧得 到的重建，xms x02 = 0.1

32、34。9结论在本文中，我们回顾了基本压缩感知构架，其中我们收集了对象的n个信息， 名义上，它有m个自由度，nm0当对象在感知上是是可压缩的时，变换系数 Ip范数可被良好掌握，然后，基本上通过测量对象中n的“随机”线性泛函, 并由变换系数11最小值来进行构建我们得到，在理论上，一个精确的重建;详情见（1.2）o9.1初步观看我们提出了一些应用为导向的问题。第一个问题时关于理论范围（L2）强度 的。这种范围包含未指定常数，所以该框架的实际意义在很大程度上取决于这些 常数的精确值。我们进行了多次模拟来与理论不等式（1.2）中观测到的特性做 比较。我们像知道在阅历关系（3.2）中得到的常数，是否在实际

33、应用中足够小， 即使是适合的n和m, m有几千个，n有几百个。我们的结论正是如此。然而，我们留意到，当对曾对象的小非零元素的的数量较少时，该方法的胜 利更令人印象深刻的，（由Ip模型可得）。在这里考虑的是问题的大小，当样本 数超出因数大约为4的非零元素时，该方法往往比较适用。不幸的是，只有由少 数非零项得到的信号是比较特殊的。我们对对象进行了块和凸粒进行了数值试验，并粗略仿照图像中的光谱和扫 描线条;对于这样的对象，其视觉外观是可衡量的，我们发觉低于某一阈值n时，CS重建视觉上比较嘈杂-即使在观看过程中并无噪音。X10(8 CS Recocstruciion00.5x10图17： （a） Sh

34、epp-Logan在7级下的精确曲波系数，（b） CS架构重建系数。9.2 扩展我们在这篇文章中主要工作在于通过争论几个CS构架的扩展来超越初步观看。 这些扩展包括， 后处理噪声去除。为了克服CS重建视觉噪声消失，我们通过平移不变的水平 依靠阀值来对CS重建进行后期处理。我们发觉，视觉噪声的消失可大大削减（对 于块和凸粒对象来说）。 在测量过程中允许存在噪声。基本CS架构不允许在观测中有噪声。为了解决 该状况下的噪声问题，我们建议事用噪声容限为L1的最小值，实质上用的是基 追踪中的基追踪降噪，这是以CS为基础的。我们提出的例子表明，在我们 的例子中能大致削减重建过程中的噪音影响。 多尺度部署。

35、更为显著地是，我们认为CS并不是唯一收集对象信息的方法， 而是应和大尺度下的经典线性采样一起来作为一个工具来使用。我们认为，在参 考文献13已经提到的理论上的混合方法，是可以和大尺度线性样本结合，并 与CS一起分开应用到每一个尺度中，而线性样本只存在与大尺度中。这两种方 法均比线性样本有效，同时也在我们实例的一些样本中给出了具有可比性的重建 精度。这是为了支持文献13中的理论叙述，其中提到了部署于混合方法中压 缩样本，在某些特定的对象中，可以对经典线性样本产生数量级的改进。交替CS矩阵。或许我们实证发觉的最大意义是，一些明显不同的随机矩阵合 集合都在CS构架的使用中表现相像。这样的发觉，假如通

36、常状况下是真的，那 么对算法的缘由来说是很重要的。为应用内点法解决线性规划（1.1）需要对很 多的矩阵向量产品小U和中TV进行战略性选择，从而选出向量u和v5。这比 应用由偏傅立叶和偏阿达玛集合定义的矩阵和T更快，其中的成本O（m log（m）是由浮点计算出的。明显，对于大m和n,人们会更喜爱在随机匀称集合 或随机符号集合中用这样的矩阵，其中会应用得到成本O （nm）的浮点计算。 这样看来，我们在CS架构中大量的性能上由足够的选择，这与13中定理全都， 并且，那些矩阵中的一些矩阵可被快速应用。压缩感知好像是采样信号一个有前景的策略，其特点是大量的标称样品，并 且呈现出已知变换的的高压缩，就像小

37、波变换和傅立叶变换。这里进行的有限试 验已经表明因数2, 4甚至问题大小中的合适大小的增益，而这些都可以由多尺 度的方式的部署和重建降噪的应用来增加。当然（1.2）范围中的理论应用好像比我们这里观看到的影响更多，在这个意 义上，至少对于大n和大m,压缩对象的特定类别中的确可能存在很多有点。当 递交本文时，有几组已经在探究这样的思路了，首先当然是Candes, Romberg, 和Tao,它们正在乐观争论3, 4, 30的应用，这是很兴奋人心的。此外，耶鲁 高校的R.R. Coifman正在使用光谱仪来进行CS构架的实际的物理试验。明显, 我们可期望在不久的将来这些构想会有有更多的试验和理论进展

38、。9.3 进一步争论的方向 压缩感知的压缩方案。本文已说明CS是一种削减的测量次数的工具，而不 是用于数据压缩的工具。我们的观点在测量成本很高时是使用的，但存储和沟通 的测量值却很廉价。这种状况下，主要成本是测量过程本身。例如，测量过程会 有长时延迟、辐射暴露、功率消耗，或需要很多专用物理设施组件。我们认为要 削减这样的成本花销。不同的观点却认为CS是一个压缩方案中的一部分，它的 系统比特率（不是测量资源）是驱动目标的。在此观点中，原始的CS测量需要 被量化，以得到较低的比特率，以及重建将涉及到使用这样的量化数据。另一种 解释将集中在CS概念的稳定性新审查中。有些问题已经在这里解决了过。我们

39、已在参考文献13中指出，即自动（L1）重建有肯定程度的稳定性（在L1范数）， 这表示假如数据能够精确量化，重建就是足够的。我们也在第6节指出，（L1, e ）在12范数上供应了稳定性。然而，需要更多具体争论的影响。我们认为， Cannes和他的团队都在进行这样的争论，并且我们鼓舞有爱好的读者关注他们 的工作。 减轻重建噪声。像在第2节和第3节展现的那样，当感测干测的数目较少， 我们常常会已噪声重建结束试验，虽然数据并无噪声。在第5节，我们通过后期 处理噪声去除方案解决了这一问题。然而据推想，经过认真地对重建误差统计特 性进行建模后可以更直接地接触这个问题。这种模式会改善去噪。由于其他限制, 如

40、总变化掌握和乐观约束，其中相关的内容也应当是有关心的。 混合/多尺度压缩传感。第7和第节中消失的概念验证的例子明确说明白使 用混合或多尺度传感方案的优点，优点表现性能方面，和计算简单程度上，方面 表现出明显的优势，使用一个或混合多尺度感测方案。这种初步成果提出了一些 值得进一步争论好玩问题。其中包括：-如何选择一个大尺度？由于最大尺度的系数的表示可直接测量，一方面，最 大尺度的选择对传感方案的性能有很大影响，另一方面对所需测量的总数也 有很大影响。我们方法是由小波变换通常有一系列的全水平大尺度的这一 事实得出的其次不断增大的精度下有不断增大的稀疏程度。因此，我们的模 拟使用了 最佳全尺度的数量

41、作为大尺度。这个问题会有进一步的检测。-如何在尺度间划分预算？ 一旦最大尺度被选定，对于多尺度CS来说， 我们还需要划分“细节”尺度之间允许测量的“预算”。本文采纳的方法为 将全部尺度中的中的样本平均安排。这是基于块小波变换的可见图案：即奇 点在每个尺度上的非零系数的数量相同。裁判问到这是否是真的样品的最佳 配置，我们也认为这个问题值得进一步争论。9.4 更多近期理论工作自本文提交的几个月里，一些好玩的理论文章已经具体阐述了基本不等式 (1.2)。 Candes 和 Tao 4以及 Rudelson 和 Vershynin36给出了 (1.2)的替换 方法，其中还包括，如，随机符号集合。这种大

42、n结果证明白上述第4节的阅历 证据，这样的替换集合表现除了相同的随机球形集合。Haupt和Nowak 34也争 论了随机信号，并得出了相像的结论。Tropp和Gilbert35的工作表明，在第2节的设置中，其中一个假定为只有 少数非零元素，非零元素一般可以使用贪欲逐步靠近(正交匹配追踪)，这比11 优化中的陈述计算效率更高。其结果粗略的争论表明，低阈值的阈值效应比这里 实际看到的还要低,例如由贪欲方法还原的比用11方法还原的稀疏度要高。Tropp 和Gilbert也得出这样一个结论，即随机符号集合与高斯集合表现相像。在第2节中观看到的相变在配套的文件中已经被认真争论过了29,更多内 容最近在3

43、2, 33有提及。其中表明10稀疏对象的完全还原的阀值正比于n,其 中n / m的比值不为零，其中还有大一n设定中的精确数值估量。Candes和Tao 31,提高了我们的噪音识别优化过程(LI, e )的熟识， 它的稳定性成流线型，并自然变成其他的矩阵集合。9.5 更多近期计算工作明显，加州理工学院的Candes和Romberg是在2004年秋季进行的试验和 本文中提到的试验是平行的;这些现在已经在和我们工作亲密相关，并对此很感 爱好的读者中传阅30。无论Tropp和Gilbert35或Alex Petukhov (私人通信) 都已经在CS设定的贪欲算法的中做了广泛的模拟。Haupt和Nowa

44、k 34也始 终在用随机符号系好做更多的数值试验。 n和m必需要多大？对于实际问题中的大小来说（L2）是否无意义？ 常数Cp的大小是多少？若（1.2）适用，常数是多少？ 当争论对象不能完全重建时，会发生什么样的错误呢？可能时误差项，即 使大小由（1.2）掌握，结构会不抱负吗？他们可能还会问： 如何将CS架构应用到实际信号中？参考文献13中，可以争论光谱和成 像的程式化模型;有人认为这些模型是用来在混合策略中配置CS的，这样可以在 粗尺度下的经典线性采样中用到相对少量的测量值，以及多数在CS策略下获得 的精尺度测量值。这些想法最初是用来做数学分析，还是为了在具体设置中有关 心？ 通过CS得到的人

45、造产品应当被抑制吗？ CS的任何后期处理需要“清理” 重建吗？ 在测量过程中假如消失噪音，应当怎么办？在观测过程中的任何噪音可能 会使框架分崩离析-即使是浮点计数法中很小的误差。假设这些问题的答案没有破坏性，通过扩展矩阵的种类而得到关于扩展方 法正常问题可以用到： 更具体的CS矩阵中。在有建设性而又明确地得到CS-矩阵上很有用。CS矩阵中可被快速应用。这和前面的问题有关。在（1.1）的线性规划公式 应用上是很便利的5,由于中和中均可被快速应用一还有他们的转置。以上便是我们认为应当回答的重要问题。1.3 概念验证和数值试验本文中，我们通过概念验证和计算试验提出了上述问题。我们认为每个问题 争论的

46、是小规模的模拟，然后生成合成数据集，并解释模拟的结果。虽然该模拟 方法不能明确回答一些问题，但它的确供应了有价值的证据，可以激发将来的理 论争论，并为将来试验和应用工作指明方向。其次节中，我们给出用到CS转换信号的例子作为热身，这些信号的真正 非零系数很少，但仍有通过Ip范数得到的稀疏系数测量值，且Ovp W 1。经 过分析实证结果，得到常数的Cp的数值证据，并将其与理论界（1.2）实证误差 进行比较。第四节中，我们发觉可自由选择CS-矩阵，这节内容描述了几种不同矩阵系 综的结果可能相同。尽管文献13的主要内容是iid列的矩阵，我们已经发觉 其他几个系综的状况也很好，包括局部傅立叶系综。18, 3我们发觉当监测样本量较小时，Ip设置的结果在某种程度上有些嘈杂， 即使数据测量值是无噪声的。为了改善这种状况，在第5节中我们争论通过CS 扩展的后期处理，来去除CS重建的“噪音:第6章争论到了嘈杂的观看，并 开发噪声感知重建方法。在第7节中，我们考虑到13中提到的CS扩展：这是一个混合方案，它使 用常规