Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis
Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis
复制标题
DOI：
10.1287/moor.2021.1219
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Jinhak Kim;Mohit Tawarmalani;Jean-Philippe P. Richard
中科院分区：
文献类型：
--
作者：
Jinhak Kim;Mohit Tawarmalani;Jean-Philippe P. Richard
我们发展了在变量置换和/或变号条件下不变集合的凸化技术，并讨论了这些结果的应用。首先，我们用一个基数约束凸化了置换和符号不变范数的单位球的交点。本文给出了稀疏主成分分析可行集的一个非线性公式和k -支持范数的一个替代证明。其次，我们通过约束矩阵集合的奇异值来刻画矩阵集合的凸包。因此，我们推广了先前的一个结果，该结果表征了谱范数低于给定阈值的秩约束矩阵的凸包。第三，我们在超立方体上推导了各种置换不变非线性函数及其水平集的凸、凹包络，在所有变量上都有同界。最后，我们发展了稀疏向量外积的新松弛。将这些松弛用于稀疏PCA，我们表明，对于协方差矩阵的维数高达50 × 50的实例，我们的松弛关闭了经典半确定规划松弛所留下的空白的98%。
We develop techniques to convexify a set that is invariant under permutation and/or change of sign of variables and discuss applications of these results. First, we convexify the intersection of the unit ball of a permutation and sign-invariant norm with a cardinality constraint. This gives a nonlinear formulation for the feasible set of sparse principal component analysis (PCA) and an alternative proof of the K-support norm. Second, we characterize the convex hull of sets of matrices defined by constraining their singular values. As a consequence, we generalize an earlier result that characterizes the convex hull of rank-constrained matrices whose spectral norm is below a given threshold. Third, we derive convex and concave envelopes of various permutation-invariant nonlinear functions and their level sets over hypercubes, with congruent bounds on all variables. Finally, we develop new relaxations for the exterior product of sparse vectors. Using these relaxations for sparse PCA, we show that our relaxation closes 98% of the gap left by a classical semidefinite programming relaxation for instances where the covariance matrices are of dimension up to 50 × 50.