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

References

• Allen GI, Maletić-Savatić M (2011) Sparse non-negative generalized PCA with applications to metabolomics. Bioinformatics 27(21):3029–3035.Crossref, Google Scholar
• Bagroy S, Kumaraguru P, De Choudhury M (2017) A social media based index of mental well-being in college campuses. Mark G, Fussell SR, Lampe C, Schraefel MC, Hourcade JP, Appert C, Wigdor D, eds. Proc. 2017 CHI Conf. Human Factors Comput. Systems (ACM, Denver, CO, USA), 1634–1646.Google Scholar
• Berk L, Bertsimas D (2019) Certifiably optimal sparse principal component analysis. Math. Program. Comput. 11(3):381–420.Google Scholar
• Berthet Q, Rigollet P (2013) Optimal detection of sparse principal components in high dimension. Ann. Statist. 41(4):1780–1815.Crossref, Google Scholar
• Bienstock D (1996) Computational study of a family of mixed-integer quadratic programming problems. Math. Programming 74(2):121–140.Crossref, Google Scholar
• Bomze IM, Eichfelder G (2013) Copositivity detection by difference-of-convex decomposition and ω-subdivision. Math. Programming 138(1–2):365–400.Crossref, Google Scholar
• Bonami P, Günlük O, Linderoth J (2018) Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods. Math. Program. Comput. 10(3):333–382.Google Scholar
• Burer S, Saxena A (2009) Old wine in a new bottle: The MILP road to MIQCP. Optimization online.Google Scholar
• Burer S, Vandenbussche D (2009) Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound. Comput. Optim. Appl. 43(2):181–195.Crossref, Google Scholar
• Cadima J, Jolliffe IT (1995) Loading and correlations in the interpretation of principle compenents. J. Appl. Statist. 22(2):203–214.Crossref, Google Scholar
• Chan SO, Papailiopoulos D, Rubinstein A (2015) On the worst-case approximability of sparse PCA. Preprint, submitted July 21, https://arxiv.org/abs/1507.05950.Google Scholar
• d’Aspremont A, Bach FR, El Ghaoui L (2007) Full regularization path for sparse principal component analysis. Ghahramani Z, ed. Proc. 24th Internat. Conf. Machine Learn. (ACM, Corvallis, Oregon, USA), 177–184.Google Scholar
• d’Aspremont A, Bach F, El Ghaoui L (2008) Optimal solutions for sparse principal component analysis. J. Machine Learn. Res. 9:1269–1294.Google Scholar
• d’Aspremont A, Bach F, El Ghaoui L (2014) Approximation bounds for sparse principal component analysis. Math. Programming 148(1–2):89–110.Crossref, Google Scholar
• d’Aspremont A, El Ghaoui L, Jordan MI, Lanckriet GR (2005) A direct formulation for sparse PCA using semidefinite programming. Adv. Neural Inform. Processing Systems (Vancouver, British Columbia, Canada), 41–48.Google Scholar
• d’Aspremont A, El Ghaoui L, Jordan MI, Lanckriet GRG (2007) A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 49(3):434–448.Crossref, Google Scholar
• De Santis M, Rendl F, Wiegele A (2018) Using a factored dual in augmented Lagrangian methods for semidefinite programming. Oper. Res. Lett. 46(5):523–528.Crossref, Google Scholar
• Frangioni A, Gentile C (2007) SDP diagonalizations and perspective cuts for a class of nonseparable MIQP. Oper. Res. Lett. 35(2):181–185.Crossref, Google Scholar
• Hastie T, Tibshirani R, Wainwright M (2015) Statistical Learning with Sparsity (CRC Press).Crossref, Google Scholar
• He Y, Monteiro RDC, Park H (2011) An algorithm for sparse PCA based on a new sparsity control criterion. Proc. 2011 SIAM Internat. Conf. Data Mining (SIAM), 771–782.Google Scholar
• Jolliffe IT, Trendafilov NT, Uddin M (2003) A modified principal component technique based on the LASSO. J. Comput. Graphical Statist. 12(3):531–547.Crossref, Google Scholar
• Journée M, Nesterov Y, Richtárik P, Sepulchre R (2010) Generalized power method for sparse principal component analysis. J. Machine Learn. Res. 11:517–553.Google Scholar
• Kim J (2016) Cardinality constrained optimization problems. Unpublished PhD thesis, Purdue University, West Lafayette, Indiana.Google Scholar
• Ma S (2013) Alternating direction method of multipliers for sparse principal component analysis. J. Oper. Res. Soc. China 1(2):253–274.Crossref, Google Scholar
• Magdon-Ismail M (2017) NP-hardness and inapproximability of sparse PCA. Inform. Processing Lett. 126:35–38.Crossref, Google Scholar
• Mazumder R, Radchenko P (2017) The discrete Dantzig selector: Estimating sparse linear models via mixed integer linear optimization. IEEE Trans. Inform. Theory 63(5):3053–3075.Google Scholar
• Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization, Wiley interscience Series in Discrete Mathematics and Optimization, Wiley, New York.Crossref, Google Scholar
• Papailiopoulos D, Dimakis A, Korokythakis S (2013) Sparse PCA through low-rank approximations. Internat. Conf. Machine Learn. (Atlanta, GA, USA), 747–755.Google Scholar
• Saha K, De Choudhury M (2017) Modeling stress with social media around incidents of gun violence on college campuses. Proc. ACM Human-Comput. Interaction, (CSCW), 1–27.Google Scholar
• Vershynin R (2016) High-Dimensional Probability: An Introduction with Applications in Data Science (Draft).Google Scholar
• Wang T, Berthet Q, Samworth RJ (2016) Statistical and computational trade-offs in estimation of sparse principal components. Ann. Statist. 44(5):1896–1930.Crossref, Google Scholar
• Witten DM, Tibshirani R, Hastie T (2009) A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis. Biostatistics 10(3):515–534.Crossref, Google Scholar
• Yuan X-T, Zhang T (2011) Truncated power method for sparse eigenvalue problems. Preprint, submitted December 12, https://arxiv.org/abs/1112.2679.Google Scholar
• Yuan X-T, Zhang T (2013) Truncated power method for sparse eigenvalue problems. J. Machine Learn. Res. 14:899–925.Google Scholar
• Zhang Y, d’Aspremont A, El Ghaoui L (2012) Sparse PCA: Convex relaxations, algorithms and applications. Anjos MF, Lasserre JB, eds. Handbook on Semidefinite, Conic and Polynomial Optimization (Springer US, Boston, MA), 915–940.Crossref, Google Scholar
• Zhang Z, Zha H, Simon H (2002) Low-rank approximations with sparse factors I: Basic algorithms and error analysis. SIAM J. Matrix Anal. Appl. 23(3):706–727.Crossref, Google Scholar
• Zou H, Hastie T, Tibshirani R (2006) Sparse principal component analysis. J. Comput. Graphical Statist. 15(2):265–286.Crossref, Google Scholar