  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 (sparse
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 SDP
relaxation for instances where the covariance matrices are of dimension up to
$50\times 50$.
