Title: Robust estimation of tree structured Gaussian Graphical Model,
Abstract: Consider jointly Gaussian random variables whose conditional independence
structure is specified by a graphical model. If we observe realizations of the
variables, we can compute the covariance matrix, and it is well known that the
support of the inverse covariance matrix corresponds to the edges of the
graphical model. Instead, suppose we only have noisy observations. If the noise
at each node is independent, we can compute the sum of the covariance matrix
and an unknown diagonal. The inverse of this sum is (in general) dense. We ask:
can the original independence structure be recovered? We address this question
for tree structured graphical models. We prove that this problem is
unidentifiable, but show that this unidentifiability is limited to a small
class of candidate trees. We further present additional constraints under which
the problem is identifiable. Finally, we provide an O(n^3) algorithm to find
this equivalence class of trees.