MPC

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

Certifiably optimal sparse principal component analysis

Lauren Berk, Dimitris Bertsimas

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




Imprint and privacy statement

For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2020 by Zuse Institute Berlin (ZIB).