压缩感知延伸.docxVIP

压缩感知的延伸Yaakov Tsaig David L. Donoho二零零四年十月二十日修改于二零零五年四月二十六日摘要：我们研究了已提出的压缩感知（CS）的概念及相关工作，[18，3,4]。这一概念提出了一种信号或图像，虽然未知，但可通过已知转换压缩得到（例如，小波或傅立叶），少数的测量值会对它产生影响，但数据点的额定数的影响较大，然而这种技术目前还未被准确重建。样本具有非适应性，并测量变换系数的“随机”线性组合。通过解决与测量数据一致的变换系数和得到的最小可能l1范数来得到近似重建。我们是在有利情况下提出最初的“概念验证”例子的，这时绝大多数的变换系数为零。我们为lp稀疏设置而继续做了一系列的数值实验，实验中对象的所有系数非零,但系数在lp范围内,p的取值范围为p∈(0,1)。重建误差遵循不等式且符合理论，并且是良性常量。我们报告了几个等值“随机”线性组合的可行族，其中包括随机球形,随机的迹象,部分傅里叶和部分阿达玛。下一步我们会研究如何将这些想法用到光谱和图像处理的模型问题中，并且由合成实例可得，CS中的重建往往是视觉“噪音”。为了抑制这种噪声，我们通过平移不变的后期处理来去噪，并发现外观得到很大改善。我们也研究到多尺度调配压缩感知，其中进行了各种规模的分离并且CS分别适用于每一个尺度; 这比文字调配CS方法论的质量重建更好。该结果表明，在进行有利设置的适当调配时，CS架构比传统的采样的保存更有意义，并有基本思路的许多有用扩展。关键词和短语：基追踪。线性方程组欠定系统。线性规划。随机矩阵理论。致谢：来自NSF DMS 00-77261, 01-40698 (FRG) 和ONR-MURI的部分支持。感谢迈克尔·桑德斯的优化建议，感谢Emmanuel Cand`es为自己的相关工作与J. Romberg 和 T. Tao进行讨论。RaphyCoifman对常量的（1.2）问题的寻根究底激发了这份报告。1 简介在现代多媒体饱和的世界里，“每个人都知道，所有人类可理解的数据是高度压缩的。在利用这一事实，主要解决方法是先进行数据的采样，然后使用各种压缩方案消除冗余。这便产生了以下问题：为什么要用传统的方式来取样然后再压缩数据呢？难道不能直接获得一个压缩表示吗？显然，如果这是可能的，在不同领域内的蕴涵会更快的从数据采集中扩展出来，这会提高采样率并降低通信负担。最近有几篇论文[18，3，13，4]指出，不同假设下，直接获得压缩表示的的形式是有可能的。本文将通过一系列压缩传感方案的有效性实例研究来验证这一猜想。1.1 方法我们从［13］中采用的语言和符号;这种方法比较抽象，但在许多潜在的应用领域有因式分解的优势。假设研究对象为矢量x0，且x0 ∈Rm，这代表m数字信号或图像的取样值。假设研究对象为可压缩先验，且转换编码格式为jpeg或jpeg-2000。从数学角度上，我们用Ψ代表问题中正交转换的矩阵，则有数列ψi, i = 1, . . . , m。可压缩的意思是在p ≤ 1，适当地R 0，∥ΨT x0∥p ≤ R; 详见［13］中该情况的更多解释，其中规定了稀疏的变换系数ΨT x0。为了进行压缩测试，我们从m矩阵Φ中的n开始测试，其中n m满足一定的条件，即CS1-CS3中的[13]。我们组成矩阵Ξ=ΦΨT，也可为n × m。根据线性系统y = Ξx0，取n片测量信息y = (y(i) : 1 ≤ i ≤ n)。当n m时，这相当于测量值比信号x0自由度少。独立测量值的形式均为y(i) = ?ξi,x0?，例如每个测量值都是由研究对象x0对核函数ξi测量值的积分得到的。这里的ξi是指Ξ中的第i行。由公式Ξ = ΦΨT和CS-matrices Φ的已知性质，我们发现咩一个测量核函数都是一种基本ψj 元素的“随机”线性组合。所需矩阵Φ满足CS1-CS3，证明了数列Φ的均匀分布随机抽样是可构成的。下述[13]，在这种方式构成的矩阵集合，被称为匀速球型集合。为重建一个近似的x0，我们应解决(L1) min ∥ΨT x∥1 subject to y = Ξx. (1.1) 调用结果 x?1，n。x?1，n 的所有对象中产生的测量数据相同，测量数据的变换系数为最小l1 范数。在[13]中提到，此重建过程可通过线性规划来实现，所以可以认为是因为计算上易处理。事实上，在整个本文提出的实验中，我们使用了原对偶障碍法这种线性规划解决方案，详情见[5]。简言之，该方法涉及线性非适应性测量，然后是非线性近似重建。文献［13］中的误差范围说明尽管欠采样很明显(n m)，压缩对象还是可以有高精度的重建。这些误差的形式表现为：∥x?1,n ? x0∥2 ≤Cp · R · (n/ log(m))1/2?1/p, n, m n0. (1.2)。当p 2