Mathematical Programming Computation, Volume 11, Issue 3, September 2019

Font Size:  Small  Medium  Large

Certifiably optimal sparse principal component analysis

Lauren Berk, Dimitris Bertsimas

Abstract


This paper addresses the sparse principal component analysis (SPCA) problem for covariance matrices in dimension n aiming to find solutions with sparsity k usingmixed integer optimization. We propose a tailored branch-and-bound algorithm, Optimal-SPCA, that enables us to solve SPCA to certifiable optimality in seconds for n = 100 s, k = 10 s. This same algorithm can be applied to problems with n = 10,000 s or higher to find high-quality feasible solutions in seconds while taking several hours to prove optimality. We apply our methods to a number of real data sets to demonstrate that our approach scales to the same problem sizes attempted by other methods, while providing superior solutions compared to those methods, explaining a higher portion of variance and permitting complete control over the desired sparsity. The software that was reviewed as part of this submission has been given the DOI (digital object identifier) https://doi.org/10.5281/zenodo.2027898

Full Text: PDF

mpc footer
© MPS 2008-2019