We study non-adaptive pooling strategies for detection of rare faulty items. Given a binary sparse N dimensional signal x, how to construct a sparse binary M × N pooling matrix F such that the signal can be reconstructed from the smallest possible number M of measurements y = Fx? We show that a very small number of measurements is possible for random spatially coupled design of pools F. Our design might find application in genetic screening or compressed genotyping. We show that our results are robust with respect to the uncertainty in the matrix F when some elements are mistaken.
Note that when the number of faulty items @math is much smaller than @math , then another line of works should be considered. The best polynomial time non-adaptive algorithms known for the coin weighting problem then need @math measurements @cite_10 . Our approach is thus useful only in regimes where the number of faulty items is larger than @math . Another problem that is closely related to non-adaptive pooling as considered here is the sparse code division multiple access (CDMA) method @cite_21 @cite_20 ; with the difference that the signal @math is not sparse and that there is usually a considerable Gaussian additive noise on the measurement vector @math . The goal in CDMA is not to minimize the number of measurements @math (the number of chips), but to support the largest possible amount of noise. Spatial coupling was investigated for (dense) CDMA in @cite_8 @cite_5 .
@cite_8 @cite_21 @cite_5 @cite_10 @cite_20
2154935897 2078780937 2164196863 2061761364 2144015943
Demodulation in a random multiple access channel is considered where the signals are chosen uniformly randomly with unit energy. It is shown that by lifting (replicating) the graph of this system and randomizing the graph connections, a simple iterative cancellation demodulator achieves the same performance as an optimal symbol-by-symbol detector of the original system. The iterative detector has a complexity that is linear in the number of users, while the direct optimal approach is known to be NP-hard. However, the maximal system load of this lifted graph is limited to @math $ can go to infinity as the SNR goes to infinity. Our results apply to several well-documented system proposals, such as interleave-division multiple access, partitioned spreading, and certain forms of multiple-input multiple-output communications. Sparse code division multiple access (CDMA), a variation on the standard CDMA method in which the spreading (signature) matrix contains only a relatively small number of nonzero elements, is presented and analysed using methods of statistical physics. The analysis provides results on the performance of maximum likelihood decoding for sparse spreading codes in the large system limit. We present results for both cases of regular and irregular spreading matrices for the binary additive white Gaussian noise channel (BIAWGN) with a comparison to the canonical (dense) random spreading code. © 2007 IOP Publishing Ltd. proved that the belief-propagation (BP) threshold for low-density parity-check codes can be boosted up to the maximum-a-posteriori (MAP) threshold by spatial coupling. In this paper, spatial coupling is applied to randomly-spread code-division multiple-access (CDMA) systems in order to improve the performance of BP-based multiuser detection (MUD). Spatially-coupled CDMA systems can be regarded as multi-code CDMA systems with two transmission phases. The large-system analysis shows that spatial coupling can improve the BP performance, while there is a gap between the BP performance and the individually-optimal (IO) performance. Abstract We shall prove a generalization of a classic inequality of Erdos and Turan on B 2 -sequences of integers to B 2 -sequences of vectors with integer components. We improve a recent result by the author when the dimension tends to infinity. Code-division multiple access (CDMA) is the basis of a family of advanced air interfaces in current and future generation networks. The benefits promised by CDMA have not been fully realized partly due to the prohibitive complexity of optimal detection and decoding of many users communicating simultaneously using the same frequency band. From both theoretical and practical perspectives, this paper advocates a new paradigm of CDMA with sparse spreading sequences, which enables near-optimal multiuser detection using belief propagation (BP) with low-complexity. The scheme is in part inspired by capacity-approaching low-density parity-check (LDPC) codes and the success of iterative decoding techniques. Specifically, it is shown that BP-based detection is optimal in the large-system limit under many practical circumstances, which is a unique advantage of sparsely spread CDMA systems. Moreover, it is shown that, from the viewpoint of an individual user, the CDMA channel is asymptotically equivalent to a scalar Gaussian channel with some degradation in the signal-to-noise ratio (SNR). The degradation factor, known as the multiuser efficiency, can be determined from a fixed-point equation. The results in this paper apply to a broad class of sparse, semi-regular CDMA systems with arbitrary input and power distribution. Numerical results support the theoretical findings for systems of moderate size, which further demonstrate the appeal of sparse spreading in practical applications.