Andnot童鞋翻译了EJ Candes的压缩感知的介绍性论文“People Hearing Without Listening:” An Introduction To Compressive Sampling在这里全文转载，感谢Andnot童鞋
PDF版本
Candes, E., & Wakin, M. (2008). An Introduction To Compressive Sampling IEEE Signal Processing Magazine, 25 (2), 21-30 DOI:10.1109/MSP.2007.914731
1. 介绍
传统信号或者图像采样多采取香农采样定理：即采样频率为信号频率最大值（那奎斯特采样频率）的二倍。
本文提出一种新的信号处理思路——压缩采样（CS）。在这种新方法下，采样率会大大降低。
压缩采样依赖两条原则：稀疏性和不相干性，前者从属于信号，后者从属于感测模式。
在开始正文之前，咱首先得说明一下，这篇东西偏向于理论，各位看官可以自行跳过某些部分。这方面的工作奠基人同样也是compressive sensing的大牛之一E.J Candes（Donoho的得意门生），以及Candes的学生Ben Recht，前者刚从caltech被挖到stanford，后者目前刚到wisconsin做AP。Candes大牛，stanford统计系出生，师从Donoho。Candes原来的主要工作集中在小波分析上（实际上C牛非常多产），比如著名的curvelets以及ridgelets，04年左右开始和Tao合作从事compressive sensing的理论工作，这里有他的简要介绍。
继续唠叨，上回说到借着collaborative filtering的东风，矩阵的稀疏表示受到了广泛的关注。说到矩阵的稀疏性，大部分看官可能有所误解。这个矩阵稀疏表示严格而言可以分为两种：
1. 矩阵元素的稀疏性，即矩阵非0元个数相对较少。参照向量的范数，同样可以定义矩阵的0范数，并将其松弛到矩阵的1范数的优化问题。
2. 矩阵奇异值的稀疏性，即矩阵奇异值中非0元的个数（即矩阵的秩）相对较少。仿照向量情况下0范数与1范数的关系，同样可以将其松弛的到迹范数（trace norm）的优化问题。
稀疏表达是近年来SP, ML, PR, CV领域中的一大热点，文章可谓是普天盖地，令人目不暇给。老板某门课程的课程需要大纲，我顺道给扩展了下，就有了这个上中下三篇介绍性质的东西。遗憾的是，我在绝大多数情况下实在不算是一个勤快的人，这玩意可能充满bug，更新也可能断断续续，尽请诸位看官见谅了。顺道一提，ICCV09有一个相关的 tutorial 。
据传博文里公式数量和其人气是成反比例关系的，一个公式可以驱散50%的读者，我写完这个（上）之后点了点公式数量，觉得大约是要无人问津了。所以，在介绍稀疏表达之前，让我们先来展示下其在computer vision中的应用，吸引下眼球。
首先是图像恢复（以前有人贴过Obama还记得不），由左侧图像恢复出右侧结果
全文转载自这个博客，很不错的博客，作者来自中科院，大伙收藏吧。
看了Ma Yi的工作后，才开始对Sparse represenation开始感兴趣。从最开始的惊奇，到中间的觉得无用，再到现在觉得还是有点用，其对这整套想法的把握真可谓一曲三折。不过总得来说，都是在项目和实验的驱动下进行的。
和ML的人不同，我们关注的点在CV中的application。解决图像分类中重要的一个方法是bag of features，也就是形成很多words图像patch后，去fit新的图，然后送去投票编码，最后分类。
其中一个很关键的步骤是怎么得到这些words的图像patch？一种方法是K-means做聚类。当然这个方法有很多naive的假设，不过总得来说效果凑合。所以最近几年大家都在死命搞features extraction，直到发现最后无论如何都打不败的是SIFT,HOG之流。
当然，科学总在进步中。大家发现feature这块都做不动了，自然开始动其他的念头，要不转行去做其他应用，要么得用ML的新工具了。最近在ICCV上发现在K-means上的重大改进，其核心就是放松了原来kmeans聚类后分配新样本去哪个类的分配方式，加上考虑到什么locally constraints，最后取得了相当好的效果。仅仅和最基本的dense sift+linear svm就打败了multiple features+nonlinear svm。哈，仔细研究了论文，发现解那个式子，可以用lasso搞搞。没准回头可以实现一下。
sparse很好，但是并不是什么新问题和新方法。总结一下这个熟悉又陌生的新思潮吧。这个总结有很多版本，看过Prfans上的，不过现在prfans好像down掉了。
最最开始要算Terrance Tao在IT上那篇best papers，因为他是华人，长得特别像电影明星，然后20+就当UCLA的教授。。。所以很吸引人。不过关于这个方面在CV还有ML开始火还在于以下几篇文章作者的工作吧。
首先是这篇文章，
John Wright, Allen Yang, Arvind Ganesh, Shankar Shastry, and Yi Ma, Robust face recognition via sparse representation. (To appear in IEEE Trans. on Pattern Analysis and Machine Intelligence)大致做法就是用training data表出新的data，即新的x是training data的线性组合，如果training data数大大小于feature数，那么这就相当于CS里的x_0=Ax，A的每列是个sample，x是每个sample的权重。于是给出新的 x_0，可以通过优化x的l_1找到最sparse的解，即用最少数量的sample表出新的点。然后还可以在Ax前乘个measurement matrix，用来做特征选择，其实就是进一步降维。我在yaleB上的实验也证明了这个方法还是比较好的。但是中间的小trick是：
如果我用来做遮挡问题，那么训练库中的样本出现问题后，测试集上的结果就将变得相当差。比如用张猴子脸训练，检测人脸的时候用许多脸来拼凑，最后得到的是猴子脸而不是人脸。。。
比较囧的是，好多CVPR和ICCV上2009的文章都来follow这种motivation的工作。然后这篇文章也挺有意思的
Robert Calderbank, Sina Jafarpour, and Robert Schapire, Compressed learning: Universal sparse dimensionality reduction and learning in the measurement domain (Preprint, 2009)其中， 证明了measurement space里train个svm和原空间里train的svm是同一个问题。关键或许是 投影到多个space里去，然后在每个space里 train，然后做boosting，类似于multi-view learning。感觉最近muliti-kernel learning是个大趋势呀。
当然一些研究还得结合自己问题的数据上的特殊性解决才行。给一些关于Compression Sensing(Sparse Representation方面的链接：
Compressive Sensing资源主页：
Compressive Sensing Resources （最权威最全面的Compressive Sensing资源主页，几乎什么都能找的到）；
Compressive Sensing （和上面的差不多）；
Compressive Sensing Listing； 马毅的课程主页
Compressive Sensing Videos；Compressed Sensing Codes （还有Compressive Sensing Resources 的Software一栏中）；
Nuit Blanche；Compressive Sensing: The Big Picture；Terence Tao‘s What’s new;理论方面的代表人物：
David Donoho; Emmanuel Candes;
最新评论