Compressed Sensing & Compressed Learning

Compressed sensing 又可以称为compressive sampling，是对香农采样定理的一种扩充。香农采样定理告诉我们，如果需要保证采样后信号的完全恢复，采样频率需要达到信号最高频的两倍。然而，对于稀疏信号（如信号覆盖了整个频率段，但其覆盖又是稀疏的）时，香农采样定理就显得比较保守。compressed sensing则告诉我们，对于属于R^n空间的，含有k个非零点的稀疏信号（ k << n )，我们不需要采集那么多点，而只需要采集O(C*k*logn)个点就足够了。

对于机器学习来说，若把数据存在的空间称为data domain，而我们观测到的数据所存在的空间称为measurement domain，通常情况下，这两个domain可能都非常大，就会遇到curse of dimensionality的问题，当然，machine learning有很多解决办法。Compressed learning其实也可以看成是属于其中的一种叫做“降维”的方法，就是使用m×n的采样矩阵A（ m << n ）对数据进行采样，再在采样后的数据上进行分类。Ref[2]讲的就是，当A满足(k,\epsilon)-RIP条件时，使用SVM在原始数据和在降维数据上的分类误差小于O(\sqrt{\epsilon})。

Ref：

1. E. J. Candès. Compressive sampling. Proceedings of the International Congress of Mathematicians, Madrid, Spain, 2006. http://www.acm.caltech.edu/~emmanuel/papers/CompressiveSampling.pdf
2. Robert Calderbank, Sina Jafarpour, and Robert Schapire, Compressed learning: Universal sparse dimensionality reduction and learning in the measurement domain (Preprint, 2009)