sparse principal component analysis

Cutting Plane Generation Through Sparse Principal Component Analysis

  • Santanu S. Dey
  • Aleksandr M. Kazachkov
  • Andrea Lodi
  • Gonzalo Muñoz
    • Categories Cutting Plane Approaches, Quadratic Programming Tags , , ,

    Quadratically-constrained quadratic programs (QCQPs) are optimization models whose remarkable expressiveness has made them a cornerstone of methodological research for nonconvex optimization problems. However, modern methods to solve a general QCQP fail to scale, encountering computational challenges even with just a few hundred variables. Specifically, a semidefinite programming (SDP) relaxation is typically employed, which provides strong … Read more

    Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming, Statistics Tags , , ,

    Sparse principal component analysis (PCA) is a popular dimensionality reduction technique for obtaining principal components which are linear combinations of a small subset of the original features. Existing approaches cannot supply certifiably optimal principal components with more than $p=100s$ of variables. By reformulating sparse PCA as a convex mixed-integer semidefinite optimization problem, we design a … Read more

    On the Quality of a Semidefinite Programming Bound for Sparse Principal Component Analysis

  • Laurent El Ghaoui
    • Categories Robust Optimization, Semi-definite Programming, Statistics Tags , , ,

    We examine the problem of approximating a positive, semidefinite matrix $\Sigma$ by a dyad $xx^T$, with a penalty on the cardinality of the vector $x$. This problem arises in sparse principal component analysis, where a decomposition of $\Sigma$ involving sparse factors is sought. We express this hard, combinatorial problem as a maximum eigenvalue problem, in … Read more