M. Malyutov, P. Grosu, and H. Sadaka

Separate Testing Inputs vs. Linear Programming Relaxation

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. A collection of tight and almost tight screening capacity bounds for non-adaptive experimental designs were obtained by 1980. We compare here the simulated capacity and operation time of two analysis methods: (i) linear programming relaxation methods used in compressed sensing, and (ii) separate testing of inputs for nonadaptive strategies. The parallel implementation of the latter allows fast processing of high-dimensional models.

КЛЮЧЕВЫЕ СЛОВА: random design, active inputs, separate testing of inputs, sparsity, linear programming relaxation, capacity, statistical simulation, parallel computing, factorial models.