CS Paper Radar

A Polynomial-Time Algorithm for the Minimal Input/Output Node Cardinality Disturbance Decoupling Problem over Networks via Output Feedback

Luca Claude Gino Lebon, Jorke de Vlas, Johannes K. Fichte, Claudio Altafini

eess.SY math.OC ·submitted 2026-10-15 23:13 UTC · v2

Abstract

For networked systems, we propose a polynomial-time algorithm for solving the minimal input/output node cardinality disturbance decoupling problem via output feedback. The algorithm computes an optimal solution, namely, a pair of minimum-cardinality sets of control input and measurement output nodes that achieve disturbance decoupling, by solving a min-cut/max-flow problem on an extended network.

Comment
MATLAB functions implementing the results presented in this article are available in the GitLab repository: https://gitlab.liu.se/lucle71/node-based-ddp or in Zenodo: https://doi.org/10.5281/zenodo.23476722

Closest papers

Nearest neighbours by meaning across the whole index.

On the NP-Hardness of Unconstrained Static Output Feedback Stabilization

eess.SY ·2026-09-30 ·Gal Barkai, Iman Shames
similarity 0.57
Abstract

In this paper we give a polynomial-time reduction from the Subset Sum Problem to unconstrained static output feedback stabilization, establishing its NP-hardness. The construction uses two scalar building blocks to impose approximate discrete choices and a weighted-sum constraint. Once the problem is encoded, we relate the stability of the $N+1$ decoupled loops encoding the problem to that of a coupled plant. This is accomplished by leveraging frequency separation via a band-pass transformation, and comparing the root counts of the true characteristic polynomial with that of the different blocks in different regions of the right half-plane. The construction then naturally bounds every stabilizing gain and gives explicit modulus-margin estimates, ensuring that the plant data have polynomial binary encoding length.

0.47

On the Observability and Controllability of Leaky-ReLU Networks

eess.SY ·2026-08-10 ·Liangjie Sun, Wai-Ki Ching, Shun-ichi Azuma, Tatsuya Akutsu
theory similarity 0.57
Abstract

This paper studies minimum-node observability and controllability of Leaky rectified linear unit (Leaky-ReLU) networks under degree constraints. The objective is to characterize how many state nodes must be measured or directly actuated to determine the initial state from a finite output sequence or to steer the network between arbitrary states within a finite horizon. For observability, a graph-theoretic analysis yields a class-wide upper bound on the minimum number of observation nodes. We construct a family of networks attaining this bound, thereby determining the exact worst-case minimum number of observation nodes. We also construct networks that are observable from a single node over a finite horizon, establishing the exact best-case value of one. By establishing an observability--controllability duality under the corresponding degree constraints, we obtain analogous exact best- and worst-case results for the minimum number of control nodes. A comparison with ReLU networks shows how replacing the zero negative slope with a nonzero slope changes the observation-node requirement. More generally, the observability arguments require only injectivity of the activation function, whereas the controllability results extend to bijective activation functions.

0.04

Complexity of Output Feedback Stabilization

cs.CC math.OCeess.SY ·2026-09-17 ·Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang, Yukai Tang
similarity 0.55
Abstract

We show that unless P = NP, there cannot be a polynomial-time (or even pseudo-polynomial-time) algorithm for output feedback stabilization of a linear dynamical system with a linear controller. This settles one of the best-known open problems in control theory. The result holds in both continuous and discrete time. We also present a family of stabilizable linear dynamical systems for which no polynomial-time algorithm can write down a stabilizing controller in its standard representation.

0.41

Spatiotemporal Response Decay for Near-Optimal Distributed LQR via System Level Synthesis

eess.SY math.OC ·2026-10-08 ·Chenchen Zhou, José Matias
theorycode/data similarity 0.50
Abstract · 31 pages, 8 figures. Code and data: https://github.com/Daakuang/spacetime-sls

Distributed control requires choosing how far information travels and how long it is retained. For networked linear quadratic regulation (LQR), we use System Level Synthesis to bound these resources for a specified performance loss per node relative to centralized control. For locally coupled systems under uniform regularity assumptions, including stabilizability and detectability, we prove that the centralized optimal state and input responses to disturbance impulses satisfy exponential decay bounds in both time and spatial distance. On networks with polynomial neighborhood growth, sufficient communication ranges and memory horizons grow logarithmically with the inverse tolerance, independently of network size. Truncating these responses gives local finite-memory filters with stability and performance guarantees under a computable small-gain condition. Under an additional uniform local feedback condition, we also obtain controllers that confine nominal disturbance effects in space and eliminate them in finite time. Numerical experiments illustrate how performance and disturbance containment requirements guide architecture selection.

