グループテスト
Since the measurements are dot products of v {\displaystyle {\textbf {v}}} , the equation M v = q {\displaystyle M{\textbf {v}}={\textbf {q}}} holds, where M {\displaystyle M} is a t × N {\displaystyle t\times N} matrix that describes the set of measurements that have been chosen and q {\displaystyle \mathbf {q} } is the set of measurement results. This construction shows that compressed sensing is a kind of 'continuous' group testing.
The primary difficulty in compressed sensing is identifying which entries are significant. Once that is done, there are a variety of methods to estimate the actual values of the entries. This task of identification can be approached with a simple application of group testing.
IEEE Transactions on Signal Processing 57 (7): 2479–2493. Bibcode: 2009ITSP...57.2479W. doi:10.1109/TSP.2009.2016892.
1 2 Berinde, R.; Gilbert, A. C.; Indyk, P.; Karloff, H.; Strauss, M. J. (September 2008). Combining geometry and combinatorics: A unified approach to sparse signal recovery. 798–805. arXiv:0804.4666. doi:10.1109/ALLERTON.2008.4797639. ISBN 978-1-4244-2925-7
↑ Indyk, Piotr (1 January 2008). “Explicit Constructions for Compressed Sensing of Sparse Signals”. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms: 30–33.
↑ “Origami Assays”. Origami Assays (2020年4月2日). 2020年4月7日閲覧。
↑ “Origami Assays”. Origami Assays (2020年4月2日). 2020年4月7日閲覧。
However, an important breakthrough occurred in 1972, with the introduction of the generalised binary-splitting algorithm. The generalised binary-splitting algorithm works by performing a binary search on groups that test positive, and is a simple algorithm that finds a single defective in no more than the information-lower-bound number of tests.
In scenarios where there are two or more defectives, the generalised binary-splitting algorithm still produces near-optimal results, requiring at most d − 1 {\displaystyle d-1} tests above the information lower bound where d {\displaystyle d} is the number of defectives.
The matrix representation makes it possible to prove some bounds on non-adaptive group testing. The approach mirrors that of many deterministic designs, where d {\displaystyle d} -separable matrices are considered, as defined below.
A binary matrix, M {\displaystyle M} , is called d {\displaystyle d} -separable if every Boolean sum (logical OR) of any d {\displaystyle d} of its columns is distinct. Additionally, the notation d ̄ {\displaystyle {\bar {d}}} -separable indicates that every sum of any of up to d {\displaystyle d} of M {\displaystyle M} 's columns is distinct.
A multiaccess channel is a communication channel that connects many users at once. Every user can listen and transmit on the channel, but if more than one user transmits at the same time, the signals collide, and are reduced to unintelligible noise. Multiaccess channels are important for various real-world applications, notably wireless computer networks and phone networks.
A prominent problem with multiaccess channels is how to assign transmission times to the users so that their messages do not collide. A simple method is to give each user their own time slot in which to transmit, requiring n {\displaystyle n} slots. (This is called time division multiplexing, or TDM.