- Disjunct matrix
-
Disjunct and separable matrices play a pivotal role in the mathematical area of non-adaptive group testing. This area investigates efficient designs and procedures to identify 'needles in haystacks' by conducting the tests on groups of items instead of each item alone. The main concept is that if there are very few special items (needles) and the groups are constructed according to certain combinatorial guidelines, then one can test the groups and find all the needles. This can reduce the cost and the labor associated with of large scale experiments.
The grouping pattern can be represented by a binary matrix, where each column represents an item and each row represents a pool. The symbol '1' denotes participation in the pool and '0' absence from a pool. The d-disjuntness and the d-separability of the matrix describe sufficient condition to identify d special items.
In a matrix that is d-separable, the Boolean sum of every d columns is unique. In a matrix that is d-disjunct the Boolean sum of every d columns does not contain any other column in the matrix. Theoretically, for the same number of columns (items), one can construct d-separable matrices with fewer rows (tests) than d-disjunct. However, designs that are based on d-separable are less applicable since the decoding time to identify the special items is exponential. In contrast, the decoding time for d-dijunct matrices is polynomial.
Contents
d-separable
Definition: A matrix M is d-separable if and only if where such that
Decoding algorithm
First we will describe another way to look at the problem of group testing and how to decode it from a different notation. We can give a new interpretation of how group testing works as follows:
Group testing: Given input M and such that output
- Take Mj to be the jth column of M
- Define so that Mj(i) = 1 if and only if
- This gives that
This formalizes the relation between and the columns of M and in a way more suitable to the thinking of d-separable and d-disjunct matrices. The algorithm to decode a d-separable matrix is as follows:
Given a matrix M such that M is d-separable:
- For each such that check if
This algorithm runs in time .
d-disjunct
In literature disjunct matrices are also called super-imposed codes and d-cover-free families.
Definition: A t x n matrix M is d-disjunct if such that , such that Mi,j = 1 but . Denoting Ma is the ath column of M and where Ma(b) = 1 if and only if gives that M is d-disjunct if and only if
Claim: M is d-disjunct implies M is d-separable
Proof: (by contradiction) Let M be a t x n d-disjunct matrix. Assume for contradiction that M is not d-separable. Then there exists and with such that . This implies that such that . This contradicts the fact that M is d-disjunct. Therefore M is d-separable.
Decoding algorithm
The algorithm for d-separable matrices was still a polynomial in n. The following will give a nicer algorithm for d-disjunct matrices which will be a d multiple instead of raised to the power of d given our bounds for t. The algorithm is as follows in the proof of the following lemma:
Lemma 1: There exists an time decoding for any d-disjunct t x n matrix.
- Observation 1: For any matrix M and given if it implies such that Mi,j = 1 and where and . The opposite is also true. If it implies if Mi,j = 1 then . This is the case because is generated by taking all of the logical or of the 's where Mi,j = 1.
- Observation 2: For any d-disjunct matrix and every set where and for each where there exists some i where such that Mi,j = 1 but . Thus, if then .
Proof of Lemma 1: Given as input use the following algorithm:
- For each set
- For , if then for all , if Mi,j = 1 set
By Observation 1 we get that any position where mathbfri = 0 the appropriate 's will be set to 0 by step 2 of the algorithm. By Observation 2 we have that there is at least one i such that if is supposed to be 1 then Mi,j = 1 and, if is supposed to be 1, it can only be the case that as well. Therefore step 2 will never assign the value 0 leaving it as a 1 and solving for . This takes time overall.
Upper bounds for non-adaptive group testing
The results for these upper bounds rely mostly on the properties of d-disjunct matrices. Not only are the upper bounds nice, but from Lemma 1 we know that there is also a nice decoding algorithm for these bounds. First the following lemma will be proved since it is relied upon for both constructions:
Lemma 2: Given let M be a matrix and:
for some integers then M is -disjunct.
Note: these conditions are stronger than simply having a subset of size d but rather applies to any pair of columns in a matrix. Therefore no matter what column i that is chosen in the matrix, that column will contain at least wmin 1's and the total number of shared 1's by any two columns is amax .
Proof of Lemma 2: Fix an arbitrary and a matrix M. There exists a match between if column i has a 1 in the same row position as in column j. Then the total number of matches is , i.e. a column j has a fewer number of matches than the number of ones in it. Therefore there must be a row with all 0s in S but a 1 in j.
We will now generate constructions for the bounds.
Randomized construction
This first construction will use a probabilistic argument to show the property wanted, in particular the Chernoff bound. Using this randomized construction gives that . The following lemma will give the result needed.
Theorem 1: There exists a random d-disjunct matrix with rows.
Proof of Theorem 1: Begin by building a random matrix M with t = cd2log n (where c will be picked later). It will be shown that M is Ω(d)-disjunct. First note that and let Mi,j = 1 independently with probability for and . Now fix . Denote the jth column of M as . Then the expectancy is . Using the Chernoff bound, with , gives if . Taking the union bound over all columns gives , . This gives , . Therefore with probability .
Now suppose and then . So . Using the Chernoff bound on this gives if . By the union bound over (j,k) pairs such that . This gives that and with probability . Note that by changing c the probability can be made to be . Thus . By setting d to be 4d, the above argument shows that M is d-disjunct.
Note that in this proof t = d2log n thus giving the upper bound of .
Strongly explicit construction
It is possible to prove a bound of using a strongly explicit code. Although this bound is worse by a logn factor it is preferable because this produces a strongly explicit construction instead of a randomized one.
Theorem 2: There exists a strongly explicit d-disjunct matrix with rows.
This proof will use the properties of concatenated codes along with the properties of disjunct matrices to construct a code that will satisfy the bound we are after.
Proof of Theorem 2: Let such that . Denote MC as the matrix with its ith column being . If C * can be found such that
- ,
then is -disjunct. To complete the proof another concept must be introduced. This concept uses code concatenation to obtain the result we want.
Kautz-Singleton '64
Let . Let Cout be a [q,k]q-Reed–Solomon code. Let such that for , where the 1 is in the ith position. Then n = qk, t = q2, and wmin = q.
---
Example: Let k = 1,q = 3,Cout = {(0,0,0),(1,1,1),(2,2,2)}. Below, MC denotes the matrix of codewords for Cout and denotes the matrix of codewords for , where each column is a codeword. The overall image shows the transition from the outer code to the concatenated code.
---
Divide the rows of into sets of size q and number them as where i indexes the set of rows and j indexes the row in the set. If then note that where . So that means . Since it gives that so let amax = k − 1. Since t = q2, the entries in each column of can be looked at as q sets of q entries where only one of the entries is nonzero (by definition of Cin) which gives a total of q nonzero entries in each column. Therefore wmin = q and (so is d-disjunct).
Now pick q and k such that (so ). Since qk = n we have . Since and t = q2 it gives that .
Thus we have a strongly explicit construction for a code that can be used to form a group testing matrix and so .
For non-adaptive testing we have shown that and we have that (i) (strongly explicit) and (ii) (randomized). As of recent work by Porat and Rothscheld they presented a explicit method construction (i.e. deterministic time but not strongly explicit) for [1], however it is not shown here. There is also a lower bound for disjunct matrices of [2][3][4] which is not shown here either.
See also
- Group testing
- Concatenated code
- Compressed sensing
Notes
- ^ Porat, E., & Rothschild, A. (2008). Explicit Non-adaptive Combinatorial Group Testing Schemes. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP) (pp. 748–759).
- ^ Dýachkov, A. G., & Rykov, V. V. (1982). Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii [Problems of Information Transmission], 18(3), 7–13.
- ^ Dýachkov, A. G., Rashad, A. M., & Rykov, V. V. (1989). Superimposed distance codes. Problemy Upravlenija i Teorii Informacii [Problems of Control and Information Theory], 18(4), 237–250.
- ^ Zoltan Furedi, On r-Cover-free Families, Journal of Combinatorial Theory, Series A, Volume 73, Issue 1, January 1996, Pages 172–173, ISSN 0097-3165, DOI: 10.1006/jcta.1996.0012. (http://www.sciencedirect.com/science/article/B6WHS-45NJMVF-39/2/172ef8c5c4aee2d85d1ddd56b107eef3)
References
Categories:
Wikimedia Foundation. 2010.