This paper considers a generalized version of the coin weighing problem with a spring scale that lies at the intersection of group testing and compressed sensing problems. Given a collection of @math coins of total weight @math (for a known integer @math ), where the weight of each coin is an unknown integer in the range of @math (for a known integer @math ), the problem is to determine the weight of each coin by weighing subsets of coins in a spring scale. The goal is to minimize the average number of weighings over all possible weight configurations. For @math , an adaptive bisecting weighing strategy is known to be optimal. However, even the case of @math , which is the simplest non-trivial case of the problem, is still open. For this case, we propose and analyze a simple and effective adaptive weighing strategy. A numerical evaluation of the exact recursive formulas, derived for the analysis of the proposed strategy, shows that this strategy requires about @math weighings on average. To the best of our knowledge, this is the first non-trivial achievable upper bound on the minimum expected required number of weighings for the case of @math . As @math grows unbounded, the proposed strategy, when compared to an optimal strategy within the commonly-used class of nested strategies, requires about @math less number of weighings on average; and in comparison with the information-theoretic lower bound, it requires at most about @math extra number of weighings on average.
We consider the quantitative group testing problem where the objective is to identify defective items in a given population based on results of tests performed on subsets of the population. Under the quantitative group testing model, the result of each test reveals the number of defective items in the tested group. The minimum number of tests achievable by nested test plans was established by Aigner and Schughart in 1985 within a minimax framework. The optimal nested test plan offering this performance, however, was not obtained. In this paper, we establish the optimal nested test plan in a closed form. This optimal nested test plan is also order optimal among all test plans as the population size approaches infinity. Using heavy-hitter detection as a case study, we show via simulation examples orders of magnitude improvement of the group testing approach over two prevailing sampling-based approaches in detection accuracy and counter consumption. Other applications include anomaly detection and wideband spectrum sensing in cognitive radio systems.