Adaptive Boolean compressive sensing by using multi-armed bandit

Abstract

A new method for solving adaptive Boolean compressive sensing is proposed. By greedy maximization of an expected information gain, a conventional method controls the pool-size for adaptive Boolean compressive sensing. However, the conventional greedy method has the drawback that it has no guarantee of convergence to the optimal strategy. To solve the problem, based on the multi-armed bandit, the proposed method controls the pool-size adaptively. The information gain of the conventional greedy method is rewritten as the reward of the multi-armed bandit, and the multi-armed bandit is introduced into adaptive Boolean compressive sensing. Experimental results indicate that the correct rate of exact recovery of the proposed method converges to 1 fast without prior knowledge about the number of defective items and that the proposed method outperforms the conventional greedy method in the case that the number of defective items is large.