Using ${\ell }_1$-Relaxation and Integer Programming to Obtain Dual Bounds for Sparse PCA

Principal component analysis (PCA) is one of the most widely used dimensionality reduction tools in scientific data analysis. The PCA direction, given by the leading eigenvector of a covariance matrix, is a linear combination of all features with nonzero loadings; this impedes interpretability. Sparse principal component analysis (SPCA) is a framework that enhances interpretability by incorporating an additional sparsity requirement in the feature weights (factor loadings) while finding a direction that explains the maximal variation in the data. However, unlike PCA, the optimization problem associated with the SPCA problem is NP-hard. Most conventional methods for solving SPCA are heuristics with no guarantees, such as certificates of optimality on the solution quality via associated dual bounds. Dual bounds are available via standard semidefinite programming (SDP)–based relaxations, which may not be tight, and the SDPs are difficult to scale using off-the-shelf solvers. In this paper, we present a convex integer programming (IP) framework to derive dual bounds. At the heart of our approach is the so-called ${\ell }_1$-relaxation of SPCA. Although the ${\ell }_1$-relaxation leads to convex optimization problems for ${\ell }_0$-sparse linear regressions and relatives, it results in a nonconvex optimization problem for the PCA problem. We first show that the ${\ell }_1$-relaxation gives a tight multiplicative bound on SPCA. Then, we show how to use standard integer programming techniques to further relax the ${\ell }_1$-relaxation into a convex IP for which there are good commercial solvers. We present worst-case results on the quality of the dual bound provided by the convex IP. We empirically observe that the dual bounds are significantly better than the worst-case performance and are superior to the SDP bounds on some real-life instances. Moreover, solving the convex IP model using commercial IP solvers appears to scale much better that solving the SDP-relaxation using commercial solvers. To the best of our knowledge, we obtain the best dual bounds for real and artificial instances for SPCA problems involving covariance matrices of size up to 2,000 × 2,000.