2017/09/26 by Hashemi, Abolfazl, Ghasemi, Mahsa, Vikalo, Haris +1 · 2 citations
#FOS: Electrical engineering #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · doi:10.48550/arxiv.1709.08823
We study the problem of scheduling sensors in a resource-constrained linear dynamical system, where the objective is to select a small subset of sensors from a large network to perform the state estimation task. We formulate this problem as the maximization of a monotone set function under a matroid constraint. We propose a randomized greedy algorithm that is significantly faster than state-of-the-art methods. By introducing the notion of curvature which quantifies how close a function is to being submodular, we analyze the performance of the proposed algorithm and find a bound on the expected mean square error (MSE) of the estimator that uses the selected sensors in terms of the optimal MSE. Moreover, we derive a probabilistic bound on the curvature for the scenario where\colorblack the measurements are i.i.d. random vectors with bounded ℓ2 norm. Simulation results demonstrate efficacy of the randomized greedy algorithm in a comparison with greedy and semidefinite programming relaxation methods.