PaperlayerView exact revision on arXiv

Source-linked AI summary

Sensor Placement for Optimal Kalman Filtering: Fundamental Limits, Submodularity, and Algorithms

Vasileios Tzoumas, Ali Jadbabaie, George J. Pappas

arXiv:1509.08146v4math.OCcs.SYeess.SY

TL;DR

The paper asks how to select a small, fixed sensor set for Kalman estimation of interdependent dynamic states in the presence of process and measurement noise. It studies sensor-placement objectives based on log-det estimation error and develops approximation algorithms. The analysis establishes scaling limits and set-function properties, and the algorithms are applied to CO2 sequestration monitoring.

  • Problem

    How to place a small sensor set to estimate interdependent dynamic states under process and measurement noise, including when operational constraints limit sensor use.

    Source: §I · p. 1

  • Method

    The paper formulates fixed-set placement around log-det Kalman error and develops approximation algorithms for target-error/minimum-sensor and sensor-budget/error-minimization problems.

    Source: §I · p. 2, C. Sensor Placement Problems · p. 4

  • Results

    The log-det error is supermodular and non-increasing in the sensor set, and the paper establishes sensor/measurement scaling limits and worst-case algorithm guarantees.

    Source: §I · pp. 1–2

  • Takeaways & Limitations

    The algorithms are used to estimate the initial condition in a CO2 sequestration model and, as a result, detect constant leaks among sites.

    Source: B. CO2 Sequestration Sites · p. 9

Abstract

from arXiv · show

In this paper, we focus on sensor placement in linear dynamic estimation, where the objective is to place a small number of sensors in a system of interdependent states so to design an estimator with a desired estimation performance. In particular, we consider a linear time-variant system that is corrupted with process and measurement noise, and study how the selection of its sensors affects the estimation error of the corresponding Kalman filter over a finite observation interval. Our contributions are threefold: First, we prove that the minimum mean square error of the Kalman filter decreases only linearly as the number of sensors increases. That is, adding extra sensors so to reduce this estimation error is ineffective, a fundamental design limit. Similarly, we prove that the number of sensors grows linearly with the system's size for fixed minimum mean square error and number of output measurements over an observation interval; this is another fundamental limit, especially for systems where the system's size is large. Second, we prove that the logdet of the error covariance of the Kalman filter, which captures the volume of the corresponding confidence ellipsoid, with respect to the system's initial condition and process noise is a supermodular and non-increasing set function in the choice of the sensor set. Therefore, it exhibits the diminishing returns property. Third, we provide efficient approximation algorithms that select a small number sensors so to optimize the Kalman filter with respect to this estimation error ---the worst-case performance guarantees of these algorithms are provided as well. Finally, we illustrate the efficiency of our algorithms using the problem of surface-based monitoring of CO2 sequestration sites studied in Weimer et al. (2008).

I. INTRODUCTION

The paper studies fixed sensor placement for Kalman estimation in noisy, interdependent dynamic systems and establishes design limits, properties of a log-det error objective, and approximation algorithms. It also distinguishes this setting from sensor scheduling and reports an application to CO2 sequestration monitoring.

I. INTRODUCTION

  • The setting is a linear time-variant system with process and measurement noise, where each sensor measures one state and the Kalman filter is the optimal linear estimator for a sensor set.The paper frames small-sensor design as important for large-scale systems and operational constraints such as limited bandwidth and communication power.Source: §I · p. 1
  • The paper quantifies sensor and measurement trade-offs: sensor count grows linearly with system size at fixed error and measurement count, while output-measurement count scales logarithmically with system size and sensor count under the stated conditions.The number of output measurements is proportional to observation-interval length.Source: §I · p. 1
  • The log-det error covariance relative to the initial condition and process noise is a non-increasing, supermodular function of the sensor set.The paper contrasts this general result with earlier results limited to special systems or zero process noise.Source: §I · p. 2
  • Unlike sensor scheduling, the placement problem selects one sensor set that remains fixed over time rather than choosing a possibly changing output subset at each time step.The paper optimizes the log-det error relative to the initial condition and process noise.Source: §I · p. 2
  • The approximation algorithms address minimum-sensor placement for a target error and error minimization under a sensor budget, with stated worst-case guarantees.For the budgeted problem, the stated guarantee at l = r is 1 − 1/e.Source: §I · p. 2
  • The minimum mean square error relative to the system state is not generally supermodular in the sensor set.The paper notes that this counterexample from sensor scheduling extends to minimal sensor placement.Source: §I · p. 2
  • The paper illustrates its analysis and tests its algorithms with simulations on an integrator-chain network and surface-based monitoring of CO2 sequestration sites.The sequestration-site study is attributed to.Source: §I · p. 3

