Positive definite completion problems for Bayesian networks

DOI10.1137/110861051zbMATH Open1253.15038arXiv1201.0310OpenAlexW2009686967MaRDI QIDQ2910972FDOQ2910972

Authors: Emanuel Ben-David, Bala Rajaratnam 

Publication date: 12 September 2012

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Abstract: A positive definite completion problem pertains to determining whether the unspecified positions of a partial (or incomplete) matrix can be completed in a desired subclass of positive definite matrices. In this paper we study an important and new class of positive definite completion problems where the desired subclasses are the spaces of covariance and inverse-covariance matrices of probabilistic models corresponding to directed acyclic graph models (also known as Bayesian networks). We provide fast procedures that determine whether a partial matrix can be completed in either of these spaces and thereafter proceed to construct the completed matrices. We prove an analog of the positive definite completion result for undirected graphs in the context of directed acyclic graphs, and thus proceed to characterize the class of DAGs which can always be completed. We also proceed to give closed form expressions for the inverse and the determinant of a completed matrix as a function of only the elements of the corresponding partial matrix.

Full work available at URL: https://arxiv.org/abs/1201.0310

Recommendations

• Probabilistic completion of nondeterministic models
• scientific article; zbMATH DE number 1746708
• Analysis of Bayesian networks via prob-solvable loops
• scientific article; zbMATH DE number 2036245
• Exact Bayesian structure discovery in Bayesian networks
• Parameterized complexity results for exact Bayesian network structure learning
• Approximate inference in Bayesian networks: parameterized complexity results

zbMATH Keywords

Bayesian networksdirected acyclic graphCholesky decompositionpositive definite matricesdeterminantsperfect graphsinversespartial matricesdecomposable graphspositive definite completioninverse-covariance matrices

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Matrix completion problems (15A83) Hermitian, skew-Hermitian, and related matrices (15B57) Theory of matrix inversion and generalized inverses (15A09) Positive matrices and their generalizations; cones of matrices (15B48) Determinants, permanents, traces, other special matrix functions (15A15) Perfect graphs (05C17)

Cited In (8)

• The critical exponent: a novel graph invariant
• Generation of positiv definite matrices with constraints to validate network algorithms for micro array data.
• Positive definite Hankel matrix completions and Hamburger moment completions
• Critical exponents of graphs
• Weighted positive binary decision diagrams for exact probabilistic inference
• On the Letac-Massam conjecture and existence of high dimensional Bayes estimators for graphical models
• A review of Gaussian Markov models for conditional independence
• Completion problem with partial correlation vines

This page was built for publication: Positive definite completion problems for Bayesian networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2910972)