Greedy Sensor Placement With Cost Constraints

Emily Clark, Travis Askham, Steven L. Brunton, J. Nathan KutzIEEE Sensors Journal 2018 · DOI

TL;DR

This paper introduces a greedy algorithm for optimally placing sensors when each sensor has an associated cost. By extending a well-established QR-based method, they demonstrate how to balance reconstruction accuracy with sensor budget across various applications, finding that simple pre-processing can significantly impact performance.

What Problem Does This Paper Address?

Designing systems that rely on sensor data often involves a trade-off between the number of sensors used and the overall cost. This is particularly true in industrial products, scientific experiments, and monitoring systems where sensors can be expensive to acquire, install, or maintain. The challenge is to select sensor locations that provide the best possible reconstruction of a system's state while staying within a given budget. Traditional methods often focus on minimizing reconstruction error for a fixed number of sensors, but they don't explicitly account for varying sensor costs or the ability to explore the cost-error trade-off landscape.

Methods

The core of this work is an extension of the column-pivoted QR decomposition algorithm, a standard technique for finding optimal sensor placements when all sensors have equal cost. The authors adapt this by introducing a cost-weighting parameter ($\gamma$) into the greedy selection process. This parameter allows the algorithm to balance the desire for accurate reconstruction (minimizing error) with the need to reduce cost (avoiding expensive sensor locations).

The algorithm iteratively selects sensor locations. At each step, it considers not only how much a potential sensor would reduce the reconstruction error but also its associated cost. This greedy approach, guided by $\gamma$, aims to find a near-optimal set of sensor locations that satisfy a cost constraint. The paper also explores different pre-processing techniques for the data before applying the sensor placement algorithm, including using raw data, randomized linear combinations of data, and singular value decomposition (SVD) modes.

Datasets

The proposed algorithm and its variations were evaluated on three distinct datasets:

  • Extended Yale Face Database B: A dataset of facial images used for facial recognition.
  • NOAA Optimal Interpolation (OI) Sea Surface Temperature (SST) v2: A dataset of weekly global sea surface temperature measurements.
  • Fluid flow behind a cylinder: Simulation data representing vortex shedding from a stationary cylinder.

The paper uses a standard train/test split approach for evaluation, with cross-validation performed to ensure robustness.

Key Insights and Ideas

  • Cost-Aware Greedy Selection: The introduction of a cost-weighting parameter ($\gamma$) into the QR-based greedy algorithm provides a principled way to explore the cost-error trade-off, allowing for the selection of sensor locations that are both informative and economical.
  • Pre-processing Matters (and SVD isn't always best): The choice of pre-processing significantly impacts sensor placement performance. Surprisingly, for datasets with slow singular value decay, using raw data or randomized linear combinations often outperforms the commonly used SVD-based approach, especially when a larger number of sensors are placed.
  • Overfitting with SVD: For datasets with slow singular value decay, SVD modes can lead to overfitting, where the reconstruction error initially decreases but then increases as more modes are added, even before reaching the theoretical noise threshold.
  • Cost-Error Landscapes: The paper effectively visualizes the trade-off between sensor cost and reconstruction error using cost-error landscapes, providing valuable insights for decision-making in practical applications.

Key Results

  • The proposed QR-based greedy algorithm with cost constraints successfully identifies sensor locations that significantly reduce cost while maintaining near-optimal reconstruction performance across the tested datasets.
  • For datasets with slow singular value decay (like sea surface temperature and eigenfaces), using raw data or randomized linear combinations for pre-processing generally yielded better results than SVD modes, especially for a larger number of sensors.
  • Randomized linear combinations were found to be a good compromise for reducing problem size and achieving good performance, outperforming SVD modes in many scenarios.
  • The algorithm demonstrated scalability, making it suitable for high-dimensional problems.

Limitations and Future Work

  • Pathological Cases for QR: While the column-pivoted QR algorithm is generally robust, the paper acknowledges that pathological examples exist where its worst-case behavior might be observed.
  • Combined Pre-processing: The authors suggest exploring pre-processing methods that might combine the benefits of SVD at low sensor counts with the advantages of raw data or randomized combinations at higher counts.
  • Further Exploration of SVD Overfitting: The unexpected overfitting behavior observed with SVD modes for slow-decaying singular value datasets warrants further investigation.
  • Practical Applications: The paper highlights the algorithm's applicability to various fields like manufacturing, atmospheric sensing, and fluid flow sensing, suggesting future work in tailoring the algorithm to specific application constraints.

Summary updated

Abstract

The problem of optimally placing sensors under a cost constraint arises naturally in the design of industrial and commercial products, as well as in scientific experiments. We consider a relaxation of the full optimization formulation of this problem and then extend a well-established greedy algorithm for the optimal sensor placement problem without cost constraints. We demonstrate the effectiveness of this algorithm on the datasets related to facial recognition, climate science, and fluid mechanics. This algorithm is scalable and often identifies sparse sensors with near-optimal reconstruction performance, while dramatically reducing the overall cost of the sensors. We find that the cost-error landscape varies by application, with intuitive connections to the underlying physics. In addition, we include experiments for various pre-processing techniques and find that a popular technique based on the singular value decomposition is often suboptimal.
BibTeX
@article{clark2018greedy,
  author = {Emily Clark and Travis Askham and Steven L. Brunton and J. Nathan Kutz},
  title = {{Greedy Sensor Placement With Cost Constraints}},
  journal = {IEEE Sensors Journal},
  year = {2018},
  doi = {10.1109/jsen.2018.2887044},
}

Loading related content...

Figure