[互联网]02 压缩传感.ppt
2.压缩传感Compressed sensing,林 通 信息科学技术学院 智能科学系2012-8-28,1,Key Lab.Of Machine Perception,School of EECS,Peking University,China,2,在图像处理、计算机视觉、和机器学习中遇到的很多问题都是病态问题；我们需要考虑介于很容易和完全不可能之间的问题。,3,4,回归：目标值连续分类：目标值离散（类标签）回归有很多应用，比如预测明天的温度多少度，预测某房屋明年的价格，等等最早的回归是勒让德和高斯发明的“最小二乘法”，应用到科学与工程各个领域。还有比最小二乘法应用更广泛的吗？回归的直观含义：姚明女儿的身高会回落到平均线附近，否则姚明的后代身高会不断增长而超过人类极限,5,回归的历史,6,7,此处再次提现了微积分的威力，微分后直接得到平衡条件方程（很多时候可能是PDE)，解方程后就得到答案。,大X矩阵由数据点排成行堆积而成,8,9,Ridge Regression and Lasso,Ridge regression shrinks the regression coefficients by imposing a penalty on their size(using L2 vector norm)Lasso(also known as basis pursuit)is a shrinkage method like ridge,with subtle but important differences(using L1 norm)Can generalize to Lq norm(q=0)Ref:The elements of statistical Learning,Stanford Textbook,chap.2,10,/lso/or/lsu/套索,11,前面讲了 线性回归 与 正则化，这部分基础内容贯穿整个课程,Compressed sensingFrom Wikipedia,Compressed sensing,also known as compressive sensing,compressive sampling and sparse sampling,is a technique for finding sparse solutions to underdetermined linear systems.In electrical engineering,particularly in signal processing,compressed sensing is the process of acquiring and reconstructing a signal that is supposed to be sparse or compressible.,12,13,Mackenzie,Dana(2009),Compressed sensing makes every pixel count,Whats Happening in the Math.Sciences,AMS,114-127.,以下材料从此综述摘录,14,buzzword buzzword|bzwdn.行话,口号,时髦词语,15,16,17,18,19,20,21,22,A Big Idea!,23,以下内容摘录自此讲稿第1部分；第2部分数学较深因此省略,24,25,26,问题2：采集大量数据之后，又需要花精力做数据压缩，把大部分数据扔掉；为什么要这么麻烦呢？,27,28,29,30,31,32,33,三篇中文综述,压缩传感综述，李树涛，魏丹，自动化学报，2009压缩感知基本理论，邵文泽，韦志辉，图像图形学报，2012压缩感知，许志强，2012,34,35,36,37,38,39,40,41,42,43,44,45,46,压缩传感应用,47,48,49,50,51,总结与展望,52,53,54,55,注意这两个概念是有差别的：K稀疏是大部分为0，而可压缩是指大部分数值很小可忽略。,56,57,58,59,60,61,62,63,64,65,具体内容省略,66,67,68,Mark Davenport,Marco Duarte,Yonina Eldar,and Gitta Kutyniok,Introduction to compressed sensing,(Chapter in Compressed Sensing:Theory and Applications,Cambridge University Press,2012),经验：L1范数的优点,相对于传统L2范数，L1范数具有如下优点：Dense noise.位置广泛但噪声幅度不大Outliers.位置稀疏（但未知）,异常幅度较大Missing data,or matrix completion.已知少量某些位置的数据缺失，需要补全。,69,70,其它说法：outlying,incomplete,corrupted 比如在分类中，outlier指某些数据的位置或标签异常，incomplete指某些数据特征向量已知位置有缺失，corrupted指某些数据特征向量内未知未知有较大幅度的异常，但不知其位置，不知有几个（但稀疏），不知幅度有多大,71,72,73,74,75,还有一类方法：组合分组检验,76,Fundamental Goal:Minimize M,Compressed sensing aims to minimize resource consumption due to measurementsDonoho:“Why go to so much effort to acquire all the data when most of what we get will be thrown away?”,最后我们回顾CS的根本目标：使观测数M最小的条件下，精确重建原始信号。,77,Donoho,Stanford,Tutorials and Reviews:CSRice,Emmanuel Cands,Compressive Sampling.(Int.Congress of Mathematics,3,pp.1433-1452,Madrid,Spain,2006)Richard Baraniuk,Compressive sensing.(IEEE Signal Processing Magazine,24(4),pp.118-121,July 2007)Emmanuel Cands and Michael Wakin,An introduction to compressive sampling.(IEEE Signal Processing Magazine,25(2),pp.21-30,March 2008)High-resolution versionJustin Romberg,Imaging via compressive sampling.(IEEE Signal Processing Magazine,25(2),pp.14-20,March 2008)Dana Mackenzie,Compressed Sensing Makes Every Pixel Count.(Mackenzie,Dana(2009),Compressed sensing makes every pixel count,Whats Happening in the Math.Sciences,AMS,114-127)Richard Baraniuk,More Is less:Signal processing and the data deluge.(Science 331(6018),pp.717-719,February 2011)Massimo Fornasier and Holger Rauhut,Compressive sensing.(Chapter in Part 2 of the Handbook of Mathematical Methods in Imaging(O.Scherzer Ed.),Springer,2011)Mark Davenport,Marco Duarte,Yonina Eldar,and Gitta Kutyniok,Introduction to compressed sensing,(Chapter in Compressed Sensing:Theory and Applications,Cambridge University Press,2012)Marco Duarte and Yonina Eldar,Structured compressed sensing:Theory and applications.(To appear in IEEE Transactions on Signal Processing)Rebecca Willett,Roummel Marcia,and Jonathan Nichols,Compressed sensing for practical optical imaging systems:a tutorial.(Optical Engineering,vol.50,no.7,pp.072601 1-13,2011)L.Jacques and P.Vandergheynst,Compressed Sensing:When sparsity meets sampling.(see below,this box is too small)Gitta Kutyniok,Compressed Sensing:Theory and Applications.(Preprint),78,THE END,问题？,79,
