Robust lossy detection using sparse measurements: The regular case

Sparse measurement structures - in which each measurement only depends on a small number of the inputs-arise in models of many problems such as sensor networks, group testing and even lossless data compression. The most important question in these applications is `How many measurements are sufficient to reconstruct the input ?´. Regular structures, where each input is measured the same number of times, require fewer measurements than when arbitrary measurements are used. In this paper we conduct a general analysis of the performance of these regular measurement structures when used for lossy reconstruction of the input in the presence of measurement noise. The main contribution of our work is the generality of the result which is applicable to lossy detection with arbitrary, even non-linear measurements and with inputs and outputs in any discrete domain. The second contribution is the quantification of the effect of noise in the measurements on the reconstruction performance, which can be used to analyze the robustness of these sparse measurement structures. We show the generality and applicability of our results by analyzing the performance of pooling designs for rare allele detection.