压缩感知介绍--最终版培训课件

压缩感知理论及应用CompressedSensing(CS)：TheoryandApplications南京航空航天大学电子工程学院张弓1背景介绍1.1传统采样理论介绍及问题提出1.2压缩感知理论的基本思想2压缩感知理论分析2.1压缩感知的前提2.2压缩感知流程介绍第一步：信号的稀疏表示第二步：观测矩阵的设计第三步：信号重构3压缩感知应用3.1波形信号仿真分析3.2CS图像融合3.3单像素CS相机3.4CS雷达1.1传统采样理论介绍及问题提出传统的基于Nyquist采样定理指导下的信息的处理主要表现在两个方面：1、采样速率需达到信号带宽的两倍以上才能精确重构信号。这样的采样硬件成本昂贵，获取效率低下，对宽带信号处理的困难日益加剧。2、在实际应用中，为了降低成本，人们常将采样的数据经压缩后以较少的比特数表示信号，而很多非重要的数据被抛弃，这种高速采样再压缩的方式浪费了大量的采样资源，另外一旦压缩数据中的某个或某几个丢失，可能将造成信号恢复的错误。1背景介绍而现实生活中，随着信息技术的高速发展，信息量的需求增加，携带信息的信号所占带宽也越来越大这就大大考验了数字化社会对信息处理的能力，包括：数据存储、传输和处理速度，基于Nyquist采样的理论遭到严峻的考验。1背景介绍能否以远低于Nyquist采样定理要求的采样速率获取信号，而保证信息不损失，并且可以完全恢复信号？即能否将对信号的采样转化为对信息的采样？一个亟待解决的问题：1背景介绍1.2压缩感知理论的基本思想一种新的理论—CompressedSensing(CS,压缩感知，亦称压缩传感)。由Candes、Romberg、Tao和Donoho等人在2004年提出，2006年才发表文献基本思想：1、信号是可压缩的或在某个变换域是稀疏的;2、就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上;3、然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号。1背景介绍2压缩感知理论分析2.1压缩感知的前提2.2压缩感知流程介绍2.3第一步：信号的稀疏表示2.4第二步：观测矩阵的设计2.5第三步：信号重构2.1压缩感知的前提稀疏性的定义：一个实值有限长的N维离散信号，由信号理论可知，它可以用一个标准正交基的线性组合来表示，假定这些基是规范正交的，其中表示矩阵的转置，那么有其中，若在基上仅有个非零系数时，称为信号的稀疏基，是稀疏(K-Sparsity)的。1NxR12,,,TkKT1Nkkkx,kkxxKKNkxxK2压缩感知理论分析E.Candes等人证明了：信号的稀疏性是CS的必备条件。信号是可压缩的或在某个变换域是稀疏的，这个条件的限制等同于信号带宽对于Nyquist采样定理的约束。2压缩感知理论分析2.2压缩感知流程介绍长度为N的信号在正交基上的变换系数是稀疏的；用一个与基不相关的观测基对系数向量进行线性变换，并得到观测向量利用优化求解的方法从观测集合中精确或高概率地重构原始信号。x:()MNMN:1YMx2压缩感知理论分析如同信号带宽对于Nyquist，信号的稀疏性是CS的必备条件；如同Nyquist采样规则对于Nyquist-Shannon采样定理，CS的关键是非相关测量（该测量称为测量矩阵），他们都是信号得以精确恢复的条件；如同Fourier变换对于Nyquist，非线性优化是CS重建信号的手段。2压缩感知理论分析第一步：信号的稀疏表示如图是一个稀疏度为3的稀疏变换，,在时域基本都是非零值，但将其变换到域时，非零值就只有3个了，数目远小于原来的非零数目，实现了信号的稀疏表示。xx2压缩感知理论分析如何找到信号的最佳稀疏域呢？这是压缩感知理论的基础和前提，也是信号精确重构的保证。对稀疏表示研究的热点主要有两个方面：1、基函数字典下的稀疏表示：寻找一个正交基使得信号表示的稀疏系数尽可能的少。比较常用的稀疏基有：高斯矩阵、小波基、正（余）弦基、Curvelet基等。Candes和Tao经研究发现光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor系数及具有不连续边缘的图像信号的Curvelet系数等都具有足够的稀疏性,可以通过压缩感知理论恢复信号。2、超完备库下的稀疏表示：用超完备的冗余函数库来取代基函数，称之为冗余字典，字典中的元素被称之为原子，目的是从冗余字典中找到具有最佳线性组合的K项原子来逼近表示一个信号，称作信号的稀疏逼近或高度非线性逼近。2压缩感知理论分析超完备库下的稀疏表示涉及到两个问题：一是如何构造这样一个适合某一类信号的冗余字典；二是在已知冗余字典的前提下如何设计快速有效的分解方法来稀疏地表示某一个信号。右图为一些不同的字典2压缩感知理论分析第二步：观测矩阵的设计观测器的目的是采样得到个观测值，并保证从中能够重构出原来长度为的信号或者稀疏基下的系数向量。观测过程就是利用观测矩阵的个行向量对稀疏系数向量进行投影，得到个观测值，即MNxMNMMTYxx2压缩感知理论分析TYxx2压缩感知理论分析观测矩阵要满足什么样的条件呢？从上式中求出是一个线性规划问题，但由于方程的个数少于未知数的个数，这是一个病态问题但如果具有稀疏性，则有可能求出确定解。Candes、Tao等人提出必须保证观测矩阵不会把两个不同的项稀疏信号映射到同一个采样几何中，这就要求从观测矩阵中抽取的每个列向量构成的矩阵是非奇异的，这跟有限等距特性(RIP)条件的要求是一致的。R.Baraniuk将上述条件简化为如果保证观测矩阵和稀疏基不相干，则在很大概率上满足RIP性质。不相干是指不能用稀疏表示，不相干性越强，互相表示时所需的系数越多。MNxKji2压缩感知理论分析第三步：信号重构首先介绍下范数的概念。向量的p-范数为：当p=0时得到0-范数，它表示上式中非零项的个数。由于观测数量，不能直接求解，在信号可压缩的前提下，求解病态方程组的问题转化为最小0-范数问题：11Nppipiss0mins.t.TTxYxMNx2压缩感知理论分析对于0-范数问题的求解是个NP问题，需要列出所有非零项位置的种组合的线性组合才能得到最优解，在多项式时间内难以求解，而且也无法验证其可靠性。Chen，Donoho和Saunders指出求解一个优化问题会产生同等的解。于是问题转化为：或者：求解该最优化问题，得到稀疏域的系数，然后反变换即可以得到时域信号。1min..TTxstYx21minTTYxx2压缩感知理论分析目前出现的重构算法主要可归为三大类：1)第一类贪婪算法：这类算法是通过每次迭代时选择一个局部最优解来逐步逼近原始信号，典型的贪婪算法--MP算法，贪婪算法是针对组合优化提出,目前已发展了多种变形，例如，OMP,OOMP,CosMP等。该类重建算法速度快,然而需要的测量数据多且精度低。2)第二类凸优化算法：这类方法是将非凸问题转化为凸问题求解找到信号的逼近，如BP算法，梯度投影方法等。该类算法速度慢，然而需要的测量数据少且精度高。3)第三类组合算法：这类方法要求信号的采样支持通过分组测试快速重建，如代表性方法SparseBayesian。该类方法位于前两者之间。2压缩感知理论分析3压缩感知应用3.1波形信号仿真分析3.2CS图像融合3.3单像素CS相机3.4CS雷达3.1波形信号仿真分析基于CS理论的一个简单的信号分析。信号长度为N=256，稀疏度为K=7，测量数M=32。信号为三个频率叠加的正弦信号，傅里叶正交变换矩阵作为系数矩阵，高斯矩阵来测量，并用OMP算法重构原信号。050100150200250300-1.5-1-0.500.511.52originalsignal050100150200250300-1.5-1-0.500.511.52recovery3压缩感知应用原信号与恢复结果对照图：050100150200250300-1.5-1-0.500.511.52RecoveryOriginal3压缩感知应用3.2CS图像融合图像融合是对来自单一传感器不同时间、不同环境下获取的图像或由多个传感器同一时间获取的信息进行多级别、多层次的处理与综合，从而获得更丰富、更精确、更可靠的有用信息。图像融合的目的是提高图像显示的质量、实现图像的特征提取、图像去噪、目标识别和跟踪以及图像的三维重构。大部分图像的稀疏特性为CS的应用带来可能，同时CS的引入为图像的融合在计算速度、融合策略上都带来了新的飞跃。3压缩感知应用图像融合结果图：3压缩感知应用3.3单像素CS相机运用压缩感知原理，RICE大学成功研制了单像素CS相机。传统百万像素的相机需要百万个探测传感器，而压缩传感数码相机只使用一个探测器来采光，然后跟捕获后的计算相结合来重构图像。这种样机的镜头由两部分组成：一个光电二极管和一个微镜阵列。该相机直接获取的是M次随机线性测量值而不是获取原始信号的N个像素值，为低像素相机拍摄高质量图像提供了可能。3压缩感知应用“数字微镜阵列”完成图像在伪随机二值模型上的线性投影的光学计算，其反射光由透镜聚焦到单个光敏二极管上，光敏二极管两端的电压值即为一个测量值y，将此投影操作重复M次，即得到测量向量Y，然后用最小全变分算法构建的数字信号处理器重构原始图像x。数字微镜器件由数字电压信号控制微镜片的机械运动以实现对入射光线的调整，相当于随机观测矩阵。3压缩感知应用字母R的实验结果：3压缩感知应用3.4CS雷达在雷达目标探测中，目标相对于背景高度稀疏，与复杂的雷达系统、海量数据呈现极度的不平衡，这就为CS技术在雷达目标探测与识别的应用提供了必要的条件。3.4.1CS与传统的高分辨雷达3.4.2CS与MIMO雷达3.4.3CS与雷达成像3压缩感知应用3.4.1CS与传统的高分辨雷达CS雷达的三个关键点（1）发射信号必须是充分不相关的；（2）在CS方法中，不需要使用匹配滤波器；（3）目标场景可以恢复是在假设目标满足稀疏性约束的条件下。3压缩感知应用3.4.1CS与传统的高分辨雷达CS技术很重要的思想是设计一个观测矩阵，用来表示稀疏信号的字典集，并且与是不相关的。利用这个思想设计出CS雷达接收机如下图所示。ADC积分器混频器rt1,1cpt取值3压缩感知应用假设空间有若干个稀疏目标，将目标所在的距离向与方位向分割成网格形式。CS雷达可以检测的目标数量，为稀疏单元数目。如果，则可以采用CS理论，通过优化问题求解，精确分辨出空间的多个目标。2NKK2KN3压缩感知应用3.4.2CS与MIMO雷达2004年Fishler等人提出了多输入多输出(MultipleInputMultipleOutput，MIMO)雷达的概念MIMO雷达收发阵列配置图3压缩感知应用3.4.2CS与MIMO雷达文献YaoYu,AthinaP.Petropulu,H.VincentPoor,MIMORadarUsingCompressiveSampling,IEEEJournalOfSelectedTopicsinSignalProcessing,Vol.4,NO.1,FEB2010基于小规模的无线网络将CS理论应用于非相参MIMO雷达系统,求得目标的角度和多普勒解。文献Chun-YangChenandP.P.Vaidyanathan,CompressedSensinginMIMORadar,Signals,SystemsandComputers,200842ndAsilomarConferenceon，26-29Oct.2008结合MIMO雷达目标在距离-多普勒-角度域的稀疏特点,研究了CS在相参MIMO雷达系统中的信号重构和波形优化问题。文献YaoYu,AthinaP.Petr