Combinatorial Group Testing And Sparse Signal Recovery

Compressed Sensing is a new sampling and coding techniques in the field of signal processing proposed by David Donoho, Emmanuel Candes and Terence Tao etc. in2006. It has aroused widespread concern both in academia and industry, and found applications in a variety of areas. The mathematical model of compressed sensing is to seek a sparse solution of an underdetermined linear system, which is also known as sparse signal recovery.Combinatorial group testing is a basic tool in conducting experiments to identify all low-frequency events in a large collection of samples. Its recent application into various molecular biology screening designs is often referred to as pooling design. Since the concerned samples are sparse, pooling design can also be regarded as a sparse signal recovery problem. Once the support set of the sparse signal is identified, there are many ways to estimate the value of the non-zero component. It implies that we only need to reconstruct the support set by pooling design algorithms.We originally use the combinatorial structure of General inhibitor model in pooling design theory to construct the sensing matrix in sparse signal recovery. We get perfect recovery of supports of signals under certain conditions and design an effective recovery algorithm. Our main results get an O(k2logn)×n sensing matrix and a decoding algorithm with total cost of the decoding complexity O(k2n log n) fork-sparse signals.