Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization
研究如何从稀疏线性矩阵不等式中找到低秩解，将稀疏性映射为图，提出三种基于图论的凸规划方法，可应用于矩阵补全、多项式优化和仿射秩最小化问题。
This paper is concerned with the problem of finding a low-rank solution of an arbitrary sparse linear matrix inequality (LMI). To this end, we map the sparsity of the LMI problem into a graph. We develop a mathematical framework to relate the rank of the minimum-rank solution of the LMI problem to the sparsity of its underlying graph. Furthermore, we propose three graph-theoretic convex programs to obtain a low-rank solution. Two of these convex optimization problems are based on a tree decomposition of the sparsity graph. The third one does not rely on any computationally expensive graph analysis and is always polynomial-time solvable, at the cost of offering a milder theoretical guarantee on the rank of the obtained solution compared to the other two methods. The results of this work can be readily applied to three separate problems of minimum-rank matrix completion, conic relaxation for polynomial optimization, and affine rank minimization. The results are finally illustrated on two applications of optimal distributed control and nonlinear optimization for electrical networks.