Recovering simple signals

The primary goal of compressed sensing and (non-adaptive) combinatorial group testing is to recover a sparse vector x from an underdetermined set of linear equations Φx = y. Both problems entail solving Φx = y given Φ and y but they use different models of arithmetic, different models of randomness models for F, and different guarantees upon the solution x and the class of signals from which x is drawn. In [1], Lipton introduced a model for error correction where the channel is computationally bounded, subject to standard cryptographic assumptions, and produces the error vector x that must be found and then corrected. This has been extended in [2], [3] to create more efficient schemes against polynomial and logspace bounded channels. Inspired by these results in error correction, we view compressed sensing and combinatorial group testing as an adversarial process, where Mallory the adversary produces the vector x to be measured, with limited information about the matrix Φ. We define a number of computationally bounded models for Mallory and show that there are significant gains (in the minimum number of measurements) to be had by relaxing the model from adversarial to computationally or information-theoretically bounded, and not too much (in some cases, nothing at all) is lost by assuming these models over oblivious or statistical models. We also show that differences in adversarial power give rise to different lower bounds for the number of measurements required to defeat such an adversary. By contrast we show that randomized one pass log space streaming Mallory is almost as powerful as a fully adversarial one for group testing while for compressed sensing such an adversary is as weak as an oblivious one.