转载：稀疏表达 | 增强视觉 | 计算机视觉 增强现实

看了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;