### Browsing by Subject "Sample complexity analysis"

Now showing 1 - 1 of 1

###### Results Per Page

###### Sort Options

Item Network Topology And Causal Structure Recovery In Linear Dynamical Systems(2024-04) Shaikh Veedu, MishfadShow more Modeling and representing complex systems by a network of interacting agents provide cost-effective and efficient ways to simulate, design, and test the solutions to real-world problems in science and engineering. Applications such as finance, neuroscience, climate science, power grids, etc. involve modeling the agents and states that interact and evolve dynamically and can contain feedback loops. Most existing literature assumes a static relationship between the agents, which fails to capture the dependencies across time. Learning the interdependency (topology) and cause-and-effect structure among the agents is therefore of importance and having an active interest in the graphical network representation and effective modeling of the dynamical systems. Identifying the unknown interaction structure can in general be classified into active and passive techniques. The active techniques involve intervention in the normal operation of the system by injecting external signals and/or modifying agents in the system. Critical applications in financial markets, power grids, meteorological systems, etc. do not allow active intervention in the system. In such critical applications passive methods, which infer the information from the observed time-series measurements, are applied. In the passive techniques, the evolution of the underlying system is mathematically modeled using a generative model, where the agents are excited with a disturbance signal. In this thesis, we study passive techniques to identify the interdependency and the influence pathways in the dynamical systems, where the agents interact linearly. Further, in practice, it might not be viable to observe all the states in the system. Thus, it is imperative to identify the influence structure (network topology) when the system involves hidden/latent states, which is a challenging problem. In Chapter 2, we provide a novel algorithm to identify the interdependency structure, including the dependency among the latent nodes, when only a subset of the nodes/agents provide the time-series measurements. In many applications, the proposed algorithm retrieves the exact influence pathways, with partial directions, including that of the latent nodes. Another practical issue is that some of the disturbances at the agents themselves can be correlated, which renders the agents' influence structure indistinguishable from passive observations. Examples of such systems are observable in applications such as power grids and stock markets. Learning the network topology in the presence of such correlated disturbances is difficult as it is required to extract the dependency between the disturbances first. In Chapter 3, we show that the correlation between the disturbances is equivalent to the dependency induced by the latent nodes. The network topology only provides the correlation structure of the network of agents. It is well known that correlation is not equivalent to causation and the cause-effect structure contains more information than the correlation structure. In many applications in medicine, biology, and statistics the correlation structure might not be sufficient. Here, it is necessary to know the causal structure of the underlying dynamics. In Chapter 4, we provide an algorithm to learn the causal structure of a linear dynamical system when the agents are excited by identical noise sources. Further, a sample complexity analysis is provided, which finds matching upper and lower bounds on the number of samples required to obtain a given error performance. In general, without intervention and assumptions on the generative models, it is impossible to identify a complete causal structure. The best one can identify without further restriction is an equivalent set of graphs with the same conditional correlation structure, Essential Graphs. In Chapter 5, we provide algorithms to estimate the essential graph in linear dynamical systems using the Wiener filter (WF). The conventional time-domain approach to computing WF is computationally expensive. To speed up the calculation, we propose a fast Fourier transform-based computationally efficient approach to estimate the Wiener filter. The conventional probability notion of CI fails to capture the CI notion in a stochastic process. To tackle this problem, we propose a novel probability notion of CI for stochastic processes in the frequency domain. This notion is used to extend the notions of the front-door and the back-door criterion from static graphical models to linear dynamical systems, where the nodal states are stochastic processes.Show more