⚡ electrical engineering

Partitioning and Observability in Linear Systems via Submodular Optimization

This paper addresses the computationally intractable challenge of partitioning large-scale linear systems for decentralized control by formulating the problem as a submodular maximization task, thereby enabling scalable sensor placement and providing theoretical bounds on the resulting subsystem observability.

Original authors: Mohamad H. Kazma, Ahmad F. Taha

Published 2026-07-09

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mohamad H. Kazma, Ahmad F. Taha

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 the captain of a massive, complex spaceship. This ship is full of thousands of sensors, engines, and computer systems all talking to each other. Your job is to keep an eye on everything to make sure the ship is running smoothly. This is called observability.

However, there's a problem: The ship is so huge that trying to watch every single part at once from the captain's bridge is impossible. It's too much data, and the computers get overwhelmed. You need a better way to manage this.

This paper proposes a clever solution: Divide and Conquer.

Here is the story of what the authors did, explained simply:

1. The Problem: Too Big to Watch

The authors are dealing with "Linear Time-Invariant" (LTI) systems. In plain English, think of these as complex machines (like the spaceship, or in their examples, chemical reaction networks) where parts interact in predictable ways.

To understand the whole machine, you need to place "sensors" (like cameras or microphones) on specific parts. But finding the best spots to put these sensors in a giant system is a nightmare. It's like trying to find the perfect 10 spots to put security cameras in a city the size of New York. If you try to calculate every possible combination, your computer will crash before it finishes.

2. The Solution: Breaking the Ship into Neighborhoods

The authors suggest breaking the giant system into smaller, manageable "neighborhoods" or subsystems.

The Partitioning: Instead of looking at the whole ship, they slice it up into smaller groups.
The Catch: You can't just slice it randomly. If you slice it poorly, the neighborhoods might become isolated islands that don't talk to each other, and you lose the ability to understand how the whole ship works.
The Goal: They want to slice the system in a way that keeps the neighborhoods connected but makes each neighborhood easy to watch on its own.

3. The Secret Weapon: "Diminishing Returns" (Submodularity)

This is the most technical part, but here is the simple version:

The authors use a mathematical concept called Submodularity. Think of it like filling a bucket with water using cups.

If your bucket is empty, the first cup of water makes a huge difference.
If your bucket is almost full, adding another cup makes very little difference.
This "diminishing returns" property is a superpower in math. It means you don't have to check every possible combination of sensors. You can use a "greedy" strategy: just pick the best spot available right now, then the next best, and so on.

The paper proves that when they slice the system into neighborhoods, this "diminishing returns" magic still works. This allows them to solve the problem quickly, even for huge systems.

4. The Two-Step Dance

The authors created a two-step process:

Step 1: Slice the Pie (Partitioning). They use math to cut the system into neighborhoods. They don't just cut randomly; they cut in a way that maximizes how "watchable" each neighborhood is. They proved that this cutting process follows the "diminishing returns" rule, so they can find a great solution very fast.
Step 2: Place the Cameras (Sensor Placement). Once the neighborhoods are sliced, they figure out where to put the sensors within those neighborhoods. Because the neighborhoods are smaller, this is much easier to calculate.

5. The Results: Faster and Just as Good

The authors tested this on two complex chemical reaction networks (think of them as very complicated recipes for making fuel).

Speed: By breaking the problem down, they solved it much faster than trying to solve the whole thing at once.
Accuracy: Surprisingly, breaking the system down didn't make the "view" worse. The sensors placed in the smaller neighborhoods worked just as well as if they had been placed in the giant, unbroken system.
The Trade-off: They found that if you slice the system into too many tiny pieces, you might lose some of the "big picture" connections. But if you slice it into the right number of pieces, you get the best of both worlds: speed and accuracy.

The Big Takeaway

This paper is like a guide for a captain who has a giant, messy ship. It says: "Don't try to watch the whole ship at once. Break it into neighborhoods, make sure the neighborhoods can still talk to each other, and then place your cameras in the best spots within those neighborhoods. You will get a clear picture of the whole ship, and you'll do it in a fraction of the time."

They proved mathematically that this approach works and showed with real-world examples (combustion reactions) that it is a practical, fast, and reliable way to manage complex systems.

Technical Summary: Partitioning and Observability in Linear Systems via Submodular Optimization

1. Problem Statement

This paper addresses the computational intractability of Sensor Placement (SP) and network partitioning in large-scale linear time-invariant (LTI) systems. While network partitioning is a known strategy to enable decentralized control and reduce computational complexity, the interplay between partitioning, system observability, and optimal sensor allocation remains an open problem.

Specifically, the authors identify a gap in the literature regarding how to partition a dynamic network into interconnected subsystems such that:

The observability metrics of the resulting subsystems are maximized.
The overall system observability is preserved or optimized.
The subsequent SP problem can be solved efficiently (scalably) compared to solving it over the full, unpartitioned system.

The core challenge is that the SP problem is combinatorial and NP-hard. Solving it directly on large-scale systems is computationally prohibitive. The paper seeks to reformulate the partitioning and SP problems into submodular maximization problems under matroid constraints, allowing for polynomial-time solutions with provable performance guarantees.

2. Methodology

The proposed framework consists of two primary stages: System Partitioning and Sensor Placement (SP), both grounded in submodular optimization theory.

