Compressed Sensing

zhiqiangMay 12, 2008 科学

最近这玩意儿很热，比如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等等不多说了。

查看更多关于compress sensing, 编码的内容。

你可能感兴趣的

At 2008.05.12 01:48, zhiqiang said:
test new comment features:
- latex support, using linux latex compiler instead of MimeTex, $\left\{\begin{array}{rcl}a&=&b+c\\\alpha&\leq&\gamma\end{array}\right.$
- wiki syntex
  - unordered list: new line with a started *
  - ordered list: new line with a started #
  - header: h3: new line with syntex == head content ==, h4: new line with syntex === head content ===
  - more: hyperlink, font formatting(bold, underline, etc.), refer wikipedia syntex
[Reply]
At 2008.05.12 09:58, Zig said:

哦，那个夫妻店居然还做这个。

[Reply]
- At 2008.05.12 10:09, zhiqiang said:
  
  你知道我说的是谁？
  
  [Reply]
At 2008.05.12 11:25, davidpeng said:

Hash Algorithm是不是它的一方面？

[Reply]
- At 2008.05.13 09:46, zhiqiang said:
  
  不明白你说的hash algorithm具体指的是哪个。不过无论是哪个，与这个compressed sensing也没有联系。
  
  [Reply]
At 2008.05.13 22:03, 张沈鹏 said:

在流数据的处理上。比如我想知道此blog到目前为止访问最多的十个IP地址（或者搜索引擎最热门的50个搜索）

这个有点像计数型bloom filter

[Reply]

« 赌博的最优策略

四川地震 »

Compressed Sensing

查看更多关于compress sensing, 编码的内容。

6条留言

test new comment features:

阅微堂