Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis

Jinhak Kim (), Mohit Tawarmalani () and Jean-Philippe P. Richard ()
Additional contact information
Jinhak Kim: College of Business, Northern Illinois University, DeKalb, Illinois 60115
Mohit Tawarmalani: Krannert School of Management, Purdue University, West Lafayette, Indiana 47907
Jean-Philippe P. Richard: Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455

Mathematics of Operations Research, 2022, vol. 47, issue 4, 2547-2584

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.

Keywords: Primary: 47N10; secondary: 90C26; 52A27; convexification; permutation-invariant sets; majorization; sparse PCA (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1219 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:4:p:2547-2584

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().