论文标题
$ k $的双曲线放松 - 局部积极的半缩矩阵
Hyperbolic Relaxation of $k$-Locally Positive Semidefinite Matrices
论文作者
论文摘要
一种成功解决大规模阳性半限定（PSD）程序的计算方法是仅在一系列子膜片上执行PSD-。在我们的研究中，我们让$ \ MATHCAL {s}^{n，k} $为$ n \ times n $对称矩阵的凸锥，其中所有$ k \ times k $ princional sumpartrices均为psd。我们在此$ K $ - \ emph {locally PSD}中调用矩阵。为了将$ s^{n，k} $与PSD矩阵进行比较，我们研究了$ k $ - {locally PSD}矩阵的特征值。本文中的关键见解是有一个凸锥$ h（e_k^n）$，因此，如果$ x \ in \ nathcal {s}^{n，k} $，则$ x $的eigenvalues的向量包含在$ h（e_k^n）$中。锥$ h（e_k^n）$是基本对称的多项式$ e^k_n $（其中$ e_k^n（x）= \ sum_ {s \ subseteq [n]：| s | s | = k} \ k} \ prod_ {i prod_ {I in s} x_i $）与所有一个Vector。使用此见解，我们能够在$ \ Mathcal {s}^{n，k} $和PSD矩阵中的矩阵之间的Frobenius距离上提高以前已知的上限。我们还研究了凸放松的质量$ h（e^n_k）$。我们首先表明，对于$ k = n -1 $的情况，对于$ h（e^n_ {n -1}）$中的每个向量而言，这种放松是紧密的，存在$ \ mathcal {s}^{n，n -1} $中的矩阵中的矩阵，其eigenvalues等于vector的组成部分。然后，我们证明了$ \ Mathcal {s}^{n，k} $ y Mathcal {s}^{n，k} $所有其$ k \ times k $主要的未成年人零的结构定理，我们认为这是独立的。然后，我们证明了一个结构定理，该定理精确地表征了$ \ MATHCAL {s}^{n，k} $中的非单个矩阵，其特征值向量属于$ h（e^n_k）$的边界。该结果表明，对于$ 1 <k <n -1 $ $ h（e_k^n）$的边界的“大零件”不会与矩阵的特征值相交。
A successful computational approach for solving large-scale positive semidefinite (PSD) programs is to enforce PSD-ness on only a collection of submatrices. For our study, we let $\mathcal{S}^{n,k}$ be the convex cone of $n\times n$ symmetric matrices where all $k\times k$ principal submatrices are PSD. We call a matrix in this $k$-\emph{locally PSD}. In order to compare $S^{n,k}$ to the of PSD matrices, we study eigenvalues of $k$-{locally PSD} matrices. The key insight in this paper is that there is a convex cone $H(e_k^n)$ so that if $X \in \mathcal{S}^{n,k}$, then the vector of eigenvalues of $X$ is contained in $H(e_k^n)$. The cone $H(e_k^n)$ is the hyperbolicity cone of the elementary symmetric polynomial $e^k_n$ (where $e_k^n(x) = \sum_{S \subseteq [n] : |S| = k} \prod_{i \in S} x_i$) with respect to the all ones vector. Using this insight, we are able to improve previously known upper bounds on the Frobenius distance between matrices in $\mathcal{S}^{n,k}$ and PSD matrices. We also study the quality of the convex relaxation $H(e^n_k)$. We first show that this relaxation is tight for the case of $k = n -1$, that is, for every vector in $H(e^n_{n -1})$ there exists a matrix in $\mathcal{S}^{n, n -1}$ whose eigenvalues are equal to the components of the vector. We then prove a structure theorem on nonsingular matrices in $\mathcal{S}^{n,k}$ all of whose $k\times k$ principal minors are zero, which we believe is of independent interest. %We then prove a structure theorem that precisely characterizes the non-singular matrices in $\mathcal{S}^{n,k}$ whose vector of eigenvalues belongs to the boundary of $H(e^n_k)$. This result shows shows that for $1< k < n -1$ "large parts" of the boundary of $H(e_k^n)$ do not intersect with the eigenvalues of matrices in $\mathcal{S}^{n,k}$.
