On the Submodularity of Linear Experimental Design
Matthias Seeger · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2009
Here, I review facts that are most probably known, namely that the information gain criterion used to drive experimental design in a linear-Gaussian model is submodular, so that a well-known approximation guarantee holds for the sequential greedy algorithm. The criterion is equal to a certain mutual information, which is not submodular in general. I point out the high potential relevance of obtaining approximation guarantees for nonlinear experimental design as well.