Info-greedy sequential adaptive compressed sensing

We present an information-theoretic framework for sequential adaptive compressed sensing, Info-Greedy Sensing, where measurements are chosen to maximize the extracted information conditioned on the previous measurements. We lower bound the expected number of measurements for a given accuracy, and derive various forms of Info-Greedy Sensing algorithms under different signal and noise models, as well as under the sparse measurement vector constraint. We also show the Info-Greedy optimality of the bisection algorithm for k-sparse signals, as well as that of the iterative algorithm which measures using the maximum eigenvector of the posterior Gaussian signals. Numerical examples demonstrate the good performance of the proposed algorithms using simulated and real data.