On the complexity of information planning in Gaussian models

We analyze the complexity of evaluating information rewards for measurement selection in sparse graphical models under the assumption that measurements are drawn from a limited number of nodes subject to a finite budget. Previous analyses [1, 2, 3] exploit the submodular property of conditional mutual information to demonstrate that greedy measurement selection come with near-optimal guarantees As noted in [4] typical formulations assume oracle value models. However, [1, 2, 5] allude to a more significant source of complexity, namely computing the measurement reward. Here, we focus on Gaussian models and show that by exploiting sparsity in the measurement model, the complexity of planning is substantially reduced. We also demonstrate that by utilizing the information form additional significant reductions in complexity may be realized.