---
res:
bibo_abstract:
- For a graph G with p vertices the closed convex cone S⪰0(G) consists of all real
positive semidefinite p×p matrices whose sparsity pattern is given by G, that
is, those matrices with zeros in the off-diagonal entries corresponding to nonedges
of G. The extremal rays of this cone and their associated ranks have applications
to matrix completion problems, maximum likelihood estimation in Gaussian graphical
models in statistics, and Gauss elimination for sparse matrices. While the maximum
rank of an extremal ray in S⪰0(G), known as the sparsity order of G, has been
characterized for different classes of graphs, we here study all possible extremal
ranks of S⪰0(G). We investigate when the geometry of the (±1)-cut polytope of
G yields a polyhedral characterization of the set of extremal ranks of S⪰0(G).
For a graph G without K5 minors, we show that appropriately chosen normal vectors
to the facets of the (±1)-cut polytope of G specify the off-diagonal entries of
extremal matrices in S⪰0(G). We also prove that for appropriately chosen scalars
the constant term of the linear equation of each facet-supporting hyperplane is
the rank of its corresponding extremal matrix in S⪰0(G). Furthermore, we show
that if G is series-parallel then this gives a complete characterization of all
possible extremal ranks of S⪰0(G). Consequently, the sparsity order problem for
series-parallel graphs can be solved in terms of polyhedral geometry.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Liam T
foaf_name: Solus, Liam T
foaf_surname: Solus
foaf_workInfoHomepage: http://www.librecat.org/personId=2AADA620-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Caroline
foaf_name: Uhler, Caroline
foaf_surname: Uhler
foaf_workInfoHomepage: http://www.librecat.org/personId=49ADD78E-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-7008-0216
- foaf_Person:
foaf_givenName: Ruriko
foaf_name: Yoshida, Ruriko
foaf_surname: Yoshida
bibo_doi: 10.1016/j.laa.2016.07.026
bibo_volume: 509
dct_date: 2016^xs_gYear
dct_language: eng
dct_publisher: Elsevier@
dct_title: Extremal positive semidefinite matrices whose sparsity pattern is given
by graphs without K5 minors@
...