Using l1-Relaxation and Integer Programming to Obtain Dual Bounds for Sparse PCA
提出一个凸整数规划框架来为稀疏PCA推导对偶界，证明其最坏情况下的质量，并实验表明该方法优于现有稀疏PCA方法。
Dual Bounds of Sparse Principal Component Analysis Sparse principal component analysis (PCA) is a widely used dimensionality reduction tool in machine learning and statistics. Compared with PCA, sparse PCA enhances the interpretability by incorporating a sparsity constraint. However, unlike PCA, conventional heuristics for sparse PCA cannot guarantee the qualities of obtained primal feasible solutions via associated dual bounds in a tractable fashion without underlying statistical assumptions. In “Using L1-Relaxation and Integer Programming to Obtain Dual Bounds for Sparse PCA,” Santanu S. Dey, Rahul Mazumder, and Guanyi Wang present a convex integer programming (IP) framework of sparse PCA to derive dual bounds. They show the worst-case results on the quality of the dual bounds provided by the convex IP. Moreover, the authors empirically illustrate that the proposed convex IP framework outperforms existing sparse PCA methods of finding dual bounds.