Subset Selection for Gaussian Markov Random Fields

Given the joint distribution of a set of random variables (in the form of a Markov random field), we consider the problem of selecting a small subset of these variables to observe so as to accurately predict the remaining unobserved variables. We focus here on Gaussian processes(Rasmussen and Williams, 2006) on graphs, i.e., Gaussian Markov random fields(Gaussian MRFs). Our aim in this paper is to give a subset selection algorithm which, given a budget for the number of variables that can be observed, minimizes the expected squared prediction error averaged over all the variables. We are particularly interested in algorithms with provable guarantees on the prediction error. Our main focus is on Gaussian MRFs on trees and other treelike graphs, or to be precise, bounded tree-width graphs--such graphs have been widely studied in the context of inference, see, e.g., Sudderth (2002). We also consider a special class of Gaussian MRFs, called Gaussian free fields (or GFFs), which arise, among others, in computer vision, see, e.g., Szeliski (1990). We first explain the notation we use and formally state our problem before describing how our work relates to previous research.