Scaling Laws for Sensor Placement in Dynamic Systems

This direction is merged into another direction: generalization to nonlinear systems. Its last version stays readable and citable here.

Version 1 of 15 papers15 conceptsfrozen 2026-10-04

When monitoring complex, large-scale systems—such as power grids, robotic swarms, or environmental sensor networks—we face a daunting combinatorial challenge. If you have a thousand possible locations to place sensors but a budget for only fifty, how do you choose the set that provides the most accurate estimate of the system's internal state?

In Sensor placement for optimal Kalman filtering: Fundamental limits, submodularity, and algorithms, researchers Vasileios Tzoumas and George J. Pappas establish the theoretical boundaries of this problem, revealing why simple strategies work and why large systems are fundamentally difficult to observe.

The Geometry of Diminishing Returns

The core difficulty of sensor placement is that it is a discrete optimization problem. In theory, finding the absolute best subset of sensors requires checking every possible combination, which is computationally impossible for large networks.

However, the estimation error of a Kalman filter possesses a structural property called supermodularity. In intuitive terms, this represents the principle of diminishing returns: the "information gain" from adding a new sensor is greatest when you have few sensors and decreases as you add more.

Because the error reduction follows this predictable curve, we don't need to search every combination. A simple greedy algorithm—one that picks the single best sensor, then the next best, and so on—is guaranteed to perform with near-optimal accuracy. This mathematical property turns an impossible search into a practical engineering task.

The Linear Scaling Wall

While greedy algorithms make sensor placement feasible, Tzoumas and Pappas identify a "fundamental limit" to how much we can economize on hardware.

They prove that to maintain a constant level of accuracy as a dynamic system grows, the number of sensors must scale linearly with the system's dimensionality. If you double the number of states in your system (for example, doubling the number of nodes in a smart grid), you generally cannot get away with a sub-linear increase in sensors. You must double the sensors to keep the same "grip" on the system's uncertainty. This suggests that for massive networks, there is no "silver bullet" algorithm that allows high-precision monitoring with only a handful of measurement points.

Why Space Beats Time

A common intuition in signal processing is that if you have a weak signal, you should just listen for longer. In the context of Kalman filtering, this would mean using a longer observation window to compensate for having fewer sensors.

The research shows that this intuition fails in dynamic systems. The benefit of increasing the observation window duration is only logarithmic, while the benefit of adding more physical sensors is linear.

Why does spatial density trump temporal duration?

  1. Information Decay: In a dynamic system, states evolve over time. Information gathered a long time ago becomes "stale" as the system's internal noise accumulates.
  2. Observability: A sensor at a specific location captures local dynamics that may be poorly communicated to other parts of the network. No amount of extra time at Sensor A can fully compensate for the lack of a Sensor B if the state at B's location is weakly coupled to A.

Ultimately, this research direction clarifies that the "where" of sensing is far more powerful than the "how long." To manage the complexity of growing dynamic networks, we must prioritize the physical density of measurements, supported by the mathematical safety net of supermodular optimization.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scaling_laws_for_sensor_placement_in_dyn_645635d3,
  title = {Scaling Laws for Sensor Placement in Dynamic Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-laws-for-sensor-placement-in-dynamic-systems/rdr_645635d350044b868190fddbe85964c9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_laws_for_sensor_placement_in_dyn_645635d3_v1,
  title = {Scaling Laws for Sensor Placement in Dynamic Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-laws-for-sensor-placement-in-dynamic-systems/rdr_645635d350044b868190fddbe85964c9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}