The theory of Compressed Sensing (highly popular in recent years) has a close relative that was developed around thirty years earlier and has been almost forgotten since – the design of screening experiments. For both problems, the main assumption is sparsity of active inputs, and the fundamental feature in both theories is the threshold phenomenon: reliable recovery of sparse active inputs is possible when the rate of design is less than the so-called capacity threshold, and impossible with higher rates.
Another close relative of both theories is
multi-access information transmission
. We survey a collection of tight and almost tight screening capacity bounds for both
strategies which correspond to either having or not having feedback in information transmission. These bounds are inspired by results from multi-access capacity theory. We also compare these bounds with the simulated performance of two analysis methods: (i) linear programming relaxation methods akin to basis pursuit used in compressed sensing, and (ii) greedy methods of low complexity for both non-adaptive and adaptive strategies.