Monte Carlo Tree Search for Binary Inverse Problems with $O(1)$ Measurements

This paper considers the problem of recovering a binary-valued signal in the extreme compression regime when only a single real-valued linear measurement of the signal is available. Recent works have demonstrated that exact recovery under such extreme compression is indeed possible using suitable pre-processing that involves storing a search tree in memory and efficiently traversing it in linear time. However, the tree still requires exponential memory for storage. For practical settings where memory is scarce, we take first steps towards developing an efficient randomized search heuristic for binary compressed sensing based on the popular Monte Carlo Tree Search (MCTS) framework. We propose novel modifications to MCTS based on the problem structure that allows early pruning of the search tree and further guides MCTS to probe only relevant parts of the solution space. We demonstrate the efficacy of our approach through simulations and discuss various design choices.