Certified by:

of Doctor of Philosophy in Electrical Engineering and Computer Science In undirected graphical models, each node represents a random variable while the set of edges specifies the conditional independencies of the underlying distri-bution. When the random variables are jointly Gaussian, the models are called Gaussian graphical models (GGMs) or Gauss Markov random fields. In this the-sis, we address several important problems in the study of GGMs. The first problem is to perform inference or sampling when the graph struc-ture and model parameters are given. For inference in graphs with cycles, loopy belief propagation (LBP) is a purely distributed algorithm, but it gives inaccurate variance estimates in general and often diverges or has slow convergence. Previ-ously, the hybrid feedback message passing (FMP) algorithm was developed to enhance the convergence and accuracy, where a special protocol is used among the nodes in a pseudo-FVS (an FVS, or feedback vertex set, is a set of nodes whose removal breaks all cycles) while standard LBP is run on the subgraph excludin