压缩感知概述

LOGO压缩感知概述赵瑞珍北京交通大学信息科学研究所2011年7月5日2目录简介◇理论产生背景◇研究现状◇压缩感知描述研究内容◇测量矩阵◇稀疏重建算法◇模拟实现◇应用举例进一步研究方向CompressiveSensing31.1理论产生背景CompressiveSensing41.1理论产生背景CompressiveSensing51.2研究现状2006《RobustUncertaintyPrinciples：ExactSignalReconstructionfromHighlyIncompleteFrequencyInformation》TerenceTao、EmmanuelCandès2006《CompressedSensing》DavidDonoho2007《CompressiveSensing》RichardBaraniuk上述文章奠定了压缩感知的理论基础。国内也将其翻译成压缩传感或压缩采样。CompressiveSensing6国际研究现状理论一经提出，就在信息论、信号处理、图像处理等领域受到高度关注。在美国、英国、德国、法国、瑞士、以色列等许多国家的知名大学(如麻省理工学院、斯坦福大学、普林斯顿大学、莱斯大学、杜克大学、慕尼黑工业大学、爱丁堡大学等等)成立了专门的课题组对CS进行研究。此外，莱斯大学还建立了专门的CompressiveSensing网站，及时报道和更新该方向的最新研究成果。7国内研究现状西安电子科技大学石光明教授在《电子学报》发表综述文章，系统地阐述了压缩传感的理论框架以及其中涉及到的关键技术问题。燕山大学练秋生教授的课题组针对压缩感知的稀疏重建算法进行了系统深入的研究，提出一系列高质量的图像重建算法。中科院电子所的方广有研究员等，探索了压缩感知理论在探地雷达三维成像中的应用。除此之外，还有很多国内学者在压缩感知方面做了重要的工作，如清华大学、天津大学、国防科技大学、厦门大学、湖南大学、西南交通大学、南京邮电大学、华南理工大学、北京理工大学、北京交通大学等等单位，在此不一一列举。8“CompressiveSamplingandFrontiersinSignalProcessing”“SparseRepresentationsandHighDimensionalGeometry”://to-cs.blog.sohu.com/entry//加州大学洛杉矶分校美国明尼苏达大学杜克大学2007年5月30日到6月1日，加州大学洛杉矶分校开展了关于“SparseRepresentationsandHighDimensionalGeometry”的短期讨论班，众多知名学者聚集，讨论压缩感知领域现有成果和今后的发展方向2007年6月4日到15日，美国明尼苏达大学举办了主题为“Compressivesamplingandfrontiersinsignalprocessing”讨论班。2009年2月25日和26日，AFRLATR中心发起的关于压缩感知的讨论班在Duke在大学举行，本次讨论班汇集了压缩感知领域的知名学术专家，集中讨论压缩感知理论、算法及其应用等。学术交流与资源CompressiveSensing9重建算法1.3压缩感知描述CompressiveSensing10重建算法1.3压缩感知描述CompressiveSensing11一简介1.1理论产生背景1.2研究现状1.3压缩感知描述二研究内容2.1测量矩阵2.2稀疏重建算法2.3模拟实现2.4应用举例三进一步研究方向CompressiveSensing12CompressiveSensing2.1测量矩阵13常用矩阵及特性CompressiveSensing1δ0,xδ)(1Φxxδ)(1222222RIP特性为充分条件。限制等距特性（RestrictedIsometryProperty，RIP）测量矩阵应满足以下特征：其列向量满足一定的线性独立性。其列向量体现某种类似噪声的独立随机性。14随机矩阵确定性矩阵高斯矩阵轮换矩阵傅里叶矩阵多项式矩阵贝努力矩阵哈达吗矩阵非相关测量矩阵托普利兹矩阵结构化随机矩阵Chirp测量矩阵┇┇常用矩阵及特性CompressiveSensing常用测量矩阵：随机矩阵重建性能好，但不易于硬件实现。确定性测量矩阵因为其占用存储空间少，硬件实现容易，是未来测量矩阵的研究方向，但目前确定性矩阵的重建精度不如随机矩阵。15CompressiveSensing重建算法2.2稀疏重建算法16算法模型0argmin||||..stxxΦx=yCompressiveSensingΦx=y17求解思路直接求解相当困难。以下两种解决方案：1不改变目标函数，寻求近似的方法求解用近似的方法直接求解0范数问题，如贪婪算法等。2将目标函数进行转化，变为更容易求解的问题（1）将0范数问题转化为1范数问题（2）采用光滑函数逼近0范数，从而将0范数问题转化为光滑函数的极值问题CompressiveSensing18近似求解方法CompressiveSensing正交匹配追踪算法（OMP算法）的迭代步骤如下：输入：感知矩阵Φ，测量向量y，误差阈值；输出：x的稀疏逼近ˆx，重建误差r；初始化：余量0ry，重建信号0x0，索引集0，迭代次数0n；Step1：计算余量和感知矩阵Φ的每一列的内积1nTngΦr；Step2：找出ng中最大的元素，{1,2,...,}argmax[]||niNikg；Step3：更新索引集1{}nnk及原子集合1{}nnkΦΦφ；Step4：利用最小二乘求得近似解1()nnnnTTxΦΦΦy；Step5：更新余量nnryΦx；Step6：判断迭代是否满足停止条件-1-nnrr，满足则停止，ˆnxx，nrr，输出ˆx，r；否则转Step1。Θ=ΦΨ19转化模型1范数比2范数更逼近0范数1argmin||||..stxxΦx=yCompressiveSensing0argmin||||..stxxΦx=y原问题：转化后：20转化模型1min..nRstxWxΦxy12111{,},||||||NdiagxxxW,是一个很小的正数其中，,CompressiveSensing另一种转化形式：21转化模型CompressiveSensing222()ixixe010lim()00iiixxx1()()Niixx00lim()Nxx引入光滑函数，实现对0范数的逼近：22常见的重建算法（1）匹配追踪系列：匹配追踪（MatchingPursuit,MP）正交匹配追踪(OrthogonalMatchingPursuit,OMP)稀疏自适应匹配追踪(SparseAdaptiveMP,SAMP)正则化正交匹配追踪(RegularizedOMP,ROMP)等（2）方向追踪系列：梯度追踪(GradientPursuit,GP)共轭梯度追踪(ConjugateGP,CGP)近似的共轭梯度追踪(ApproximationCGP,ACGP)贪婪算法CompressiveSensing23常见的重建算法凸优化算法（1）基追踪法(BasisPursuit,BP)（2）最小角度回归法(LeastAngleRegression,LARS)（3）梯度投影法(GradientProjectionforSparseReconstruction,GPSR)等。另类算法（1）Bayesian类的统计优化算法（2）基于光滑l0范数最小的SL0算法（Smoothedl0Norm）（3）最小化lp(0p1)范数的迭代聚焦算法(FocalUnderdeterminedSystemSolver,FOCUSS)等。CompressiveSensing24改进方法举例：自适应正则化匹配追踪算法的提出算法特点不足OMP单原子选择精确重建较长的时间代价需已知稀疏度ROMP正则化过程，重建时间短，精确重建需已知稀疏度SAMP自适应过程，无需已知稀疏度，精确重建时间成本高RAMP自适应过程，正则化过程，无需已知稀疏度，运行时间短，精确重建25实验结果对比算法名称峰值信噪比/dB相对误差匹配度运行时间/sMP19.550.10530.947218.202OMP26.490.09080.9548160.433ROMP28.180.07470.96267.802SAMP27.920.07710.961648.22RAMP28.400.07290.96359.010不同算法的重建质量对比（）M/N=0.5262.3模拟实现模拟信号x(t)数字信号y(m)系数a(n)数字信号x(n)1AIC狭义上的压缩传感过程稀疏重构过程广义的压缩感知过程CompressiveSensing273、模拟实现实例：单像素相机DMD：digitalmicromirrordeviceRNG：randomnumbergeneratorCompressiveSensingΦx=y28基于压缩感知的水印加密方法由于感知矩阵的多样性及压缩比的可调节性，有效地提高了整个加密过程的安全性，在不知道密钥的情况下，水印几乎是不可提取的，这在实际的版权保护中能有效防止不法分子对水印的恶意篡改、提取。XXXXXx(a)原水印(b)水印加密后(c)含水印图像(d)提取的水印(a)原水印(b)水印加密后(c)含水印图像(d)提取的水印(a)原水印(b)水印加密后(c)含水印图像(d)提取的水印2.4应用举例292.4应用举例新方法：干净小波系数非常稀疏，而含噪小波系数很稠密，然而两者通过测量矩阵作用后却非常接近，因此在重建过程中通过最小化非零小波系数的个数对原小波系数进行估计，从而将去噪问题转化为一个最优化问题。该方法非常适合于低信噪比信号的去噪。CompressiveSensing,,,,,||ˆ0,||jkjkjkjk,,,,,sign()(||),||ˆ0,||jkjkjkjkjk小波硬阈值方法小波软阈值方法基于稀疏重建的小波去噪30实验结果CompressiveSensing31不同去噪方法的信噪比对比实验结果CompressiveSensing32一简介1.1理论产生背景1.2研究现状1.3压缩感知描述二研究内容2.1测量矩阵2.2稀疏重建算法2.3模拟实现2.4应用举例三进一步研究方向CompressiveSensing33进一步研究方向目前，压缩感知理论仍处于发展阶段，有很多关键问题尚待解决，如:（1）探索测量矩阵的必要条件，构造确定性矩阵；（2）如何硬件实现压缩感知的过程；（3）提高现有重建算法恢复质量、速度，论证算法理论基础，保证其收敛，增强鲁棒性；（4）设计不同环境下的重建算法；（5）设计移动压缩传感器等。CompressiveSensingLOGO北京交通大学信息科学研究所