Submodular Observation Selection and Information Gathering for Quadratic Models

We study the problem of selecting a subset of observations that enable accurate prediction of unknown parameters, i.e., the task of choosing the most informative observations from a potentially significantly larger set. This problem arises in a variety of settings in machine learning and signal processing including feature selection, phase retrieval, and target localization. For quadratic measurement models, the moment matrix is generally unknown and the practice of optimizing the so-called alphabetical selection criteria no longer guarantees selection of a near-optimal subset. Majority of prior work resorts to approximation techniques such as linearization of the measurement model to optimize the utility of an approximate moment matrix. In contrast, by exploiting a connection to the classical Van Trees' inequality, we derive new alphabetical optimality criteria without distorting the relational structure of the measurement model. We further show that under certain conditions on parameters of the problem these optimality criteria are monotone and (weak) submodular set functions. These results enable us to develop an efficient greedy observation selection algorithm uniquely tailored for quadratic models, and provide theoretical bounds on its achievable utility. Extensive numerical experiments demonstrate efficacy of the proposed framework.