Bibliographic Details
| Title: |
Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis. |
| Authors: |
Kim, Jinhak1 (AUTHOR) jkim23@niu.edu, Tawarmalani, Mohit2 (AUTHOR) mtawarma@purdue.edu, Richard, Jean-Philippe P.3 (AUTHOR) jrichar@umn.edu |
| Source: |
Mathematics of Operations Research. Nov2022, Vol. 47 Issue 4, p2547-2584. 38p. |
| Subject Terms: |
Principal components analysis, Covariance matrices, Semidefinite programming, Unit ball (Mathematics), Convex sets |
| Abstract: |
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. [ABSTRACT FROM AUTHOR] |
|
Copyright of Mathematics of Operations Research is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Business Source Complete |
