TY - JOUR
T1 - Topology Learning of Linear Dynamical Systems With Latent Nodes Using Matrix Decomposition
AU - Veedu, Mishfad
AU - Harish, Doddi
AU - Salapaka, Murti V.
N1 - Publisher Copyright:
IEEE
PY - 2022/11/1
Y1 - 2022/11/1
N2 - In this article, we present a novel approach to reconstruct the topology of networked linear dynamical systems with latent nodes. The network is allowed to have directed loops and bi-directed edges. The main approach relies on the unique decomposition of the inverse of power spectral density matrix (IPSDM) obtained from observed nodes as a sum of sparse and low-rank matrices. We provide conditions and methods for decomposing the IPSDM into sparse and low-rank components. The sparse component yields moral graph (MG) associated with the observed nodes, and the low-rank component retrieves parents, children and spouses (the Markov Blanket) of the hidden nodes. The article provides necessary and sufficient conditions for the unique decomposition of a given skew symmetric matrix into sum of a sparse skew symmetric and a low-rank skew symmetric matrices. For a large class of systems, the unique decomposition of imaginary part of the IPSDM of observed nodes, a skew symmetric matrix, into the sparse and the low-rank components is sufficient to identify the MG of the observed nodes as well as the Markov Blanket of latent nodes. For a large class of systems, all spurious links in the MG formed by the observed nodes can be identified. Assuming conditions on hidden nodes required for identifiability, links between hidden and observed nodes can be reconstructed, thus retrieving the exact topology of the network from the IPSDM. Moreover, for finite data, we provide bounds on entry-wise distance between the true and the estimated IPSDMs.
AB - In this article, we present a novel approach to reconstruct the topology of networked linear dynamical systems with latent nodes. The network is allowed to have directed loops and bi-directed edges. The main approach relies on the unique decomposition of the inverse of power spectral density matrix (IPSDM) obtained from observed nodes as a sum of sparse and low-rank matrices. We provide conditions and methods for decomposing the IPSDM into sparse and low-rank components. The sparse component yields moral graph (MG) associated with the observed nodes, and the low-rank component retrieves parents, children and spouses (the Markov Blanket) of the hidden nodes. The article provides necessary and sufficient conditions for the unique decomposition of a given skew symmetric matrix into sum of a sparse skew symmetric and a low-rank skew symmetric matrices. For a large class of systems, the unique decomposition of imaginary part of the IPSDM of observed nodes, a skew symmetric matrix, into the sparse and the low-rank components is sufficient to identify the MG of the observed nodes as well as the Markov Blanket of latent nodes. For a large class of systems, all spurious links in the MG formed by the observed nodes can be identified. Assuming conditions on hidden nodes required for identifiability, links between hidden and observed nodes can be reconstructed, thus retrieving the exact topology of the network from the IPSDM. Moreover, for finite data, we provide bounds on entry-wise distance between the true and the estimated IPSDMs.
KW - Latent variable graphical models
KW - matrix decomposition
KW - network topology
KW - structure learning
UR - http://www.scopus.com/inward/record.url?scp=85118660529&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85118660529&partnerID=8YFLogxK
U2 - 10.1109/TAC.2021.3124979
DO - 10.1109/TAC.2021.3124979
M3 - Article
AN - SCOPUS:85118660529
SN - 0018-9286
VL - 67
SP - 5746
EP - 5761
JO - IEEE Transactions on Automatic Control
JF - IEEE Transactions on Automatic Control
IS - 11
ER -