When monitoring spatial phenomena, which are often modeled as Gaussian Processes (GPs), choosing sensor locations is a fundamental task. A common strategy is to place sensors at the points of highest entropy (variance) in the GP model. We propose a mutual information cri- teria, and show that it produces better placements. Fur- thermore, we prove that finding the configuration that maximizes mutual information is NP-complete. To ad- dress this issue, we describe a polynomial-time approx- imation that is within (1 − 1/e) of the optimum by ex- ploiting the submodularity of our criterion. This algorithm is extended to handle local structure in the GP, yielding significant speedups. We demonstrate the advantages of our approach on two real-world data sets.

@inproceedings{guestrin05near,
	author = {Carlos Guestrin and Andreas Krause and Ajit Singh},
	booktitle = {International Conference on Machine Learning (ICML)},
	month = {August},
	title = {Near-optimal Sensor Placements in {G}aussian Processes},
	year = {2005}}