An Improved Greedy Algorithm for Subset Selection in Linear Estimation

Shamak Dutta, N. Wilde, Stephen L. Smith

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review


In this paper, we consider a subset selection problem in a spatial field where we seek to find a set of k locations whose observations provide the best estimate of the field value at a finite set of prediction locations. The measurements can be taken at any location in the continuous field, and the covariance between the field values at different points is given by the widely used squared exponential covariance function. One approach for observation selection is to perform a grid discretization of the space and obtain an approximate solution using the greedy algorithm. The solution quality improves with a finer grid resolution but at the cost of increased computation. We propose a method to reduce the computational complexity, or conversely to increase solution quality, of the greedy algorithm by considering a search space consisting only of prediction locations and centroids of cliques formed by the prediction locations. We demonstrate the effectiveness of our proposed approach in simulation, both in terms of solution quality and runtime.
Original languageEnglish
Title of host publicationProceedings European Control Conference (ECC) 2022
ISBN (Electronic)978-3-907144-07-7
ISBN (Print)978-1-6654-9733-6
Publication statusPublished - 2022
Event2022 European Control Conference (ECC) - London, United Kingdom
Duration: 12 Jul 202215 Jul 2022

Publication series

Name2022 European Control Conference, ECC 2022


Conference2022 European Control Conference (ECC)
Country/TerritoryUnited Kingdom


  • Greedy algorithms
  • runtime
  • costs
  • Computational modeling
  • Europe
  • Estimation
  • Computational complexity


Dive into the research topics of 'An Improved Greedy Algorithm for Subset Selection in Linear Estimation'. Together they form a unique fingerprint.

Cite this