Generalized Group Testing
Generalized Group Testing
复制标题
广义组测试
DOI：
10.1109/tit.2022.3218174
复制
发表时间：
2021
影响因子：
2.5
通讯作者：
Qiaoqiao Zhou
中科院分区：
文献类型：
--
作者：
Xiwei Cheng;S. Jaggi;Qiaoqiao Zhou
In the problem of classical group testing one aims to identify a small subset (of size <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula>) of diseased individuals/defective items in a large population (of size <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>). This process is based on a minimal number of suitably-designed group tests on subsets of items, where the test outcome is positive iff the given test contains at least one defective item. Motivated by physical considerations, such as scenarios with imperfect test apparatus, we consider a generalized setting that includes as special cases multiple other group-testing-like models in the literature. In our setting the test outcome is governed by an arbitrary <italic>monotonically increasing</italic> (stochastic) test function <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula>, with the test outcome being positive with probability <inline-formula> <tex-math notation="LaTeX">$f(x)$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula> is the number of defectives tested in that pool. This formulation subsumes as special cases a variety of noiseless and noisy group-testing models in the literature. Our main contributions are as follows. Firstly, for any monotone test function <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula> we present a non-adaptive scheme that with probability <inline-formula> <tex-math notation="LaTeX">$1-\varepsilon $ </tex-math></inline-formula> identifies all defective items. Our scheme requires at most <inline-formula> <tex-math notation="LaTeX">${\mathcal{ O}}\left ({{\Psi (f)} d\log \left ({\frac {n}{\varepsilon }}\right)}\right)$ </tex-math></inline-formula> tests, where <inline-formula> <tex-math notation="LaTeX">${\Psi (f)}$ </tex-math></inline-formula> is a suitably defined “sensitivity parameter” of <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula>, and is never larger than <inline-formula> <tex-math notation="LaTeX">${\mathcal{ O}}(d^{1+o(1)})$ </tex-math></inline-formula>, but indeed can be substantially smaller for a variety of <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula>. Secondly, we argue that any non-adaptive group testing scheme needs at least <inline-formula> <tex-math notation="LaTeX">$\Omega \left ({(1-\varepsilon) {\psi (f)} d\log \left ({\frac {n} d}\right)}\right)$ </tex-math></inline-formula> tests to ensure high reliability recovery. Here <inline-formula> <tex-math notation="LaTeX">${\psi (f)}$ </tex-math></inline-formula> is a suitably defined “concentration parameter” of <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula>, and <inline-formula> <tex-math notation="LaTeX">${\psi (f)}\in \Omega {(1)}$ </tex-math></inline-formula>. Thirdly, we prove that our sample-complexity bounds for generalized group testing are information-theoretically near-optimal for a variety of sparse-recovery group-testing models in the literature. That is, for <italic>any</italic> “noisy” test function <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula> (i.e., <inline-formula> <tex-math notation="LaTeX">$0 < f(0) < f(d) < 1$ </tex-math></inline-formula>), and for a variety of “(one-sided) noiseless” test functions <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula> (i.e., either <inline-formula> <tex-math notation="LaTeX">$f(0)=0$ </tex-math></inline-formula>, or <inline-formula> <tex-math notation="LaTeX">$f(d)=1$ </tex-math></inline-formula>, or both) studied in the literature we show that <inline-formula> <tex-math notation="LaTeX">$\frac {\Psi (f)} {\psi (f)} \in \Theta (1)$ </tex-math></inline-formula>. As a by-product we tightly characterize the heretofore open information-theoretic order-wise sample-complexity for the well-studied model of threshold group-testing. For general (near)-noiseless test functions <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula> we show that <inline-formula> <tex-math notation="LaTeX">$\frac {\Psi (f)} {\psi (f)} \in {\mathcal{ O}}(d^{1+o(1)})$ </tex-math></inline-formula>. We also demonstrate a “natural” test-function <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula> whose sample complexity scales “extremally” as <inline-formula> <tex-math notation="LaTeX">$\Theta (d^{2}\log n)$ </tex-math></inline-formula>, rather than <inline-formula> <tex-math notation="LaTeX">$\Theta (d\log n)$ </tex-math></inline-formula> as in the case of classical group-testing. Some of our techniques may be of independent interest – in particular our achievability requires a delicate saddle-point approximation, our impossibility proof relies on a novel bound relating the mutual information of pair of random variables with the mean and variance of a specific function, and as a by-product of our proof showing that our sample-complexity upper and lower bounds are close we derive novel structural results about monotone functions.
In the problem of classical group testing one aims to identify a small subset (of size <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula>) of diseased individuals/defective items in a large population (of size <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>). This process is based on a minimal number of suitably-designed group tests on subsets of items, where the test outcome is positive iff the given test contains at least one defective item. Motivated by physical considerations, such as scenarios with imperfect test apparatus, we consider a generalized setting that includes as special cases multiple other group-testing-like models in the literature. In our setting the test outcome is governed by an arbitrary <italic>monotonically increasing</italic> (stochastic) test function <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula>, with the test outcome being positive with probability <inline-formula> <tex-math notation="LaTeX">$f(x)$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$x$ </tex-math></inline-formula> is the number of defectives tested in that pool. This formulation subsumes as special cases a variety of noiseless and noisy group-testing models in the literature. Our main contributions are as follows. Firstly, for any monotone test function <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula> we present a non-adaptive scheme that with probability <inline-formula> <tex-math notation="LaTeX">$1-\varepsilon $ </tex-math></inline-formula> identifies all defective items. Our scheme requires at most <inline-formula> <tex-math notation="LaTeX">${\mathcal{ O}}\left ({{\Psi (f)} d\log \left ({\frac {n}{\varepsilon }}\right)}\right)$ </tex-math></inline-formula> tests, where <inline-formula> <tex-math notation="LaTeX">${\Psi (f)}$ </tex-math></inline-formula> is a suitably defined “sensitivity parameter” of <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula>, and is never larger than <inline-formula> <tex-math notation="LaTeX">${\mathcal{ O}}(d^{1+o(1)})$ </tex-math></inline-formula>, but indeed can be substantially smaller for a variety of <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula>. Secondly, we argue that any non-adaptive group testing scheme needs at least <inline-formula> <tex-math notation="LaTeX">$\Omega \left ({(1-\varepsilon) {\psi (f)} d\log \left ({\frac {n} d}\right)}\right)$ </tex-math></inline-formula> tests to ensure high reliability recovery. Here <inline-formula> <tex-math notation="LaTeX">${\psi (f)}$ </tex-math></inline-formula> is a suitably defined “concentration parameter” of <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula>, and <inline-formula> <tex-math notation="LaTeX">${\psi (f)}\in \Omega {(1)}$ </tex-math></inline-formula>. Thirdly, we prove that our sample-complexity bounds for generalized group testing are information-theoretically near-optimal for a variety of sparse-recovery group-testing models in the literature. That is, for <italic>any</italic> “noisy” test function <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula> (i.e., <inline-formula> <tex-math notation="LaTeX">$0 < f(0) < f(d) < 1$ </tex-math></inline-formula>), and for a variety of “(one-sided) noiseless” test functions <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula> (i.e., either <inline-formula> <tex-math notation="LaTeX">$f(0)=0$ </tex-math></inline-formula>, or <inline-formula> <tex-math notation="LaTeX">$f(d)=1$ </tex-math></inline-formula>, or both) studied in the literature we show that <inline-formula> <tex-math notation="LaTeX">$\frac {\Psi (f)} {\psi (f)} \in \Theta (1)$ </tex-math></inline-formula>. As a by-product we tightly characterize the heretofore open information-theoretic order-wise sample-complexity for the well-studied model of threshold group-testing. For general (near)-noiseless test functions <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula> we show that <inline-formula> <tex-math notation="LaTeX">$\frac {\Psi (f)} {\psi (f)} \in {\mathcal{ O}}(d^{1+o(1)})$ </tex-math></inline-formula>. We also demonstrate a “natural” test-function <inline-formula> <tex-math notation="LaTeX">$f(\cdot)$ </tex-math></inline-formula> whose sample complexity scales “extremally” as <inline-formula> <tex-math notation="LaTeX">$\Theta (d^{2}\log n)$ </tex-math></inline-formula>, rather than <inline-formula> <tex-math notation="LaTeX">$\Theta (d\log n)$ </tex-math></inline-formula> as in the case of classical group-testing. Some of our techniques may be of independent interest – in particular our achievability requires a delicate saddle-point approximation, our impossibility proof relies on a novel bound relating the mutual information of pair of random variables with the mean and variance of a specific function, and as a by-product of our proof showing that our sample-complexity upper and lower bounds are close we derive novel structural results about monotone functions.