グループテスト
The definite defectives method (DD) is an extension of the COMP algorithm that attempts to remove any false positives. Performance guarantees for DD have been shown to strictly exceed those of COMP.
The decoding step uses a useful property of the COMP algorithm: that every item that COMP declares non-defective is certainly non-defective (that is, there are no false negatives). It proceeds as follows.
First the COMP algorithm is run, and any non-defectives that it detects are removed. All remaining items are now "possibly defective".
Since it is always possible to resort to individual testing by setting S j = { j } {\displaystyle S_{j}=\{j\}} for each 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n} , it must be that that t ̄ ( d , n ) ≤ n {\displaystyle {\bar {t}}(d,n)\leq n} . Also, since any non-adaptive testing procedure can be written as an adaptive algorithm by simply performing all the tests without regard to their outcome, t ( d , n ) ≤ t ̄ ( d , n ) {\displaystyle t(d,n)\leq {\bar {t}}(d,n)} .
グループテストを実行するためのスキームには単純なものも複雑なものもあり、ひとつのスキームの中の各段階の検査も異なる場合がある。次の段階の検査法が前の段階の検査結果によって変わるようなスキームは適応的手順(adaptive procedure)と呼ばれる一方, すべての検査法が事前に決まるように設計されたスキームは「非適応的手順」(non-adaptive procedure)と呼ばれる。非適応的手順に含まれる検査のスキームの構造は「プーリング設計」として知られている(訳注: この部分の意味が原文ではわからない)。
グループテストには、統計学、生物学、コンピュータサイエンス、医学、エンジニアリング、サイバーセキュリティなど、多くの応用がある。これらの検査スキームに対する関心は、近年もHuman Genome Projectによって再燃している 。
Here a group test produces a complex number: the sum of the entries that are tested. The outcome of a test is called positive if it produces a complex number with a large magnitude, which, given the assumption that the significant entries are sparse, indicates that at least one significant entry is contained in the test.
There are explicit deterministic constructions for this type of combinatorial search algorithm, requiring d 2 ( log 2  log 2  N ) O ( 1 ) {\displaystyle d2^{(\log _{2}\log _{2}N)^{O(1)}}} measurements. However, as with group-testing, these are sub-optimal, and random constructions (such as COMP) can often recover f {\displaystyle f} sub-linearly in N {\displaystyle N} .
Using the properties of d {\displaystyle d} -separable and d {\displaystyle d} -disjunct matrices the following can be shown for the problem of identifying d {\displaystyle d} defectives among n {\displaystyle n} total items.
The number of tests needed for an asymptotically small average probability of error scales as O ( d log 2  n ) {\displaystyle O(d\log _{2}n)} .
The number of tests needed for an asymptotically small maximum probability of error scales as O ( d 2 log 2  n ) {\displaystyle O(d^{2}\log _{2}n)} .
The number of tests needed for a zero probability of error scales as O ( d 2 log 2  n log 2  d ) {\displaystyle O\left({\frac {d^{2}\log _{2}n}{\log _{2}d}}\right)} .
Thus each column of M {\displaystyle M} represents an item and each row represents a test, with a 1 {\displaystyle 1} in the ( i , j ) -th {\displaystyle (i,j){\textrm {-th}}} entry indicating that the i -th {\displaystyle i{\textrm {-th}}} test included the j -th {\displaystyle j{\textrm {-th}}} item and a 0 {\displaystyle 0} indicating otherwise.
As well as the vector x {\displaystyle \mathbf {x} } (of length n {\displaystyle n} ) that describes the unknown defective set, it is common to introduce the result vector, which describes the results of each test.
Let t {\displaystyle t} be the number of tests performed by a non-adaptive algorithm.