⚡ electrical engineering

Provably Efficient Sensor Allocation for Unknown High-dimensional Systems with Limited Sensing

This paper proposes a two-stage framework that learns efficient sensor allocations for unknown high-dimensional linear systems by first identifying system parameters from multiple partial trajectories and then adapting classic allocation methods, thereby achieving near-optimal sensor usage without requiring prior knowledge of an observable configuration.

Original authors: Yuyang Zhang, Derya Cansever, Na Li

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuyang Zhang, Derya Cansever, Na Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand how a massive, complex machine works—like a giant power grid, a weather system, or even the human brain. This machine has thousands of moving parts (called "state coordinates"). To understand it, you need to watch these parts. But here's the catch: you can't afford to put a camera on every single part. Cameras (sensors) are expensive, and you only have a few of them.

The problem is: How do you figure out the rules of the machine and decide exactly where to put your few cameras so you can see everything that matters?

This paper solves that puzzle with a two-step strategy, like a detective solving a mystery with limited clues.

The Problem: The "Blind" Machine

Usually, to know where to put your cameras, you need to already know the machine's blueprint (its mathematical model). But in real life, we often don't have the blueprint. We have to learn it by watching the machine run.

However, there's a catch:

If you try to learn the blueprint by watching the machine, you usually need to see everything at once.
If you only have a few cameras, you can't see everything.
If you don't know where to put the cameras to see the "important" parts, you might end up with a blurry picture that doesn't tell you how the machine works.

It's a "chicken and egg" problem: You need the blueprint to pick the right camera spots, but you need the right camera spots to get the blueprint.

The Solution: A Two-Stage Detective Story

The authors propose a clever two-stage framework to break this cycle.

Stage 1: The "Rotating Flashlight" (System Identification)

Imagine you have a flashlight (a sensor) and a dark room with 100 switches. You can only shine the light on one switch at a time.

The Old Way: You might try to shine the light on all switches at once (impossible with one flashlight) or guess which ones to shine on.
The New Way (This Paper): You take the flashlight and move it around systematically.
- Trajectory 1: Shine on switches 1, 2, 3.
- Trajectory 2: Shine on switches 4, 5, 6.
- Trajectory 3: Shine on switches 7, 8, 9.
- ...and so on, cycling through the room.

Even though you never see the whole room at once, you collect many "snapshots" over time. The paper's algorithm acts like a super-smart puzzle solver. It takes all these partial snapshots and stitches them together to reconstruct the entire blueprint of the machine.

The Magic Trick: The algorithm realizes that even if you only see a tiny piece of the machine at any moment, if you rotate your view enough times, you can mathematically deduce how the parts connect to each other. It proves that as long as every single switch is seen at least once across all your snapshots, you can learn the machine's rules perfectly.

Stage 2: The "Smart Map" (Sensor Allocation)

Now that you have the reconstructed blueprint (the learned model), you need to decide: "Where should I permanently place my cameras to watch this machine efficiently?"

The Goal: Find the smallest number of cameras that still let you see the whole picture (a concept called "observability").
The Method: The paper uses a "greedy" strategy. It starts with no cameras and asks: "If I add one camera here, how much more of the machine can I see?" It picks the spot that gives the biggest "bang for the buck."
The Result: It keeps adding cameras one by one until the whole machine is visible. The paper proves that this method will never use more than a tiny bit extra compared to the absolute best possible arrangement. It's like packing a suitcase: you might not get the mathematically perfect fit, but you'll get 99% of the way there with very little effort.

What About "Inaccessible" Parts?

Sometimes, some parts of the machine are behind a locked door (inaccessible coordinates). You can't put a camera there, no matter what.

The paper extends its method to handle this. It says: "Okay, we can't see the locked room, but if the parts outside the locked room are enough to tell us what's happening inside, we can still solve the puzzle."
It adjusts the "rotating flashlight" strategy to only scan the accessible doors, and the "smart map" strategy only looks for camera spots in those accessible areas.

The Bottom Line

This paper provides a mathematical guarantee that you can:

Learn the rules of a huge, unknown system using only a few sensors, as long as you move those sensors around to see different parts over time.
Design a permanent sensor setup that is nearly perfect (using the minimum number of sensors needed) based on what you learned.

It turns a seemingly impossible task—learning a giant system with tiny eyes—into a reliable, step-by-step process.

Technical Summary: Provably Efficient Sensor Allocation for Unknown High-dimensional Systems with Limited Sensing

Problem Statement
This paper addresses the challenge of learning efficient sensor allocations for unknown high-dimensional linear dynamical systems ( $x_{t+1} = Ax_t + Bu_t + w_t$ ) where the state dimension $r$ is large. The objective is to identify a minimal set of sensors (state coordinates) that ensures the system is observable, using only a limited number of sensors during the data collection phase.

