最近这玩意儿很热，比如Terry Tao凑了不少热闹，这边有对夫妻店也在做这玩意儿，连续听了好几次这方面的讲座，觉得挺有趣的。

Compressed Sensing是什么意思呢？存在一种编码矩阵$A$，对任何长为$n$的$x$，使得从编码后的$y=Ax$可以(近似)复原$x$的最大的$k$项，而且$y$的长度只有$k\log\frac{n}{k}$。这种把$x$编码成很短的$y$，但又能恢复$x$的绝大部分信息（在某些特定条件下），看似无用（因为单就保存数据而言，这种编码方式并无优势），但在某些特定条件下是非常有用的。

编码所用的矩阵$A$的构造和解码的方法是compressed sensing研究的主要内容，这里主要介绍它的应用：

• 现在流行高分辨率的相机，什么500万像素的相机都拿不出手了。但要注意的是，绝大部分照片的信息含量根本就没有这么大，500万像素的照片保存到硬盘上往往只有500K。但问题就在于与其在拍照后再进行压缩，为何不直接在拍照时就不用获取那么多象素的数据呢？也就是说只需要合理安排像素获取点的位置，100万像素的相机有可能达到与500万像素相机同样的效果。
• 在流数据的处理上。比如我想知道此blog到目前为止访问最多的十个IP地址（或者搜索引擎最热门的50个搜索）。一个方法是开一个$2^{32}$大小的计数数组，每来一个新的访问，对应的IP计数器加1。但这种方法的缺点在于所需的内存太大了。使用Compressed Sensing的方法是，构造sensing矩阵$A$，然后每次$y+=A_i$，$A_i$是$A$的第$i$列。根据compressed sensing的原理，$y$包含了所需要的信息。这样所用的内存就很少了。
• 还有就是什么Error Correcting Code等等不多说了。

写于2008年五月 12日