Sequential adaptive compressed sampling via huffman codes

In this paper we introduce an information theoretic approach to construct a sequence of binary sampling vectors to determine a sparse signal. Unlike the standard approaches, ours is adaptive in the sense that each sampling vector depends on the previous sample results. We prove that the expected total cost (number of measurements and reconstruction combined) we need for an s-sparse vector in ℝ ⁿ is no more than s log n + 2s.