Skip to main content

Clustered Greedy Algorithm for Large-Scale Sensor Selection

Kaushani Majumder (Indian Institute of Technology, Bombay); Sibi Raj B. Pillai (Indian Institute of Technology, Bombay); Satish Mulleti (Indian Institute of Technology Bombay, India)

  • SPS
    Members: Free
    IEEE Members: $11.00
    Non-members: $15.00
07 Jun 2023

In the problem of sensor selection, observations from $L$ out of $N$ sensors are chosen for data estimation, with the objective of minimizing an error metric. It is well known that a greedy selection (GS) method can achieve an error metric which is not worse than $1/e$ from that of the optimal algorithm, for a wide class of sensor selection problems. However, GS does not scale well with the problem size. The available accelerators to GS also fail to solve large scale problems in any reasonable time. In this paper, we propose a clustering-based solution called clustered greedy selection (CGS) which not only reduces the problem size, but also achieves a similar performance to GS. CGS first clusters the sensors based on a similarity metric and then applies GS on this lower dimensional problem. The method seems particularly suitable when the number of sensors to be selected is much less than the total number of sensors. We provide bounds for the worst-case performance of CGS and experimentally validate our results on some linear models.

More Like This

  • SPS
    Members: Free
    IEEE Members: $11.00
    Non-members: $15.00
  • SPS
    Members: Free
    IEEE Members: $11.00
    Non-members: $15.00
  • SPS
    Members: Free
    IEEE Members: $11.00
    Non-members: $15.00