Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering
Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering
复制标题
DOI：
10.1109/cdc40024.2019.9029620
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Jared Miller;Yang Zheng;Biel Roig-Solvas;M. Sznaier;A. Papachristodoulou
中科院分区：
文献类型：
--
作者：
Jared Miller;Yang Zheng;Biel Roig-Solvas;M. Sznaier;A. Papachristodoulou
半定规划（SDP）经常出现在一些NP困难问题的松弛中，如果SDP的解服从一定的秩约束，则松弛将是紧的。基于弦稀疏性的分解方法已经被应用于加速稀疏SDP的求解，但是处理秩约束的方法还不发达。本文利用最小秩完备化结果将单个大矩阵上的秩约束分解为一组较小矩阵上的多个秩约束。重新加权的启发式算法被用作排名的代理，并且启发式算法的特定形式保留了迭代之间的稀疏模式。讨论了秩最小化SDP的邻域点算法和一阶算法的实现。子空间聚类的问题被用来证明所提出的方法的计算改进。
Semidefinite programs (SDPs) often arise in relaxations of some NP-hard problems, and if the solution of the SDP obeys certain rank constraints, the relaxation will be tight. Decomposition methods based on chordal sparsity have already been applied to speed up the solution of sparse SDPs, but methods for dealing with rank constraints are underdeveloped. This paper leverages a minimum rank completion result to decompose the rank constraint on a single large matrix into multiple rank constraints on a set of smaller matrices. The re-weighted heuristic is used as a proxy for rank, and the specific form of the heuristic preserves the sparsity pattern between iterations. Implementations of rank-minimized SDPs through interior-point and first-order algorithms are discussed. The problem of subspace clustering is used to demonstrate the computational improvement of the proposed method.