  Sparse Principal Component Analysis (sPCA) is a cardinal technique for
obtaining combinations of features, or principal components (PCs), that explain
the variance of high-dimensional datasets in an interpretable manner. This
involves solving a sparsity and orthogonality constrained convex maximization
problem, which is extremely computationally challenging. Most existing works
address sparse PCA via methods-such as iteratively computing one sparse PC and
deflating the covariance matrix-that do not guarantee the orthogonality, let
alone the optimality, of the resulting solution when we seek multiple mutually
orthogonal PCs. We challenge this status by reformulating the orthogonality
conditions as rank constraints and optimizing over the sparsity and rank
constraints simultaneously. We design tight semidefinite relaxations to supply
high-quality upper bounds, which we strengthen via additional second-order cone
inequalities when each PC's individual sparsity is specified. Further, we
derive a combinatorial upper bound on the maximum amount of variance explained
as a function of the support. We exploit these relaxations and bounds to
propose exact methods and rounding mechanisms that, together, obtain solutions
with a bound gap on the order of 0%-15% for real-world datasets with p = 100s
or 1000s of features and r \in {2, 3} components. Numerically, our algorithms
match (and sometimes surpass) the best performing methods in terms of fraction
of variance explained and systematically return PCs that are sparse and
orthogonal. In contrast, we find that existing methods like deflation return
solutions that violate the orthogonality constraints, even when the data is
generated according to sparse orthogonal PCs. Altogether, our approach solves
sparse PCA problems with multiple components to certifiable (near) optimality
in a practically tractable fashion.
