Positive semidefinite matrices with a given sparsity pattern

DOI10.1016/0024-3795(88)90240-6zbMath0655.15016OpenAlexW2034769312MaRDI QIDQ1109100

Jim Agler, J. William Helton, Leiba Rodman, Scott A. McCullough

Publication date: 1988

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(88)90240-6

zbMATH Keywords

completion problemsalgorithmic graph theorysparsity patterncone of positive matricesextremal matricesorder of pattern

Mathematics Subject Classification ID

Factorization of matrices (15A23) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48) Algebraic systems of matrices (15A30) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

Minimal separators of 2-chordal graphs, Multivariate Gaussians, semidefinite matrix completion, and convex algebraic geometry, Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without \(K_{5}\) minors, Decomposition Methods for Sparse Matrix Nearness Problems, Sparse sums of squares on finite abelian groups and improved semidefinite lifts, Extermal positive semidefinite matrices with given sparsity pattern, Nonchordal positive semidefinite stochastic matrices^∗, Matrices attaining the minimum semidefinite rank of a chordal graph, Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures, On representing the positive semidefinite cone using the second-order cone, Do Sums of Squares Dream of Free Resolutions?, Linear optimization over homogeneous matrix cones, Sparse polynomial optimisation for neural network verification, Chordal sparsity for SDP-based neural network verification, Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks, Critical exponents of graphs, Digital Simulation of Single Qubit Markovian Open Quantum Systems: A Tutorial, Sum-of-squares chordal decomposition of polynomial matrix inequalities, Sparse matrix decompositions and graph characterizations, Graphs with sparsity order at most two: the complex case, Maximum likelihood threshold and generic completion rank of graphs, A panorama of positivity. II: Fixed dimension, Exploiting term sparsity in noncommutative polynomial optimization, COSMO: a conic operator splitting method for convex conic problems, TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity, Decomposition of arrow type positive semidefinite matrices with application to topology optimization, Memory-Efficient Structured Convex Optimization via Extreme Point Sampling, The positive definite completion problem revisited, The critical exponent: a novel graph invariant, A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices, Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion, Spectrahedral cones generated by rank \(1\) matrices, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Research problem: The completion number of a graph, Learning chordal extensions, Chordal decomposition in operator-splitting methods for sparse semidefinite programs, Limitations on the Expressive Power of Convex Cones without Long Chains of Faces, Extremal bipartite matrices, Preserving positivity for matrices with sparsity constraints, Decomposed structured subsets for semidefinite and sum-of-squares optimization, Exploiting sparsity in complex polynomial optimization, Extremal positive semidefinite doubly stochastic matrices

Cites Work

• Unnamed Item
• Completion of partial matrices to contractions
• Positive definite completions of partial Hermitian matrices
• Schur products and matrix completions
• Extensions of band matrices with band inverses
• Inverses of banded matrices
• Subalgebras of \(C^ *\)-algebras
• Triangulated graphs and the elimination process
• Inertia possibilities for completions of partial hermitian matrices^*
• Invertible Selfadjoint Extensions of Band Matrices and Their Entropy
• Norm-Preserving Dilations and Their Applications to Optimal Error Bounds
• On Spectral Permanence for Certain Banach Algebras
• Positive Functions on C ∗ -Algebras