Submodular Observation Selection and Information Gathering for Quadratic Models

Abolfazl Hashemi, Mahsa Ghasemi, Haris Vikalo, Ufuk Topcu
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:2653-2662, 2019.

Abstract

We study the problem of selecting most informative subset of a large observation set to enable accurate estimation of unknown parameters. This problem arises in a variety of settings in machine learning and signal processing including feature selection, phase retrieval, and target localization. Since for quadratic measurement models the moment matrix of the optimal estimator is generally unknown, majority of prior work resorts to approximation techniques such as linearization of the observation model to optimize the alphabetical optimality criteria of an approximate moment matrix. Conversely, by exploiting a connection to the classical Van Trees’ inequality, we derive new alphabetical optimality criteria without distorting the relational structure of the observation 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-hashemi19a, title = {Submodular Observation Selection and Information Gathering for Quadratic Models}, author = {Hashemi, Abolfazl and Ghasemi, Mahsa and Vikalo, Haris and Topcu, Ufuk}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {2653--2662}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/hashemi19a/hashemi19a.pdf}, url = {https://proceedings.mlr.press/v97/hashemi19a.html}, abstract = {We study the problem of selecting most informative subset of a large observation set to enable accurate estimation of unknown parameters. This problem arises in a variety of settings in machine learning and signal processing including feature selection, phase retrieval, and target localization. Since for quadratic measurement models the moment matrix of the optimal estimator is generally unknown, majority of prior work resorts to approximation techniques such as linearization of the observation model to optimize the alphabetical optimality criteria of an approximate moment matrix. Conversely, by exploiting a connection to the classical Van Trees’ inequality, we derive new alphabetical optimality criteria without distorting the relational structure of the observation 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.} }
Endnote
%0 Conference Paper %T Submodular Observation Selection and Information Gathering for Quadratic Models %A Abolfazl Hashemi %A Mahsa Ghasemi %A Haris Vikalo %A Ufuk Topcu %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-hashemi19a %I PMLR %P 2653--2662 %U https://proceedings.mlr.press/v97/hashemi19a.html %V 97 %X We study the problem of selecting most informative subset of a large observation set to enable accurate estimation of unknown parameters. This problem arises in a variety of settings in machine learning and signal processing including feature selection, phase retrieval, and target localization. Since for quadratic measurement models the moment matrix of the optimal estimator is generally unknown, majority of prior work resorts to approximation techniques such as linearization of the observation model to optimize the alphabetical optimality criteria of an approximate moment matrix. Conversely, by exploiting a connection to the classical Van Trees’ inequality, we derive new alphabetical optimality criteria without distorting the relational structure of the observation 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.
APA
Hashemi, A., Ghasemi, M., Vikalo, H. & Topcu, U.. (2019). Submodular Observation Selection and Information Gathering for Quadratic Models. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:2653-2662 Available from https://proceedings.mlr.press/v97/hashemi19a.html.

Related Material