II. PROBLEM FORMULATION

This section establishes notation for sets, matrices, vectors, norms, eigenvalues, and random-variable covariances.

II. PROBLEM FORMULATION

  • The natural numbers are denoted by N, the reals by R, and {1, 2, . . ., n} by [n]; |X| denotes the cardinality of a set X.Source: §II · p. 3
  • Capital letters denote matrices and lowercase letters vectors; A⊤ is the transpose of A, and Aij is its entry in row i and column j.Source: §II · p. 3
  • The section defines the spectral norm and minimum and maximum eigenvalues, positive-semidefinite and positive-definite notation, and expected value and covariance for random variables.I denotes the identity matrix, with its dimension inferred from context.Source: §II · p. 3

A. System and Estimation Framework

The framework models noisy linear dynamics over a finite observation interval and uses linear estimation to assess state uncertainty. It also defines a log-det error metric based on the associated confidence ellipsoid.

A. System and Estimation Framework

  • The model uses state x_k, output y_k, input u_k, process noise w_k, measurement noise v_k, and initial condition x_0.Source: A. System and Estimation Framework · p. 3
  • The initial condition and process and measurement noises are assumed uncorrelated, with positive-definite covariances for the initial condition and process noise and covariance σ^2I for measurement noise.The measurement-noise variance parameter satisfies σ > 0.Source: A. System and Estimation Framework · p. 3
  • The observation interval is [0, k], of length k + 1, and the measurements, process noises, and measurement noises are stacked into corresponding vectors over that interval.The measurement vector is known, while the stacked noise vectors are not.Source: A. System and Estimation Framework · p. 3
  • The framework considers minimum mean square linear estimators for states within the observation interval; recursive implementation of the estimator gives the Kalman filtering algorithm.Source: A. System and Estimation Framework · pp. 3–4
  • In addition to state-estimation error, the framework uses the volume of an η-confidence ellipsoid for the estimation error, and calls its logarithmic form the log-det estimation error.The ellipsoid contains the estimation error with probability η.Source: A. System and Estimation Framework · p. 4

B. Sensor Placement Framework

Sensor placement selects a fixed subset of system states to measure. The framework studies how that subset affects estimation of the initial and final states.

B. Sensor Placement Framework

C. Sensor Placement Problems

The paper frames three sensor-placement objectives: characterize estimation-error limits, establish properties of logdet error as a function of the sensor set, and design placements under error or sensor-count constraints.

C. Sensor Placement Problems

III. FUNDAMENTAL LIMITS IN OPTIMAL SENSOR PLACEMENT

The section derives bounds and trade-offs for Kalman-filter estimation error over a finite observation interval. Sensor requirements scale linearly with system size under fixed error, while required observation length scales logarithmically under fixed error and sensor count.

III. FUNDAMENTAL LIMITS IN OPTIMAL SENSOR PLACEMENT

  • With fixed estimation error, the number of sensors grows linearly with system size; for fixed sensor count, required observations grow only logarithmically with system size.For fixed system size and error, the required observation length also decreases logarithmically as sensor count increases.Source: §III · pp. 4–6
  • For a fixed finite sensor count and observation interval, the lower bound keeps mmse(x0) above zero and decreases only inversely with sensor count, while increasing linearly with system size.For fixed, non-zero λmin, the scaling also applies to mmse(xk).Source: §III · p. 5
  • The necessary sensor count increases when the target mmse or the number of output measurements decreases, and grows linearly with system size for fixed mmse(x0).For λmin ≤ 1, the sensor count can instead grow sublinearly with system size for fixed mmse(xk).Source: §III · p. 6
  • The necessary number of output measurements increases when the target mmse or sensor count decreases, but grows only logarithmically with system size for fixed error and sensor count.It also decreases logarithmically as the number of sensors increases.Source: §III · p. 6

IV. SUBMODULARITY IN OPTIMAL SENSOR PLACEMENT

The section derives a closed-form logdet error objective and proves it is supermodular and non-increasing in the sensor set. This diminishing-returns property supports efficient approximate algorithms for the two placement problems.

IV. SUBMODULARITY IN OPTIMAL SENSOR PLACEMENT

  • The section derives a closed formula for logdet error as a sensor-set function, with its dependence on the sensor set made explicit through O_k.Source: §IV · p. 6
  • The supermodularity result supports efficient approximate greedy algorithms for P1 and P2.Source: §IV · pp. 6–7
  • The logdet error is supermodular and non-increasing in the sensor set, so its reduction from newly placed sensors diminishes as the existing set grows.Source: §IV · pp. 6–7

