We consider the nonadaptive group testing with @math items, of which @math are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick @math tests uniformly at random with replacement and place the item in those tests. We analyze the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires roughly 23 fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as combinatorial orthogonal matching pursuit and definite defectives (DD). This gives the best known nonadaptive group testing performance for @math and the best proven performance with a practical decoding algorithm for all @math . We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when @math . We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes.
Similarly, other subsequent papers have proposed forms of constant or near-constant column weight designs @cite_12 @cite_9 @cite_0 @cite_42 , but to our knowledge, none of these works provide non-trivial achievable rates for the vanishing error probability criterion, which is the focus of the present paper. Chan @cite_38 considered constant row weight designs, and found no improvement over Bernoulli designs.
@cite_38 @cite_9 @cite_42 @cite_0 @cite_12
2542299727 2037982184 2461651802 2160051394
We investigate recovery of nonnegative vectors from nonadaptive compressive measurements in the presence of noise of unknown power. It is known in the literature that under additional assumptions on the measurement design recovery of such vectors is possible with nonnegative least squares without any regularization. We show that uniqueness results known for the noiseless case carry over to robust guarantees in the noisy setting. We present guarantees which hold instantaneously by connecting the relation to the robust nullspace property. As an important example, we prove that an m × n random iid. 0 1-valued Bernoulli matrix with m = O(s log(n)) rows admits the robust nullspace property with high probability and meets the design requirements for nonnegative least squares recovery. Our analysis is motivated by applications in wireless network activity detection. In a celebrated work by Hoeffding [J. Amer. Statist. Assoc. 58 (1963) 13-30], several inequalities for tail probabilities of sums M n = X 1 + ... + X n of bounded independent random variables X j were proved. These inequalities had a considerable impact on the development of probability and statistics, and remained unimproved until 1995 when Talagrand [Inst. Hautes Etudes Sci. Publ. Math. 81 (1995a) 73-205] inserted certain missing factors in the bounds of two theorems. By similar factors, a third theorem was refined by Pinelis [Progress in Probability 43 (1998) 257-314] and refined (and extended) by me. In this article, I introduce a new type of inequality. Namely, I show that P M n ≥ x ≤ cP S n ≥ x , where c is an absolute constant and S n = e 1 + ... + e n is a sum of independent identically distributed Bernoulli random variables (a random variable is called Bernoulli if it assumes at most two values). The inequality holds for those x ∈ Ρ where the survival function x → P S n ≥ x has a jump down. For the remaining x the inequality still holds provided that the function between the adjacent jump points is interpolated linearly or log-linearly. If it is necessary, to estimate P S n ≥ x special bounds can be used for binomial probabilities. The results extend to martingales with bounded differences. It is apparent that Theorem 1.1 of this article is the most important. The inequalities have applications to measure concentration, leading to results of the type where, up to an absolute constant, the measure concentration is dominated by the concentration in a simplest appropriate model, such results will be considered elsewhere. We observe that Sturm's error bounds readily imply that for semidefinite feasibility problems, the method of alternating projections converges at a rate of @math O(k-12d+1-2), where d is the singularity degree of the problem--the minimal number of facial reduction iterations needed to induce Slater's condition. Consequently, for almost all such problems (in the sense of Lebesgue measure), alternating projections converge at a worst-case rate of @math O(1k). Consider a Bernoulli-Gaussian complex n-vector whose components are Vi = XiBi, with Xi C N(0, Px) and binary Bi mutually independent and iid across i. This random q-sparse vector is multiplied by a square random matrix U, and a randomly chosen subset, of average size n p, p ∈ [0,1], of the resulting vector components is then observed in additive Gaussian noise. We extend the scope of conventional noisy compressive sampling models where U is typically a matrix with iid components, to allow U satisfying a certain freeness condition. This class of matrices encompasses Haar matrices and other unitarily invariant matrices. We use the replica method and the decoupling principle of Guo and Verdu, as well as a number of information-theoretic bounds, to study the input-output mutual information and the support recovery error rate in the limit of n → ∞. We also extend the scope of the large deviation approach of Rangan and characterize the performance of a class of estimators encompassing thresholded linear MMSE and l1 relaxation.