0.39

Observability Blocking in a Linear Synchronization Network with Partial State Measurements

eess.SY ·2026-08-26 ·Alexis Moreno, Abdullah Al Maruf
similarity 0.49
Abstract · 8 pages, 3 figures, submitted to the IEEE Conference on Decision and Control (CDC)

Large-scale networked systems are increasingly vulnerable to adversaries that can infer system dynamics from a small set of compromised nodes. This paper addresses the problem of blocking such inference using limited state information. While existing state-feedback methods achieve observability blocking with eigenvalue preservation, they require full state access and are impractical for large networks. We propose multiple control strategies that operate under partial state measurements. The first approach employs output feedback to achieve observability blocking while preserving a subset of open-loop eigenvalues. The second approach leverages an observer to reconstruct the system state and enables full-state feedback control, preserving all eigenvalues and providing greater flexibility in sensor placement. We further extend the observer-based design to a distributed framework. Numerical examples demonstrate the scope and validity of the proposed methods.

0.30

Scalable Incremental Robustness Analysis of Neural Network Feedback Systems

cs.LG math.OCeess.SY ·2026-09-18 ·Zichen Wang, Peter Seiler, Geir Dullerud, Bin Hu
similarity 0.48
Abstract

Semidefinite programming (SDP) certificates for feedback systems containing deep neural networks (NNs) typically scale with the total number of neurons, whereas small-gain tests are scalable but can be highly conservative. This paper develops a unified and scalable framework for incremental robust stability and performance analysis of feedback interconnections involving high-dimensional NNs and unmodeled dynamics. By combining a structured decomposition of the full-order SDP condition with scalable Lipschitz constant estimation algorithms, we derive reduced verification conditions that certify incremental convergence and incremental $\ell_2$-gain bounds. The dimensions of the resulting control-analysis linear matrix inequalities (LMIs) depend only on the widths of the last two network layers and are \textit{independent of network depth}. The framework preserves the coupling between the plant and the NN, with the incremental small-gain condition recovered as a special case. To further reduce conservatism, we develop a multi-round alternating update scheme that iteratively refines the coupling variables while preserving scalability. Numerical experiments show that the proposed framework achieves state-of-the-art incremental $\ell_2$-gain bounds for large-scale NN feedback systems.

0.35

L1 Minimum Energy Estimation of Positive Systems

eess.SY math.OC ·2026-10-14 ·Alba Gurpegui Ramón
similarity 0.46
Abstract · 7 figures. Under review

We present a novel class of minimum energy estimation problems for positive linear systems with linear costs subject to coupled process and measurement disturbances, where the latter is bounded by the state and the former is bounded by the noise. Through dynamic programming we show that the problem admits explicit solutions. Remarkably, the Luenberger observer structure of the optimal estimator emerges from the optimization itself, with a switching gain that inherits the sparsity of the disturbance constraints, and it is obtained from a differential equation in the finite horizon case. In the infinite horizon case, an algebraic equation characterizes the limit of the finite-horizon solution and yields a stationary estimator with a static gain. We introduce two distinct notions of detectability to characterize when the static gain stabilizes the error dynamics while preserving their positivity, and analyze under which conditions the stationary solution can be formulated as a linear program. We further establish that a disturbance perturbation of finite L1-norm yields an estimation error of finite L1-norm. The framework is illustrated on a large-scale irrigation network.

0.22

A graph decomposition approach for the synthesis of EMPs in directed acyclic networks

eess.SY ·2026-10-22 ·Eduardo Mapurunga, Michel Gevers, Alexandre Bazanella
unusual similarity 0.46
Abstract · Paper submitted to Automatica

This paper considers the identifiability of dynamical networks whose topology is a Directed Acyclic Graph (DAG), in the context where not all nodes are excited and not all nodes are measured. The objective is to construct a valid and parsimonious Excitation and Measurement Pattern (EMP), i.e. a selection of excited and measured nodes, that allows to identify the whole network with a small number of excitations and measurements. We show first that a DAG can be decomposed into a set of trees and parallel paths networks. We propose an algorithm that achieves this decomposition and computes an EMP that combines EMPs for the individual trees and parallel paths networks. We formally show that this algorithm yields an EMP capable of identifying the whole network.

0.34