Hypothesis test for bounds on the size of random defective set

Arkadii D'Yachkov, Nikita Polyanskii, Vladislav Shchukin, Ilya Vorobyev

    Research output: Contribution to journalArticlepeer-review


    The conventional model of disjunctive group testing assumes that there are several defective elements (or defectives) among a large population, and a group test yields the positive response if and only if the testing group contains at least one defective element. The basic problem is to find all defectives using a minimal possible number of group tests. However, when the number of defectives is unknown there arises an additional problem, namely: how to estimate the random number of defective elements. In this paper, we concentrate on testing the hypothesis H0: the number of defectives ≤ s1 against the alternative hypothesis H1: the number of defectives ≥ s2. We introduce a new decoding algorithm based on the comparison of the number of tests having positive responses with an appropriate fixed threshold. For some asymptotic regimes on s1 and s2, the proposed algorithm is shown to be order-optimal. Additionally, our simulation results verify the advantages of the proposed algorithm such as low complexity and a small error probability compared with known algorithms.

    Original languageEnglish
    Article number8827291
    Pages (from-to)5775-5784
    Number of pages10
    JournalIEEE Transactions on Signal Processing
    Issue number22
    Publication statusPublished - 15 Nov 2019


    • Compressed sensing
    • error probability
    • parameter estimation
    • sparse matrices


    Dive into the research topics of 'Hypothesis test for bounds on the size of random defective set'. Together they form a unique fingerprint.

    Cite this