A Direct Proof for the Matrix Decomposition of Chordal-Structured Positive Semidefinite Matrices
A Direct Proof for the Matrix Decomposition of Chordal-Structured Positive Semidefinite Matrices
复制标题
弦结构正半定矩阵矩阵分解的直接证明
DOI：
10.1016/j.laa.2010.04.012
复制
发表时间：
2010
影响因子：
1.1
通讯作者：
Naonori Kakimura
中科院分区：
文献类型：
--
作者：
Aki-Hiro SATO;Takaki HAYASHI;Naonori Kakimura
Agler, Helton, McCullough， and Rodman证明了一个图是弦性的，当且仅当任意正半定（PSD）对称矩阵，其非零项由给定图指定，可以分解为与极大团对应的PSD矩阵的和。这种分解最近被用来有效地求解正半定规划。他们的证明是基于Grone， Johnson, s<e:1>和Wolkowicz对弦结构矩阵的PSD矩阵补全的表征。本文给出了Agler等人的结果的一个直接和简单的证明，从而引出了Grone等人的另一个证明。
Agler, Helton, McCullough, and Rodman proved that a graph is chordal if and only if any positive semidefinite (PSD) symmetric matrix, whose nonzero entries are specified by a given graph, can be decomposed as a sum of PSD matrices corresponding to the maximal cliques. This decomposition is recently exploited to solve positive semidefinite programming efficiently. Their proof is based on a characterization for PSD matrix completion of a chordal-structured matrix due to Grone, Johnson, Sá, and Wolkowicz. This note gives a direct and simpler proof for the result of Agler et al., which leads to an alternative proof of Grone et al.