Inspired by group testing algorithms and the coded computation paradigm, we propose and analyze a novel multiple access scheme for detecting active users in large-scale networks. The scheme consists of a simple randomized detection algorithm that uses computation coding as intermediate steps for computing logical disjunction functions over the multiple access channel (MAC). First we show that given an efficient MAC code for disjunction computation the algorithm requires @math decision steps for detecting @math active users out of @math users. Subsequently we present a simple suboptimal code for a class of MACs with arbitrarily varying sub-gaussian noise that uniformly requires @math channel uses for solving the activity detection problem. This shows that even in the presence of noise an efficient detection of active users is possible. Our approach reveals that the true crux of the matter lies in constructing efficient codes for computing disjunctions over a MAC.
@cite_5: We investigate recovery of nonnegative vectors from non-adaptive compressive measurements in the presence of noise of unknown power. In the absence of noise, existing results in the literature identify properties of the measurement that assure uniqueness in the non-negative orthant. By linking such uniqueness results to nullspace properties, we deduce uniform and robust compressed sensing guarantees for nonnegative least squares. No l1-regularization is required. As an important proof of principle, we establish that m x n random i.i.d. 0 1-valued Bernoulli matrices obey the required conditions with overwhelming probability provided that m=O(slog(n s)). We achieve this by establishing the robust nullspace property for random 0 1-matrices - a novel result in its own right. Our analysis is motivated by applications in wireless network activity detection.
@cite_4: 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.
The problem of user activity detection in large-scale networks has been already addressed in the context of compressive sensing in @cite_4 @cite_5 where the authors show the existence of a non-adaptive optimal activity detection strategy. The approach in @cite_4 @cite_5 relies heavily on methods from high dimensional probability and on methods for estimating certain partial sums affected by noise.