Randomized Greedy Sensor Selection: Leveraging Weak Submodularity

We study the problem of estimating a random process from the observations collected by a network of sensors that operate under resource constraints. When the dynamics of the process and sensor observations are described by a state-space model and the resource are unlimited, the conventional Kalman f...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on automatic control 2021-01, Vol.66 (1), p.199-212
Main Authors: Hashemi, Abolfazl, Ghasemi, Mahsa, Vikalo, Haris, Topcu, Ufuk
Format: Article
Language:English
Subjects:
Combinatorial analysis
Covariance matrices
Greedy algorithms
Kalman filtering
Kalman filters
Linear programming
Maximization
Mean square error methods
Noise measurement
Optimization
Radar tracking
Random processes
Semidefinite programming
sensor networks
sensor selection
Sensors
State space models
Upper bounds
weak submodularity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the problem of estimating a random process from the observations collected by a network of sensors that operate under resource constraints. When the dynamics of the process and sensor observations are described by a state-space model and the resource are unlimited, the conventional Kalman filter provides the minimum mean square error (MMSE) estimates. However, at any given time, restrictions on the available communications bandwidth and computational capabilities and/or power impose a limitation on the number of network nodes, whose observations can be used to compute the estimates. We formulate the problem of selecting the most informative subset of the sensors as a combinatorial problem of maximizing a monotone set function under a uniform matroid constraint. For the MMSE estimation criterion, we show that the maximum elementwise curvature of the objective function satisfies a certain upper-bound constraint and is, therefore, weak submodular. Building upon the work of Mirzasoleiman et al. on submodular maximization, we develop an efficient randomized greedy algorithm for sensor selection and establish guarantees on the estimator's performance in this setting. Extensive simulation results demonstrate the efficacy of the randomized greedy algorithm compared to state-of-the-art greedy and semidefinite programming relaxation methods.
ISSN:0018-9286
1558-2523
DOI:10.1109/TAC.2020.2980924