Friday, October 31, 2008

CS: Adaptive Sampling: Sequential adaptive compressed sampling via Huffman codes, Compressive Structured Light for Participating Media

The question of adaptive sampling comes back often even though the initial intent of compressed sensing is to have a linear acquisition process. In effect, if one is to nonlinearly acquire signals, how is that different from JPEG and more specialized compression techniques ? Well for one, if we had to wait for a standard like JPEG for high-dimensional signals, we'd have to wait for a long, no make that a looooooong time. Hence it becomes obvious that one should look at CS as a way to perform a nonlinear compr
ession scheme in fields where
 the amount of (economic?) interest is very restricted. Here is the latest entry on this matter:

Sequential adaptive compressed sampling via Huffman codes by Akram Aldroubi, Haichao Wang, Kourosh Zarringhalam. The abstract reads:
There are two main approaches in compressed sensing: the geometric approach and the combinatorial approach. In this paper we introduce an information theoretic approach and use results from the theory of Huffman codes to construct a sequence of binary sampling vectors to determine a sparse
 signal. Unlike other approaches, our approach is adaptive in the sense that each sampling vector depends on the previous sample. The number of measurements we
 need for a k-sparse vector in n-dimensional space is no more than O(k log n) and the reconstruction is O(k).

The O(k log n) result is very interesting but I am a little bothered about the "unlike other approaches.." as "unlike most other approaches.." would have
 sufficed. We have seen adaptive measurements before (as listed in the Big Picture page ):

I have mentioned them before, but let me do this again as 

Let us note the following in the page:

In our experiment, we use the vertical binary stripe patterns as the coded light pattern. Each frame has 128 stripes. The stripes are randomly assigned to be 0 (black) or 1 (white) according to Bernoulli distribution (with p=0.5). We also tried Hadamard codes and found that the Bernoulli random code is better.

I am sure they will also be able to use adaptive measurements at some point in time.

Image Credit: NASA/JPL/Space Science Institute, Have you ever seen star shining through Saturn's ring ? W00050600.jpg was taken on October 28, 2008 and received on Earth October 29, 2008.

No comments: