Partitioning and Observability in Linear Systems via Submodular Optimization
Mohamad H. Kazm a, Graduate Student Member, IEEE, Ahmad F. Taha, Member, IEEE · 2025
Read Partitioning and Observability in Linear Systems via Submodular Optimization by Mohamad H. Kazm a, Graduate Student Member, IEEE, Ahmad F. Taha, Member, IEEE (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-16169.txt.
Introduction
Splitting a huge network into pieces a computer can watch and steer sounds administrative, but a bad split can blind the operators. Mohamad Kazma and Ahmad Taha tackle that trade-off in this 2025 paper for linear dynamic systems. They show the partitioning task, choosing sensor spots included, can be framed as maximizing a submodular function, a class with strong algorithmic guarantees.
On top of the partition, the sensor placement problem can then be solved piece by piece. The authors prove bounds comparing how observable the whole network is versus its parts, putting a price on decentralization. Case studies on networks of several sizes confirmed the bounds behave as promised.
Catalog record
| CREATOR | Mohamad H. Kazm a, Graduate Student Member, IEEE, Ahmad F. Taha, Member, IEEE |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-16169
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Partitioning and Observability in Linear Systems via Submodular Optimization Mohamad H. Kazm a, Graduate Student Member, IEEE, Ahmad F. Taha, Member, IEEE Abstract Network partitioning has gained recent attention as a pathway to enable decentralized operation and control in large-scale systems. This paper addresses the interplay between partitioning, observability, and sensor placement (SP) in dynamic networks. The problem, being computationally intractable at scale, is a largely unexplored, open problem in the literature. To that end, the paper’s objective is designing scalable partitioning of linear systems while maximizing observability metrics of the subsystems. We show that the partitioning problem can be posed as a submodular maximization problem—and the SP problem can subsequently be solved over the partitioned network. Consequently, theoretical bounds are derived to compare observability metrics of the original network with those of the resulting partitions, highlighting the impact of partitioning on system observability. Case studies on networks of varying sizes corroborate the derived theoretical bounds. I Introduction and Contributions N etwork partitioning, the process of segmenting a system into finite sub-networks, has gained popularity in the past decade for both static and dynamic networks. Its advantages are numerous. Some of these merits are: reducing computational complexity, identifying community structures, performing localized sensing and decentralized feedback control, reducing communication costs, improving network resilience, and minimizing cascading failures. Partitioning is not merely a theoretical concept—it has been studied in a variety of dynamic network applications (epidemics, opinion dynamics, power grids, and water systems). Relevant to dynamic network partitioning is observability—a fundamental system-theoretic notion that enables one to infer internal system states from some output measurements. Observing the full state is limited by the number and configuration of sensors within a system. In particular, for large and complex systems, such as cyber-physical systems [ 1 ] and coupled biological reaction networks [ 2 ] , state reconstruction is constrained by sensing and its allocation costs. As a result, one potential goal of partitioning is to identify observable subsystems (i.e., partitions) that preserve overall system observability, thereby enabling scalable localized/distributed state-estimation strategies developed for large-scale systems. In this paper, we consider the problem of network partitioning for linear systems such that a variety of the subsystems’ observability metrics are optimized. This is followed by performing localized sensor placement (SP) via a submodular set optimization approach. We note that there is no literature on studying the interplay between observability, partitioning, and SP—and there are no known methods solving this observability-based partitioning problem. The benefit of this approach is threefold: (i) to identify observable interconnected subsystems, (ii) to enable localized/decentralized state-estimation strategies, and (iii) to yield a more scalable solution for the SP problem, which remains a subject of ongoing research due to its combinatorial properties. \mathcal{V} 1 2 3 4 5 6 7 8 (a) Complete System (a) \mathcal{S}_{1} \mathcal{S}_{2} \mathcal{S}_{3} 1 2 3 4 5 6 7 8 (b) Partitioned Subsystems (b) Fig. 1: (a) A system of measured internal state, v\in\mathcal{V} (measurable space), depicting interactions of a dynamical system and (b) the subsequent subsystems \mathcal{S}_{i}\subseteq\mathcal{V} . The nodes represent the system states and edges represent the internal state connections. The colored boxes represent the nodes that belong to a particular subsystem. The interactions between the subsystems remain after system partitioning. The SP problem has been thoroughly studied in the literature [ 3 , 4 , 5 , 6 , 7 , 8 ] . One approach follows from [ 4 ] that formulates the actuator placement, dual to the SP problem, in the context of submodular set optimization. This setting is characterized by diminishing returns properties which provides provable performance guarantees that allow one to solve the combinatorial SP problem in polynomial time [ 9 ] . However, the applicability of polynomial-time algorithms, such as the simple greedy, still yields scalability challenges for large-scale systems and real-time sensor scheduling. To this end, in this paper we approach alleviating the computational burden of the SP problem in large-scale linear time-invariant (LTI) systems by identifying subsystems within the original dynamical system as described in Fig. 1 . This allows the exploitation of more advanced algorithms that leverage parallelization over the subsystems. Specifically, this paper studies the fundamental problem of partitioning or clustering of a dynamic linear network to perform two key functions: (i) maximizing the partitions’ observability metrics while (ii) ensuring optimized SP for overall system observability. This also enables, as broader impact, localized state estimation for the partitioned interconnected subsystems. We perform the above two key functions via a specific set of techniques, grounded in submodular set function optimization using matroid constraints. In what follows, we briefly highlight the rich literature of network partitioning, SP, and their overlap. Clustering versus partitioning. We note here that there is somewhat of an ambiguity in the literature of partitioning/clustering, where there is no consensus among the practical interpretation of these two words. While some studies define partitioning through dissecting a network into k partitions that are no longer connected [ 10 , 11 ] , others maintain the connectivity in the network [ 12 , 13 , 14 ] . In this paper, we consider the problem of partitioning a system into clustered communities, referred to as subsystems, where the interconnections between the measurable states of the subsystems are maintained. Notice from Fig. 1b , the connections (arrows) between subsystems \mathcal{S}_{1},\mathcal{S}_{2},\mathcal{S}_{3} remain intact after the partitioning. Why is partitioning needed? The clustering of nodes and network states is becoming increasingly relevant for the scalability of distributed control methods [ 15 ] . In a dual concept to observability, a submodular approach towards islanding of multi-agent networks based on consensus-based control is formulated in [ 16 ] . The controlled islanding or partitioning of a power grid is formulated to reduce the effects of cascading failure events. Furthermore, while studying control under multi-agent networks and coupled systems, the herdability * * * Herdability is a relaxed notion of controllability that indicates the ability to steer system states to a specific state-space subset. of a set of leader nodes in a cluster is introduced in recent literature [ 11 , 17 ] . The dynamical network is equitable partitioned to characterize a controllable subspace that renders the system herdable. In [ 18 , 19 ] , the local subsystem dynamics of a discrete LTI system are identified by leveraging local subsystem input and output signals. An optimization-based partitioning algorithm is proposed in [ 20 ] , where local controllability is imposed as a constraint through the rank of the controllability matrix. The method demonstrates that partitioning can reduce computational costs for local controllers, thereby improving decentralized control performance. Readers are referred to [ 15 ] for a survey on clustering strategies for scalable distributed control, and to [ 21 ] for a recent survey on partitioning in model predictive control; clustering remains a topic of interest. The partitioning of complex systems provides an essential decomposition for effective and scalable decentralized state estimation in large-scale dynamical systems [ 22 ] . For system monitoring under limited computational and sensing resources, the authors in [ 23 ] propose a clustering-based approach that constructs an aggregated observer for large-scale linear flow networks. The method designs an observer based on the average