A. System Partitioning (Problem P1 $\to$ P2)

The authors first define the problem of partitioning the measurable state-space $V$ into $\kappa$ disjoint subsystems $S_i$ .

Reformulation: The original partitioning problem (P1), which seeks to maximize the sum of observability metrics of subsystems, is reformulated as a submodular maximization problem (P2) subject to a partition matroid constraint.
Mechanism: To achieve this, the ground set is expanded to $X = \mathcal{C} \times V$ (where $\mathcal{C}$ is the set of subsystem indices). This creates $\kappa$ copies of each state. The constraint ensures that each state $v \in V$ is assigned to at most one subsystem ( $|S \cap (\mathcal{C} \times \{v\})| \leq 1$ ).
Algorithm: The problem is solved using a continuous greedy algorithm combined with multilinear extension. This approach provides a $(1 - 1/e)$ -approximation guarantee for the optimal solution.

B. Sensor Placement (Problem P3)

Once the system is partitioned, the SP problem is solved for the resulting subsystems.

Constraint: Unlike standard SP problems that use a uniform cardinality constraint (selecting $r$ sensors from the whole network), the partitioned SP problem (P3) is solved under a partition matroid constraint. This limits the number of sensors allocated to each specific subsystem ( $|R \cap S_i| \leq r_i$ ).
Submodularity: The paper proves that common observability metrics (Trace, Log-determinant, and Rank of the Observability Gramian) retain their submodular properties even when the system is partitioned.
Theoretical Bounds: The authors derive theoretical bounds comparing the observability of the global system to the sum of observability metrics of the partitions. Specifically, for Trace and Log-determinant metrics, the global observability is bounded below by the sum of local observabilities.

C. Key Theoretical Properties

Modularity of Gramians: The observability Gramian for a subsystem is shown to be a modular set function with respect to state selection.
Submodularity of Metrics: While the Gramian itself is modular, derived metrics like Log-determinant and Rank are proven to be submodular and monotone increasing under the partition.
Equivalence: The paper establishes that the partitioned system's total observability Gramian ( $W_{\pi_\kappa}$ ) is equivalent to the sum of the subsystem Gramians ( $W_{S_i}$ ), allowing for decentralized analysis.

3. Key Contributions

Submodular Formulation of Partitioning: The paper introduces a framework to partition LTI systems by maximizing observability-based metrics, reformulating the combinatorial partitioning problem into a submodular maximization problem under a partition matroid. This enables the use of greedy algorithms with theoretical optimality guarantees.
Preservation of Submodularity: It is demonstrated that observability-based measures (Trace, Logdet, Rank) remain submodular in a partitioned system, allowing the SP problem to be solved efficiently over the partitions rather than the full system.
Theoretical Bounds: The authors provide bounds characterizing the relationship between global observability and the sum of local subsystem observabilities. These bounds quantify the potential performance loss (or lack thereof) when solving SP in a partitioned versus unpartitioned system.
Continuous Greedy Algorithm: The application of the continuous greedy algorithm with multilinear extensions is utilized to solve both the partitioning and SP problems, achieving a $(1 - 1/e)$ performance guarantee.

4. Numerical Results and Validation

The framework was validated using two nonlinear natural gas combustion reaction networks (H2O2 and GRI30), linearized around steady-state conditions.

Computational Efficiency: Solving the SP problem on the partitioned system significantly reduced computational time compared to the unpartitioned system (e.g., reducing time from ~0.65s to ~0.23s for the H2O2 network) while yielding identical optimal sensor configurations and observability values.
Theoretical Bound Validation: In the GRI30 network (53 states), the results confirmed the theoretical bounds in Theorem 2. Solving the SP problem with a localized objective function (sum of local logdets) yielded suboptimal results compared to the global objective function, validating the derived inequality.
Partition Number ( $\kappa$ ) Trade-offs: The study analyzed varying $\kappa$ (3 to 6). It was found that while higher modularity (denser intra-cluster connections) is often desired in clustering, it does not necessarily correlate with higher observability. The observability-based partitioning (P2) produced partitions with lower modularity but significantly higher observability metrics compared to spectral clustering.
State Estimation Performance: Using a discrete-time Kalman filter, the paper demonstrated that state estimation performance (relative error) for the partitioned system matched that of the unpartitioned system, confirming that the partitioning strategy does not degrade estimation accuracy.

5. Significance and Claims

The paper claims to fill a critical gap in the literature by providing the first method to simultaneously address network partitioning and sensor placement in linear systems through the lens of submodular optimization.

Scalability: The primary significance is the ability to solve large-scale SP problems in polynomial time by decomposing the system into observable subsystems, thereby enabling decentralized state estimation strategies.
Theoretical Rigor: The work provides rigorous theoretical guarantees (submodularity, monotonicity, and $(1-1/e)$ approximation bounds) that are often lacking in heuristic partitioning approaches.
Practical Utility: By showing that partitioned SP yields the same optimal sensor configurations as the full system but with reduced computational cost, the paper argues for the practical viability of this approach for large-scale cyber-physical systems (e.g., power grids, chemical reaction networks).

The authors note limitations, including the exclusion of process/measurement noise in the formulation (though tested in simulation), lack of sensor redundancy considerations, and the focus on interconnected rather than fully disconnected subsystems. They suggest future work on decomposing Gramians into sub-Gramians and utilizing distributed algorithms.