Abstract
Identifying the underlying topology of networked linear dynamical systems (LDS) is a fundamental challenge in fields ranging from power grid management to biological network analysis. Traditional topology learning algorithms often rely on the assumption of independent and identically distributed (i.i.d.) white noise as exogenous input. However, real-world systems are frequently driven by temporally correlated "colored" noise, which can lead to the detection of spurious "ghost edges." This paper introduces a regularized Wiener filter estimator capable of exact topology recovery under non-white excitation. We prove that the required number of observations scales logarithmically with the network size, even when data is collected from a single continuous trajectory.
Introduction
The problem of "passive" topology learning involves identifying hidden connections within a network of interacting components solely through observation. In a Networked Linear Dynamical System (LDS), the state of each node evolves based on its neighbors' states and external forces. A significant hurdle in this field is the presence of unobserved, temporally correlated external inputs. Standard methods often fail in these scenarios, incorrectly identifying connections where none exist because they cannot distinguish between internal system dynamics and external correlations. This work addresses the finite-sample regime, providing a robust estimator that accounts for colored noise.
Methodology
The core of the proposed approach is a Regularized Wiener Filter Estimator. This method leverages three key techniques:
- Non-Causal Regression: Unlike standard causal models that only look at past states, the Wiener filter uses the entire trajectory. This non-causal approach is mathematically equivalent to analyzing the inverse power spectral density, allowing the system to "cancel out" the effects of correlated external inputs.
- $l_1$-Regularization: To handle high-dimensional settings where the number of nodes ($p$) may exceed the number of time points, a Lasso-like penalty is added to encourage sparsity in the recovered graph.
- Two-Step Thresholding: The algorithm first identifies a "two-hop" neighborhood—nodes that are either direct neighbors or neighbors-of-neighbors. A subsequent thresholding step prunes these connections to isolate the true direct edges.
Data Collection Scenarios
The researchers evaluated the estimator under two distinct data-collection regimes:
- Restart & Record: This involves observing multiple independent, short bursts of system activity.
- Consecutive Trajectory: This involves a single, continuous stream of data. The latter is significantly more challenging to analyze due to the temporal dependencies between data points, yet it is often the only feasible method in real-world settings.
Key Results and Insights
The most significant theoretical contribution is the proof that the sample complexity for perfect network recovery grows only logarithmically with the number of nodes ($O(\log p)$). This efficiency makes the method suitable for massive networks.
Numerical simulations on two-dimensional square grid graphs (ranging from 4 to 140 nodes) validated these findings. The regularized approach significantly outperformed traditional benchmarks like the Graphical Lasso, which struggled to account for correlated noise. For a 24-node grid, the method achieved zero errors in topology reconstruction with far fewer samples than conservative theoretical estimates predicted.
Conclusion and Future Work
This work provides a rigorous framework for learning the topology of LDS under realistic, non-white excitation. While currently focused on first-order discrete-time systems and undirected graphs, the use of frequency-domain analysis and non-causal filtering opens doors for extensions to higher-order models and directed networks. Future research will explore the application of these techniques to non-linear dynamics and more complex real-world datasets.
Summary updated