Existing approaches face two primary limitations in this setting:

Model Dependency: Classic sensor allocation methods require exact knowledge of the system matrices ( $A, B$ ), which are unavailable in unknown systems.
Data Requirements: Standard system identification (SYSID) methods typically require full-state observations (prohibitively expensive) or assume the existence of an initial sensor allocation that already guarantees observability (circular dependency).

Methodology
The authors propose a two-stage framework to overcome these limitations, operating under the assumption that the system is controllable and stable (Assumptions 1 and 2).

Stage 1: System Identification with Dynamic Measurement Selection
The authors introduce a novel SYSID algorithm (Algorithm 1) that does not require full-state measurements or a pre-existing observable allocation.
- Data Collection: Instead of measuring all states simultaneously, the algorithm collects $K$ trajectories. In each trajectory $k$ , a small number of sensors ( $\bar{n}$ ) measure a specific, potentially different, subset of state coordinates.
- Measurement Strategy: The measurement matrices $C_k$ are designed cyclically to ensure that every state coordinate is observed in at least $s$ trajectories ( $s_{min} \ge 1$ ).
- Estimation: The algorithm leverages a recursive expansion of the state dynamics to express the state as a linear combination of past inputs (Markov parameters). By performing least-squares regression on these input-output pairs across all trajectories, the algorithm estimates the Markov parameters matrix $G = [B, AB, \dots, A^dB]$ .
- Recovery: The system matrices $\hat{A}$ and $\hat{B}$ are subsequently recovered from the estimated Markov parameters using a pseudo-inverse approach, provided the estimation rank $d \ge r$ .
Stage 2: Data-Driven Sensor Allocation
Using the estimated system matrices from Stage 1, the authors adapt a greedy sensor allocation algorithm (Algorithm 2) to select the final sensor set.
- Rank Estimation Subroutine: A critical component is a rank estimation subroutine (Algorithm 3) that estimates the rank of the observability matrix $\mathcal{O}(\hat{C})$ using the noisy estimate $\hat{A}$ . This subroutine employs a carefully derived threshold based on the estimation error bounds to distinguish between non-zero and zero singular values.
- Greedy Selection: The algorithm iteratively adds sensors to the state coordinate that maximizes the estimated rank increase of the observability matrix until full rank ( $r$ ) is achieved.
Extension to Inaccessible Coordinates
The framework is extended to scenarios where certain state coordinates are physically inaccessible for sensor placement. The algorithm restricts the search space to accessible coordinates and utilizes an estimated Hankel matrix constructed from the accessible rows of the Markov parameters to perform rank estimation (Algorithm 4).

Key Contributions and Theoretical Results

Non-Asymptotic Error Bounds for SYSID: The paper provides finite-sample guarantees for the proposed SYSID algorithm. Theorem 1 establishes that the error in estimating the Markov parameters decays as $\tilde{O}(\sqrt{md/(s_{min}T)})$ , where $m$ is the input dimension, $d$ is the estimation rank, $T$ is the trajectory length, and $s_{min}$ is the minimum number of times any state is observed. Crucially, this holds even with a single sensor ( $\bar{n}=1$ ) provided enough trajectories are collected.
Sensor Allocation Guarantees: Theorem 2 and Theorem 3 prove that the proposed two-stage framework yields a sensor allocation that guarantees observability. The number of sensors used, $\hat{n}$ , is bounded by $(1 + \log(r))n^*$ , where $n^*$ is the optimal minimum number of sensors required. This approximation ratio matches the best-known results for known systems, despite operating on learned, approximate models.
Robustness to Inaccessibility: The framework successfully handles systems with inaccessible state coordinates, provided the accessible coordinates are sufficient to ensure observability (Assumption 3).

Experimental Validation
The authors validate their approach through numerical experiments on two models:

Block-Cyclic System: A system where observability requires one sensor per block. The algorithm successfully learned the system parameters and identified an optimal allocation of 5 sensors.
Thermal Dynamics (HVAC): A 20-zone system with 5 inaccessible coordinates. The algorithm learned the dynamics using only accessible measurements and identified an optimal allocation of 10 sensors (two per block) to ensure observability.

Significance
The paper claims to bridge the gap between theoretical sensor allocation (which assumes known models) and practical data-driven control (which often lacks full observability). By decoupling the system identification process from the requirement of full-state observability, the proposed method enables the learning of efficient sensor configurations for high-dimensional systems where sensors are scarce, expensive, or restricted to specific locations. The non-asymptotic guarantees provide a theoretical foundation for the reliability of these data-driven allocations in safety-critical applications such as power grids, weather forecasting, and neuroscience.