压缩传感的讲座.doc

压缩传感报告理查德.巴拉尼克 莱斯大学发表在IEEE信号处理杂志,2007年7月 1.背景香农/奈奎斯特采样定理告诉我们，为了不丢失信息均匀采样信号时，我们必须采取至少两倍的带宽的采样频率。在许多应用程序中，包括数字图像和视频摄像头,奈奎斯特采样频率会很高，我们最终得到的采样信息太多，必须压缩存储或传输。在其他应用程序,包括成像系统(医学扫描仪，雷达)和高速数模转换器，增加采样率或密度超出了，当前最先进设备的采样范围，并且非常昂贵。 在篇论文中,我们将学习一种新的使用压缩传感技术，来解决这些问题【1,2】。我们将以一个更一般的线性测量方案取代传统的采样和重建方法，加以优化。以明显低于奈奎斯特速率的采样频率，获得某些种类的信号。 2.相关这里提出的方法可以用来说明本科或研究生数字信号处理的统计数据和应用数学中遇到的，数据采集、线性代数、扩展基础、逆问题、压缩降维等各种优化问题之间的联系。3.先决条件 理解和教学这种方法所需的先决条件是线性代数、优化知识和概率知识。 4.问题说明 奈奎斯特抽样利用其频带限制，完全描述了信号。我们的目标是减少测量的数量，通过利用其压缩性完整地描述一个信号。转折是我们的测量不是点样品，但是一般较之线性泛函更具普遍意义的信号。考虑一个圆,实值finite-length、一维离散时间信号x,我们认为这是一个N1列向量与元素xNRN,N = 1,2,。,N。我们对待一个图像或更高维的数据vectorizing成一长一维向量。 任何信号RN可以在N1的基础上向量我 N i = 1。为简单起见,假设是正交的基础。形成NN基础矩阵:=1 | 2 |。我 | N通过叠加向量作为列,我们可以表达任何信号x，x =XNi=1si i or x = s其中年代是N1列向量的权重系数si = hx,2 = T我x和T表示厄密共轭转置操作。显然,x和年代是等价表示相同的信号,与x在时间域和域。 我们将重点讨论信号稀疏表示,x是一个线性组合的K基础向量,与KN。也就是说,只有K的si(1)非零和(N?K)为零。稀疏是出于这样一个事实,许多自然和人造的信号是可压缩的,存在着基础的表示(1)有几大系数和许多小的系数。可压缩信号K-sparse来近似表示,这是变换编码的基础3。例如,自然图像往往是可压缩的离散余弦变换(DCT)和小波基础3的JPEG压缩和JPEG - 2000标准为基础。音频信号和通信信号在局部傅里叶计算可压缩。 变换编码的过程中扮演着重要的角色在数据采集系统,如数码相机,样本的数量很高,但信号是可压缩的。在这个框架中,我们获得完整的N-sample x信号,计算转换系数的完整通过年代 si = Tx;定位最大K系数和丢弃(N?K)系数最小;和编码的最大系数K值和位置。(在实践中,我们还和位置的值转换为数字）。 不幸的是,sample-then-compress框架患有三种固有的低效率:首先,我们必须先从一种潜在的大量的样品氮即使最终所需的钾很小。其次,编码器必须计算所有的N转换系数 si ,即使它会丢弃所有但K。第三,编码器面临编码的开销大系数的位置。 作为替代,我们将研究一个更一般的数据采集方法,凝结的信号直接在压缩表示没有经历的中间阶段N样本。考虑更一般的线性测量计算的过程MN内部产品之间x和一个向量的集合 .叠加yj进去1的测量向量y和测量向量 行成一个MXN.(a)(b) 图1:(a)压缩传感测量过程(随机高斯)测量矩阵和离散余弦变换(DCT)矩阵 。系数向量稀疏与K = 4。(b)测量过程的产品矩阵XXX四列对应的非零si高亮显示。y测量向量的线性组合这四列。矩阵X(1)替代,我们可以写XXXX.见图1(a)(2)的图形描述。请注意,测量过程非自适应性;即，X不以任何方式依赖于x信号。 我们在接下来的目标是设计一个测量矩阵X和K-sparse和可压缩信号重建算法,只需要M约等于N或者稍微测量，大约的数量尽可能多的测量系数编码在传统转换编码器。我们的方法是基于压缩传感理论的介绍最近在1、2。 5，解决方案 解决方案包括两个步骤。在第一步中,我们设计一个稳定的测量矩阵X,确保重要信息在任何K-sparse或可压缩信号不是破坏的降维x 2 RN down to y 2 RM.在第二步中,我们开发一个重建算法恢复x从测量。起初,我们关注到底K-sparse信号。 5.1稳定的测量矩阵 首先,我们设计了测量的数据采集系统,它是基于矩阵X。我们的目标是,让米测量向量(y),我们可以稳定重建length-N信号x,或相当于其稀疏系数向量年代x的基础。显然不可能重建如果x的测量过程损失的信息。不幸的是,一般是这样:由于测量过程是线性和中定义的术语矩阵X和Y,解决年代给定y(2)只是一个线性代数问题,和M N,方程有少于未知,使解决方案一般病态。 然而,K-sparsity年代来到我们的救援。在这种情况下,测量向量y只是一个线性组合的X的K列对应的XXX(b)(参见图1)。因此,如果我们知道先验K条目的年代是零,然后我们可以形成一个MK线性方程组解出这些非零项,在现在的数量方程米的数量等于或超过未知K。确保一个充分必要条件这米K系统状态良好的,因此运动稳定逆这对于任何向量v共享相同的K非零项年代XXXX在词,矩阵X必须保持这些特定K-sparse的长度向量。当然,在实践中我们不会知道K非零项的位置年代。有趣的是,一个可以显示K-sparse稳定逆的充分条件和可压缩信号是X满足(3)任意3 sparse向量v .这是所谓的限制等容属(RIP1。 稳定的另一种方法是确保测量矩阵X是不连贯的与sparsifying基础X,向 j 不能稀疏表示向量我,反之亦然(1、2、4)。经典的例子功能三角洲和傅立叶正弦曲线峰值扮演的角色 j 和我;傅里叶不确定性原理立即收益率不连贯。 所以,给定一个sparsifying基础X,我们如何构建一个测量矩阵X,X =XX撕吗?不幸的是,仅仅是验证给定的X combinatorially RIP复杂的;我们必须验证(3)为每个X K的非零项的可能的组合length-N向量v。 在压缩传感,我们回避这个问题通过选择X随机矩阵。例如,我们画出矩阵元素X作为独立和恒等分布的随机变量(iid)从零均值,1 / N-variance高斯密度(白噪声)(1、2、5)。然后,测量y仅仅是M x的元素的不同随机加权线性组合(记得图1(a)和注意x)的随机结构。 一个高斯X有两个有趣的和有用的属性。首先,X是语无伦次的基础X =我三角洲峰值高概率,因为它需要完全N峰值代表X的每一行。更严格,使用浓度的测量参数,一个MN iid高斯矩阵X =我= X可以展示概率高的RIP如果M cK日志(N / K),在一个小的常数c1、2、5。因此,我们可以预期恢复length-N K-sparse高概率和可压缩信号从justM cK日志(N / K)N随机高斯测量。其次,由于iid高斯分布的属性产生X,矩阵X = XX也iid高斯不管(正交)sparsifying基础矩阵X的选择。因此,随机高斯测量X是普遍,X = XX RIP高概率为每一个可能的x。在众多国家中,随处矩阵随机1项也可以显示RIP和普遍性属性5。 5.2信号重建算法 RIP提供了理论保证K-sparse或可压缩信号可以完全米所描述的测量在y,但它并没有告诉我们如何恢复它。信号重建一步必须测量y,随机测量矩阵X(或随机的生成)的种子,sparsifying依据X X和再生length-N信号,或相当于其稀疏系数向量。我们再次开始关注K-sparse信号。 XXXXXX因此,我们的目标是找到信号的稀疏系数向量翻译后的空的空间。 XXX当p = 0我们获得“0“常态”,非零项的数量;因此K-sparse向量“0 K。 最低的2规范重建:这种类型的解决逆问题的经典方法是最小二乘法;也就是说,我们选择翻译零空间中的向量H与最小的2范数(能源): 甚至有一个方便的封闭的solutionb XXX。但是不幸的是当我们所寻求的向量年代K-sparse,X最小化几乎永远不会发现它。我们得到相反的是nonsparseb X的响在6.1节(更多内容见下文)。 最小X标准重建:自从X规范(4)不能反映信号稀疏,一个合乎逻辑的选择是寻找翻译零空间H sparsest向量:XXX 可以证明,只有M = K + 1 iid高斯测量,这种优化将恢复K-sparse信号高概率6。但不幸的是解决(5)两个数值不稳定,是一个np完全问题,需要一个详尽的XX枚举所有可能的组合在年代的非零项的位置。最小X标准重建:压缩传感令人吃惊的是,从XXX iid高斯测量我们可以完全reconstructK-sparse高概率向量和密切近似可压缩向量稳定通过X优化1、2XXXX这是一个凸优化问题,方便减少线性程序称为基础追求1、2的计算复杂度是O(N3)。 总而言之,压缩传感数据采集系统由基于X的随机测量线性规划重建获得X紧随其后。 6，讨论 6，1几何解释 压缩传感的几何问题RN帮助我们想象X重建成功,X重建失败的原因。首先,注意的所有K-sparse向量在RN是一个高度非线性的空间组成的所有K-dimensional超平面与坐标轴一致(见图2(a)。因此,稀疏向量生活接近RN的坐标轴。 想象为什么X重建失败,注意翻译零空间H = N()+ s的维度(NM)和面向随机角由于矩阵X的随机性。参见图2(b),但在实践中注意,XXX,所以你需要推断你的直觉到高维度。(4)的Xminimizerb X点H接近原点。我们能找到这一点通过炸毁一个超球面球(X),直到它触及到h .由于随机的方向,最接近pointbs将概率高的生活远离坐标轴,因此既不会少,也不会接近正确的答案。 在X球X形成强烈的反差,XX球在图2(c)是“尖”点对齐沿着坐标轴(和它成为pointier随着环境维度N)。因此,当我们炸毁X球,它会首先联系翻译零空间H在靠近坐标轴,这正是稀疏向量X所在地。 6.2模拟信号 虽然我们都集中在离散时间信号,压缩传感也适用于模拟信号x(t)可以仅使用稀疏表示的K的N元素从一些持续或词典我(t)倪= 1。虽然每个我(t)(因此可能大带宽奈奎斯特率高),信号x(t)只有K自由度,我们可以应用上面理论来衡量它的速度低于奈奎斯特。实际模拟压缩感知的一个例子系统一个所谓的“analog-to-information”转换器-7中给出了;有有趣连接8。图2:(a)一个稀疏向量年代躺在K-dimensional超平面与RN的坐标轴从而接近轴。通过X(b)压缩感知恢复最小化不找到正确的稀疏解年代翻译零空间(绿色超平面),而是non-sparse向量X(c)有足够的测量,通过X最小化并找到正确的稀疏恢复解决方案。 7.实际的例子 考虑图3的单像素”“实线压数码相机(a),直接获得随机线性测量没有首先收集N像素值9。这一事件lightfield对应于所需的图像x不是集中到CCD或CMOS采样数组而反射数字微镜器件(DMD)组成的一个数组的N小镜子。(分布式监测是发现在许多计算机投影仪和投影电视。)反射的光通过第二个镜头收集起来,然后集中到一个光电二极管(单一像素)。每个镜子可以向独立的光电二极管(对应于1)或消失从光电二极管(对应于一个0)。每个测量获得的图是如下:随机数发生器(RNG)镜子在伪随机取向模式0/1创建测量向量X。光电二极管的电压等于刘晓波,内部产品X X和所需的图像之间。这个过程是重复M次获得所有的条目在y。(a) (b)(c) 图3(b)和(c)说明一个目标对象和一个图像X单像素相机拍摄的原型实线9使用随机测量比重构像素少约60%。在这里重建通过执行总变差优化1,这是在小波域X重建密切相关。 单像素,主要利用实线压缩传感的方法是,这款相机可以适应图像波长困难或昂贵的地方创建一个大型阵列的传感器。它还可以获得数据随着时间的推移,使视频重建9。 8.结论 在这节课中,我们已经了解到获得信号采样并不是唯一的途径。感兴趣的信号是可压缩的或稀疏时,它可以更有效和流线型的采用随机测量和优化只为了获得我们需要的测量。 我们还了解到,重建我们的老朋友最小二乘我们失败,我们需要看看其他口味的凸优化线性规划(参见4、10)。抗压传感仍然是一个新兴的领域,保持开放的心态和许多有趣的研究问题。一个相当详尽的参考/cs目前的研究方向是可用的。(a)(b)(c)图3:单像素,(a)实线压缩传感摄像头。(b)传统数码相机图像的足球球。(c)6464黑白图像相同的软球(N = 4096像素)从M = 1600中恢复过来随机测量了(a)。图像的相机(b)和(c)不应该是一致的。参考文献：1 E. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” IEEE Trans. Inform. Theory, vol. 52,no. 2, pp. 489509, Feb. 2006.2 D. Donoho, “Compressed sensing,” IEEE Trans. Inform. Theory, vol. 52, no. 4, pp. 12891306, April 2006.3 S. Mallat, A Wavelet Tour of Signal Processing. Academic Press, 1999.4 J. Tropp and A. C. Gilbert, “Signal recovery from partial information via orthogonal matching pursuit,” April 2005,/_jtropp/papers/TG05-Signal-Recovery.pdf.5 R. G. Baraniuk, M. Davenport, R. DeVore, and M. B. Wakin, “The Johnson-Lindenstrausslemma meets compressed sensing,” 2006, /cs/jlcs-v03.pdf.6 D. Baron, M. B. Wakin, M. Duarte, S. Sarvotham, and R. G. Baraniuk, “Distributed compressed sensing,” 2005, /cs/DCS112005.pdf.7 S. Kirolos, J. Laska, M. Wakin, M. Duarte, D. Baron, T. Ragheb, Y. Massoud, and R. G. Baraniuk, “Analog-to-information conversion via random demodulation,” in IEEE Dallas Circuits and Systems Workshop, Oct. 2006.8 M. Vetterli, P. Marziliano, and T. Blu, “Sampling signals with finite rate of innovation,” IEEE Trans. Signal Processing, vol. 50, no. 6, pp. 14171428, June 200