[互联网]02 压缩传感.ppt
2. 压缩传感 Compressed sensing,林 通 tonglin123gmail.com 信息科学技术学院 智能科学系 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,/læso/ or /læsu/ 套索,11,前面讲了 线性回归 与 正则化，这部分基础内容贯穿整个课程,Compressed sensing From 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“, What's Happening in the Math. Sciences, AMS, 114-127.,以下材料从此综述摘录,14,buzzword buzz·word | 'bzwd n. 行话, 口号, 时髦词语,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 measurements Donoho: “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 Candès, 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 Candès and Michael Wakin,An introduction to compressive sampling. (IEEE Signal Processing Magazine, 25(2), pp. 21 - 30, March 2008) High-resolution version Justin 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“, What's 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,
