Title :
Robust lossy detection using sparse measurements: The regular case
Author :
Narayanaswamy, Balakrishnan ; Negi, Rohit ; Khosla, Pradeep
Author_Institution :
Dept. of Electr. & Comput. Eng., Carnegie Mellon Univ., Pittsburgh, PA, USA
Abstract :
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.
Keywords :
signal detection; signal reconstruction; group testing; lossless data compression; measurement noise; noise effect quantification; nonlinear measurements; regular measurement structures; robust lossy detection; sensor networks; signal detection; sparse measurement structures; Compressed sensing; Distortion measurement; Electric variables measurement; Loss measurement; Maximum likelihood decoding; Maximum likelihood detection; Noise measurement; Performance analysis; Robustness; Testing;
Conference_Titel :
Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on
Conference_Location :
Austin, TX
Print_ISBN :
978-1-4244-7890-3
Electronic_ISBN :
978-1-4244-7891-0
DOI :
10.1109/ISIT.2010.5513453