V. ALGORITHMS FOR OPTIMAL SENSOR PLACEMENT

Because the two sensor-placement problems minimize a supermodular error function, the paper develops efficient approximation algorithms for both. Their guarantees trade sensor-set size against estimation quality.

V. ALGORITHMS FOR OPTIMAL SENSOR PLACEMENT

  • P1 and P2 are combinatorial minimizations of a supermodular error function, and minimizing a general supermodular function is NP-hard.The paper therefore provides approximation algorithms with worst-case performance guarantees.Source: §V · p. 7
  • P1's Algorithm 2 meets the error bound with a sensor set whose size is within a logarithmic-factor guarantee of the minimum feasible size.The guarantee factor depends logarithmically on P1's parameters.Source: §V · pp. 7–8
  • For the generic cardinality-constrained problem, increasing the selected-set size from r to l improves the stated approximation factor to 1 − e^(−l/r).The cited examples give approximately 0.63 at l = r and 0.99 at l = 5r.Source: §V · pp. 8–9
  • For P2, Algorithm 4 returns l ≥ r sensors and achieves a near-optimal objective value as l increases.The approximation level depends on network size, r, and noise variance.Source: §V · pp. 7, 9

A. Integrator Chain Network

On a five-node integrator chain, the algorithms select optimal sensor sets for the tested error bounds and sensor budgets. The minimum logdet error nevertheless improves only linearly as more sensors are added.

A. Integrator Chain Network

  • {3, 5} is the optimal minimal sensor set for the tested bound R, and Algorithm 2 returns optimal minimal sets for every other feasible R.No singleton meets the bound; among two-sensor sets, {3, 5} has the smallest logdet error.Source: A. Integrator Chain Network · p. 9
  • For each tested budget r = 1, 2, …, 5, Algorithm 4 selects a set that minimizes log det(Σz4, ·) among sets of that size.The paper reports optimal performance for all tested values of r.Source: A. Integrator Chain Network · p. 9
  • As r increases from 0 to 5, the minimum logdet error decreases only linearly, from 0 to approximately −31.The paper relates this behavior to Theorem 1.Source: A. Integrator Chain Network · p. 9

B. CO2 Sequestration Sites

In the 81-location CO2 sequestration example, Algorithm 2 uses fewer sensors as the allowed error bound is relaxed, while Algorithm 4's objective improves with a larger sensor budget. The two algorithms perform at or beyond their stated guarantees in the tested comparisons.

B. CO2 Sequestration Sites

  • In Fig. 2’s left plot, Algorithm 2 uses fewer sensors as R increases, consistent with relaxing P1’s estimation-error bound.Source: B. CO2 Sequestration Sites · p. 10
  • Algorithm 4's minimum logdet values coincide with the minima from random samples of 80,000 sensor sets across the tested budgets.The random comparison used 10,000 distinct sets for each tested r.Source: B. CO2 Sequestration Sites · p. 10
  • For error bounds R below −20, Algorithm 2 returns a set that satisfies the bound and minimizes log det(Σz99, ·); above −20, its objective is close to Algorithm 4's.For R above −20, Algorithm 2 solves P1 but does not minimize the logdet error.Source: B. CO2 Sequestration Sites · p. 10
  • As r increases from 0 to 81, the minimum logdet error decreases only linearly, from 0 to approximately −62.The paper identifies this as an example of the fundamental design limit in Theorem 1.Source: B. CO2 Sequestration Sites · p. 10

VII. CONCLUDING REMARKS

The paper studies Kalman estimation for linear time-variant systems over a finite observation interval and proves design limits and sensor-set properties. It uses those properties to build approximation algorithms and illustrates them with simulations.

VII. CONCLUDING REMARKS

  • The number of selected sensors grows linearly with system size when the minimum mean square error and observation interval are fixed.The conclusion presents this as one example of the paper's design limits.Source: §VII · p. 10
  • The logdet estimation error for the initial condition and process noise is supermodular and non-increasing in the sensor set for any observation interval.The paper uses this property to develop efficient approximation algorithms for P1 and P2 with worst-case guarantees.Source: §VII · p. 10
  • Simulations illustrate the analysis and test the algorithms on an integrator-chain network and surface-based monitoring of CO2 sequestration sites.Thermal control of indoor environments is identified as another application fitting the minimal sensor-placement context.Source: §VII · p. 10

Related papers

Loading 1509.08146v4…