Koopman Lifting with Certified Error Bounds for Joint Inference in Nonlinear Networks
Pith reviewed 2026-06-26 23:25 UTC · model grok-4.3
The pith
Koopman operator embedding with separable node-wise dictionaries converts joint state and topology inference in nonlinear networks into a linear filtering task equipped with explicit three-term error bounds.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Under a separable-dictionary condition, block sparsity of the lifted coupling operator is isomorphic to the graph topology, enabling group-sparse regularization; the framework supplies a three-term certified mean-squared error bound that decomposes error into Koopman truncation, observation noise, and topology residual, with monotone consistency as dictionary dimension grows.
What carries the argument
The structural homomorphism lemma, which proves that block sparsity in the lifted coupling operator corresponds isomorphically to the original graph topology when the dictionary is separable across nodes.
If this is right
- Standard linear tools such as Kalman filters become applicable to the lifted system for state estimation.
- Topology inference reduces to a convex block-structured group-sparse problem solvable by ADMM with linear convergence guarantees.
- The three-term error bound certifies accuracy of both state estimates and recovered topology.
- An exponential forgetting factor extends the method to time-varying topologies while preserving convergence.
Where Pith is reading between the lines
- The error decomposition could be used to adaptively enlarge the dictionary only in directions that reduce the dominant error term.
- If separability holds for common physical dictionaries, the same lifting might apply to inverse problems on other networked systems such as power grids or neural circuits.
- The polynomial scaling reported for high-dimensional cases suggests the approach could be tested on networks with thousands of nodes where particle filters become intractable.
Load-bearing premise
The dictionary used for the Koopman lifting must be separable node by node so that block sparsity in the lifted operator directly reflects the graph topology.
What would settle it
A concrete network example in which the separable-dictionary condition holds yet the group-sparse solution recovers a coupling operator whose block-sparsity pattern differs from the true graph edges, or in which increasing dictionary dimension fails to reduce the certified mean-squared error.
Figures
read the original abstract
Jointly inferring latent node states and unknown network topology in nonlinear graphical dynamical systems is a fundamental yet largely unsolved problem, where the mutual entanglement of continuous states and discrete structure renders accurate recovery of either quantity critically dependent on the other. We propose \textbf{Koopman-GKFA} (Koopman Group-sparse Kalman Filter--ADMM), a unified framework that lifts nonlinear network dynamics into an approximately linear system via Koopman operator embedding with a separable node-wise dictionary, enabling optimal linear filtering for state estimation and provably convergent convex optimization for topology inference. Three theoretical contributions underpin the framework: (i)~a \emph{structural homomorphism lemma} proving that, under a separable-dictionary condition, block sparsity of the lifted coupling operator is isomorphic to the graph topology, providing the rigorous foundation for group-sparse regularization; (ii)~a block-structured group-sparse ADMM topology subproblem with certified linear convergence, extended by an exponential forgetting factor to track time-varying topologies; and (iii)~a \emph{three-term certified mean-squared error bound} that decomposes total estimation error into Koopman truncation, observation noise, and topology residual components, with monotone consistency established as the dictionary dimension grows. Extensive experiments on synthetic benchmarks (Kuramoto oscillators, Hill-kinetics gene-regulatory networks) and real-world datasets (NGSIM US-101, DREAM4) demonstrate that Koopman-GKFA consistently outperforms EKF-, UKF-, and particle-filter-based joint estimators in both state estimation and topology recovery, while exhibiting polynomial computational scaling and strong robustness in high-dimensional nonlinear settings.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proposes Koopman-GKFA, a framework for joint state and topology inference in nonlinear network dynamical systems. It lifts the dynamics via Koopman embedding with a separable node-wise dictionary to obtain an approximately linear system, then applies linear filtering for states and group-sparse ADMM for topology recovery. The central claims are (i) a structural homomorphism lemma showing that, under a separable-dictionary condition, block sparsity of the lifted coupling operator is isomorphic to the underlying graph topology; (ii) a block-structured group-sparse ADMM subproblem with certified linear convergence (extended by exponential forgetting for time-varying topologies); and (iii) a three-term certified MSE bound decomposing error into Koopman truncation, observation noise, and topology residual, with monotone consistency as dictionary dimension increases. Experiments on Kuramoto oscillators, Hill-kinetics networks, NGSIM, and DREAM4 report superior performance over EKF/UKF/particle-filter baselines.
Significance. If the structural homomorphism lemma and the three-term bound can be rigorously established with the separable-dictionary condition explicitly characterized and verified on the benchmark dictionaries, the work would supply a principled, certifiably consistent approach to joint inference that directly ties topology recovery to group-sparse regularization. The monotone consistency result with growing dictionary dimension and the polynomial scaling claim would be notable strengths for high-dimensional nonlinear network problems.
major comments (2)
- [Abstract (contribution (i))] Abstract, contribution (i): The structural homomorphism lemma asserts that block sparsity of the lifted coupling operator is isomorphic to graph topology under a 'separable-dictionary condition,' yet the manuscript supplies no explicit characterization of the function class for which separability holds. It is also not shown that the dictionaries employed in the Kuramoto and Hill-kinetics experiments satisfy the condition. This premise is load-bearing for the justification of group-sparse regularization and for the subsequent ADMM and error-bound guarantees.
- [Abstract (contribution (iii))] Abstract, contribution (iii): The three-term certified MSE bound is stated to decompose total error into Koopman truncation, observation noise, and topology residual components with monotone consistency as dictionary dimension grows, but the derivation of the decomposition and any numerical verification of bound tightness are not referenced. Without these, the 'certified' claim cannot be assessed as independent of the final performance numbers.
minor comments (2)
- [Abstract] The abstract lists four datasets but does not report the specific dictionary dimensions or forgetting-factor values used, which would help readers assess the practical scaling.
- [Abstract] Notation for the lifted coupling operator and the separable dictionary should be introduced with a short equation or definition even in the abstract to improve readability.
Simulated Author's Rebuttal
We thank the referee for the constructive feedback highlighting the need for greater explicitness in the theoretical claims. We address each major comment below and will make the indicated revisions to strengthen the manuscript.
read point-by-point responses
-
Referee: Abstract, contribution (i): The structural homomorphism lemma asserts that block sparsity of the lifted coupling operator is isomorphic to graph topology under a 'separable-dictionary condition,' yet the manuscript supplies no explicit characterization of the function class for which separability holds. It is also not shown that the dictionaries employed in the Kuramoto and Hill-kinetics experiments satisfy the condition. This premise is load-bearing for the justification of group-sparse regularization and for the subsequent ADMM and error-bound guarantees.
Authors: We agree that an explicit characterization of the separable-dictionary condition is required. The condition is used in the proof of the homomorphism lemma (Lemma 1) but is not stated as a standalone definition. In the revision we will insert a formal definition (Definition 2) characterizing separable dictionaries as those that are direct sums of node-local functions with no cross-node interactions. We will also add Proposition 1 proving that common node-wise bases (polynomials, Fourier, RBFs) satisfy the condition by construction, and we will explicitly verify and state that the dictionaries used in the Kuramoto (node-wise Fourier) and Hill-kinetics (node-wise sigmoidal) experiments meet this definition. These additions will be placed immediately before the lemma statement. revision: yes
-
Referee: Abstract, contribution (iii): The three-term certified MSE bound is stated to decompose total error into Koopman truncation, observation noise, and topology residual components with monotone consistency as dictionary dimension grows, but the derivation of the decomposition and any numerical verification of bound tightness are not referenced. Without these, the 'certified' claim cannot be assessed as independent of the final performance numbers.
Authors: The decomposition and monotone consistency are derived in Theorem 3 (Section 4) via the triangle inequality applied to the lifted-state error, with each term bounded separately and the dictionary-dimension consistency following from the universal approximation property of the chosen function class. The proof is in Appendix B. We acknowledge, however, that the abstract and main-text statements lack explicit forward references to the theorem and that no numerical check of bound tightness is provided. In the revision we will add cross-references in the abstract and Section 4, include a new figure (Figure 8) comparing the certified bound against empirical MSE on the Kuramoto and Hill-kinetics examples, and expand the appendix proof with an additional intermediate lemma for readability. revision: yes
Circularity Check
No circularity: derivations rest on external assumptions and independent proofs
full rationale
The paper's core claims—the structural homomorphism lemma under an explicitly stated separable-dictionary condition, the block-structured ADMM with linear convergence, and the three-term MSE bound with monotone consistency—are presented as derived from the Koopman lifting and convex optimization setup without reducing any prediction or result to a fitted parameter or self-referential definition. No equations equate outputs to inputs by construction, no fitted quantities are relabeled as predictions, and no load-bearing steps rely on self-citations. The separable-dictionary condition functions as a premise rather than a derived or tautological element, leaving the framework self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
free parameters (2)
- dictionary dimension
- exponential forgetting factor
axioms (1)
- domain assumption separable-dictionary condition
Reference graph
Works this paper leans on
-
[1]
Power system dynamic state es- timation: Motivations, definitions, methodologies, and future work
Junbo Zhao, Antonio G´ omez-Exp´ osito, Marcos Netto, Lamine Mili, Ali Abur, Vladimir Terzija, In- nocent Kamwa, Bikash Pal, Abhinav Kumar Singh, Junjian Qi, et al. Power system dynamic state es- timation: Motivations, definitions, methodologies, and future work. IEEE Transactions on Power Sys- tems, 34(4):3188–3198, 2019
2019
-
[2]
How to infer gene networks from expression profiles
Mukesh Bansal, Vincenzo Belcastro, Alberto Ambesi-Impiombato, and Diego Di Bernardo. How to infer gene networks from expression profiles. Molecular Systems Biology, 3:78, 2007
2007
-
[3]
W. Helly. Simulation of bottlenecks in single-lane traffic flow. In Proceedings of Symposium on Theory Traffic Flow, pages 207–238, 1959
1959
-
[4]
Nonlinear state estimation for hu- manoid robot walking
Stylianos Piperakis, Maria Koskinopoulou, and Panos Trahanias. Nonlinear state estimation for hu- manoid robot walking. IEEE Robotics and Automa- tion Letters, 3(4):3347–3354, 2018
2018
-
[5]
Learning graphs from data: A signal representation perspective
Xiaowen Dong, Dorina Thanou, Michael Rabbat, and Pascal Frossard. Learning graphs from data: A signal representation perspective. IEEE Signal Pro- cessing Magazine, 36(3):44–63, 2019
2019
-
[6]
Network topology in- ference from spectral templates
Santiago Segarra, Antonio G Marques, Gonzalo Ma- teos, and Alejandro Ribeiro. Network topology in- ference from spectral templates. IEEE Transactions on Signal and Information Processing over Networks, 3(3):467–483, 2017
2017
-
[7]
Connecting the dots: Identifying network structure via graph signal pro- cessing
Gonzalo Mateos, Santiago Segarra, Antonio G Mar- ques, and Alejandro Ribeiro. Connecting the dots: Identifying network structure via graph signal pro- cessing. IEEE Signal Processing Magazine, 36(3):16– 43, 2019
2019
-
[8]
Topology inference for network sys- tems: Causality perspective and nonasymptotic per- formance
Yushan Li, Jianping He, Cailian Chen, and Xin- ping Guan. Topology inference for network sys- tems: Causality perspective and nonasymptotic per- formance. IEEE Transactions on Automatic Control, 69(6):3483–3498, 2023
2023
-
[9]
Infer- ring topology of network systems by few excitations: Probability analysis and fusion
Qing Jiao, Yushan Li, and Jianping He. Infer- ring topology of network systems by few excitations: Probability analysis and fusion. IEEE Transactions on Automatic Control, 2025
2025
-
[10]
A new approach to linear filtering and prediction problems
Rudolph Emil Kalman. A new approach to linear filtering and prediction problems. Journal of Basic Engineering, 82(1):35–45, 1960
1960
-
[11]
Adaptation, learning, and optimiza- tion over networks
Ali H Sayed. Adaptation, learning, and optimiza- tion over networks. Foundations and Trends ® in Machine Learning, 7(4-5):311–801, 2014
2014
-
[12]
Joint graph learning and sig- nal recovery via Kalman filter for multivariate auto-regressive processes
Mahmoud Ramezani-Mayiami and Baltasar Beferull-Lozano. Joint graph learning and sig- nal recovery via Kalman filter for multivariate auto-regressive processes. In Proceedings of Eu- ropean Signal Processing Conference (EUSIPCO) , pages 907–911. IEEE, 2018
2018
-
[13]
Joint topology learning and graph signal recovery via Kalman filter in causal data processes
Mahmoud Ramezani-Mayiami and Baltasar Beferull-Lozano. Joint topology learning and graph signal recovery via Kalman filter in causal data processes. In Proceedings of International Workshop on Machine Learning for Signal Processing (MLSP), pages 1–6. IEEE, 2018
2018
-
[14]
Graphical in- ference in linear-Gaussian state-space models
V´ ıctor Elvira and Emilie Chouzenoux. Graphical in- ference in linear-Gaussian state-space models. IEEE Transactions on Signal Processing , 70:4757–4771, 2022
2022
-
[15]
Joint state estimation and topology in- ference for graphical dynamical systems
Pengfei Fang, Wenling Li, Jia Song, Xiaoming Li, and Li Ma. Joint state estimation and topology in- ference for graphical dynamical systems. Signal Pro- cessing, 237:110070, 2025
2025
-
[16]
Distributed optimization and statisti- cal learning via the alternating direction method of multipliers
Parikh Neal, Chu Eric, Peleato Borja, and Eckstein Jonathan. Distributed optimization and statisti- cal learning via the alternating direction method of multipliers. Foundations and Trends ® in Machine learning, 3(1):1–122, 2011
2011
-
[17]
On the linear convergence of the alternating direction method of multipliers
Mingyi Hong and Zhi-Quan Luo. On the linear convergence of the alternating direction method of multipliers. Mathematical Programming, 162(1):165– 199, 2017
2017
-
[18]
Application of state-space meth- ods to navigation problems
Stanley F Schmidt. Application of state-space meth- ods to navigation problems. In Advances in Control Systems, volume 3, pages 293–340. Elsevier, 1966
1966
-
[19]
Unscented filtering and nonlinear estimation
Simon J Julier and Jeffrey K Uhlmann. Unscented filtering and nonlinear estimation. Proceedings of the IEEE, 92(3):401–422, 2004
2004
-
[20]
A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking
M Sanjeev Arulampalam, Simon Maskell, Neil Gor- don, and Tim Clapp. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Transactions on Signal Processing, 50(2):174– 188, 2002
2002
-
[21]
Extended Kalman filter for graph signals in nonlin- ear dynamic systems
Guy Sagi, Nir Shlezinger, and Tirza Routtenberg. Extended Kalman filter for graph signals in nonlin- ear dynamic systems. In Proceedings of IEEE Inter- national Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1–5. IEEE, 2023. 25
2023
-
[22]
Unscented Kalman filter of graph signals
Wenling Li, Xiaoyan Fu, Bin Zhang, and Yang Liu. Unscented Kalman filter of graph signals. Automat- ica, 148:110796, 2023
2023
-
[23]
State-space network topology identifi- cation from partial observations
Mario Coutino, Elvin Isufi, Takanori Maehara, and Geert Leus. State-space network topology identifi- cation from partial observations. IEEE Transactions on Signal and Information Processing over Networks, 6:211–225, 2020
2020
-
[24]
In- ductive representation learning on large graphs
Will Hamilton, Zhitao Ying, and Jure Leskovec. In- ductive representation learning on large graphs. In Proceeding of Advances in Neural Information Pro- cessing Systems (NeurIPS) , volume 30, 2017
2017
-
[25]
GSP- KalmanNet: Tracking graph signals via neural-aided Kalman filtering
Itay Buchnik, Guy Sagi, Nimrod Leinwand, Yuval Loya, Nir Shlezinger, and Tirza Routtenberg. GSP- KalmanNet: Tracking graph signals via neural-aided Kalman filtering. IEEE Transactions on Signal Pro- cessing, 72:3700–3716, 2024
2024
-
[26]
Hamiltonian systems and transformation in Hilbert space
Bernard O Koopman. Hamiltonian systems and transformation in Hilbert space. Proceedings of the National Academy of Sciences , 17(5):315–318, 1931
1931
-
[27]
Spectral properties of dynamical sys- tems, model reduction and decompositions
Igor Mezi´ c. Spectral properties of dynamical sys- tems, model reduction and decompositions. Nonlin- ear Dynamics, 41(1):309–325, 2005
2005
-
[28]
Dynamic mode decomposition of numerical and experimental data
Peter J Schmid. Dynamic mode decomposition of numerical and experimental data. Journal of Fluid Mechanics, 656:5–28, 2010
2010
-
[29]
A data–driven approxima- tion of the Koopman operator: Extending dynamic mode decomposition
Matthew O Williams, Ioannis G Kevrekidis, and Clarence W Rowley. A data–driven approxima- tion of the Koopman operator: Extending dynamic mode decomposition. Journal of Nonlinear Science , 25(6):1307–1346, 2015
2015
-
[30]
On convergence of extended dynamic mode decomposition to the Koopman operator
Milan Korda and Igor Mezi´ c. On convergence of extended dynamic mode decomposition to the Koopman operator. Journal of Nonlinear Science , 28(2):687–710, 2018
2018
-
[31]
Koopman invariant subspaces and finite linear representations of non- linear dynamical systems for control
Steven L Brunton, Bingni W Brunton, Joshua L Proctor, and J Nathan Kutz. Koopman invariant subspaces and finite linear representations of non- linear dynamical systems for control. PloS one , 11(2):e0150171, 2016
2016
-
[32]
Generalizing Koopman theory to allow for in- puts and control
Joshua L Proctor, Steven L Brunton, and J Nathan Kutz. Generalizing Koopman theory to allow for in- puts and control. SIAM Journal on Applied Dynam- ical Systems, 17(1):909–930, 2018
2018
-
[33]
Koopman- based lifting techniques for nonlinear systems identi- fication
Alexandre Mauroy and Jorge Goncalves. Koopman- based lifting techniques for nonlinear systems identi- fication. IEEE Transactions on Automatic Control , 65(6):2550–2565, 2019
2019
-
[34]
Bilineariza- tion, reachability, and optimal control of control- affine nonlinear systems: A Koopman spectral ap- proach
Debdipta Goswami and Derek A Paley. Bilineariza- tion, reachability, and optimal control of control- affine nonlinear systems: A Koopman spectral ap- proach. IEEE Transactions on Automatic Control , 67(6):2715–2728, 2021
2021
-
[35]
Optimal construc- tion of Koopman eigenfunctions for prediction and control
Milan Korda and Igor Mezi´ c. Optimal construc- tion of Koopman eigenfunctions for prediction and control. IEEE Transactions on Automatic Control , 65(12):5114–5129, 2020
2020
-
[36]
Deep learning for universal linear embeddings of nonlinear dynamics
Bethany Lusch, J Nathan Kutz, and Steven L Brun- ton. Deep learning for universal linear embeddings of nonlinear dynamics. Nature Communications , 9(1):4950, 2018
2018
-
[37]
Model selection and estima- tion in regression with grouped variables
Ming Yuan and Yi Lin. Model selection and estima- tion in regression with grouped variables. Journal of the Royal Statistical Society Series B: Statistical Methodology, 68(1):49–67, 2006
2006
-
[38]
Tracking switched dynamic network topologies from informa- tion cascades
Brian Baingana and Georgios B Giannakis. Tracking switched dynamic network topologies from informa- tion cascades. IEEE Transactions on Signal Process- ing, 65(4):985–997, 2016
2016
-
[39]
Proximal splitting methods in signal processing
Patrick L Combettes and Jean-Christophe Pesquet. Proximal splitting methods in signal processing. In Fixed-Point Algorithms for Inverse Problems in Science and Engineering , pages 185–212. Springer, 2011
2011
-
[40]
On model selection con- sistency of LASSO
Peng Zhao and Bin Yu. On model selection con- sistency of LASSO. Journal of Machine Learning Research, 7:2541–2563, 2006
2006
-
[41]
Consistency of the group LASSO and multiple kernel learning
Francis R Bach. Consistency of the group LASSO and multiple kernel learning. Journal of Machine Learning Research, 9(6), 2008
2008
-
[42]
Chemical turbulence
Yoshiki Kuramoto. Chemical turbulence. In Chemi- cal Oscillations, Waves, and Turbulence , pages 111–
-
[43]
On the assessment of vehicle trajectory data accuracy and application to the Next Gener- ation SIMulation (NGSIM) program data
Vincenzo Punzo, Maria Teresa Borzacchiello, and Bi- agio Ciuffo. On the assessment of vehicle trajectory data accuracy and application to the Next Gener- ation SIMulation (NGSIM) program data. Trans- portation Research Part C: Emerging Technologies , 19(6):1243–1262, 2011
2011
-
[44]
Generating realistic in silico gene networks for performance assessment of reverse engineering methods
Daniel Marbach, Thomas Schaffter, Claudio Mat- tiussi, and Dario Floreano. Generating realistic in silico gene networks for performance assessment of reverse engineering methods. Journal of Computa- tional Biology, 16(2):229–239, 2009
2009
-
[45]
Matrix Anal- ysis
Roger A Horn and Charles R Johnson. Matrix Anal- ysis. Cambridge University Press, 2 edition, 2012. 26
2012
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.