解决大规模稀疏 PCA 至可证明（近似）最优

May, 2020

解决大规模稀疏 PCA 至可证明（近似）最优

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

Dimitris Bertsimas, Ryan Cory-Wright, Jean Pauphilet

TL;DR通过将稀疏主成分分析重新制定为凸混合整数半定规划问题，并设计一个切平面方法，该方法可以以确切的最优性选择 5 个协变量从 300 个变量并能在更大范围内提供小的界限间隙。我们还提出了一种凸松弛和贪心舍入方案，可在几分钟内提供 1-2％的绑定间隙，使其成为规模上的可行替代方法。使用真实的金融和医疗数据集，我们展示了我们的方法在可解释性和易于计算的情况下，在不同范围内可行性的能力。

Abstract

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 th

sparse principal component analysis convex mixed-integer semidefinite optimization dimensionality reduction linear combinations interpretability

发现论文，激发创造

具有多个分量的稀疏 PCA

本研究提出一种新的方法，通过将正交性条件重新表述为秩约束，并同时优化稀疏性和秩约束，使得稀疏主成分分析问题更易解决。通过设计合理的半定松弛和可行的二阶锥不等式，本文的方法在实际数据集中可以获得最优解，并且相比现有方法具有更好的性能。

Sep, 2022

稀疏主成分分析的最优解

本论文提出了一种基于协方差矩阵的稀疏主成分分析方法，采用半正定松弛和贪心算法求解，可以适用于诸如子集选择和稀疏恢复等领域，并能在人工和生物数据等实验数据中提供全局最优解。

Jul, 2007

稀疏主成分的半定松弛高维分析

本文研究了高维 PCA 问题，通过添加 $k$-sparse 最大特征向量来扰动协方差矩阵，并分析了两种可计算的最大特征向量恢复方法：一种是简单的对角线阈值法，另一种是复杂的半定规划 (SDP) 松弛法，研究结果突出高维推断中计算与统计效率的权衡。

Mar, 2008

稀疏主成分分析：凸松弛，算法和应用

研究了稀疏主成分分析的解决方法，基于凸松弛技术和贪心算法，应用于机器学习、工程和金融等领域。

Nov, 2010

鲁棒主成分分析及其变体的高效优化算法

该论文回顾了现有的优化方法来解决鲁棒 PCA 及其变体。论文讨论了这些方法的优缺点和收敛性，并提出了一些面向多处理器环境下解决大规模问题的新算法框架的可能研究方向。

Jun, 2018

稀疏主成分分析的增广拉格朗日方法

本研究提出了一种新的稀疏 PCA 方法，旨在找到稀疏和几乎不相关的主成分，并具有正交的载荷向量，同时尽可能多地解释总方差。我们还开发了一种新的增广 Lagrangian 方法来解决一类非光滑约束优化问题，该方法非常适合我们的稀疏 PCA 公式。最后，我们将我们的稀疏 PCA 方法与其他方法在合成数据，随机数据和真实数据上进行比较。计算结果表明，我们的方法产生的稀疏主成分在总方差，主成分相关性和载荷向量的正交性等方面显着优于其他方法。

Jul, 2009

使用 L1 松弛和整数规划获得稀疏主成分分析的对偶界限

本文提出了一种使用凸整数规划框架来导出 Sparse PCA 的对偶界限的方法，包括在标准半定编程（SDP）松弛中获得对偶界限的双重界限，并将其进一步放松为凸整数编程。此方法表现出在高维数据集上表现的能力，尤其是与 SDP 松弛相比，可以通过商业整数规划求解器更好地扩展。

Oct, 2018

稀疏主成分分析的精确和近似算法

该论文提出了两种混合整数 SDP，用于优化选择主子矩阵的最大特征值，进一步分析和证明了它们的理论最优性差距优于现有技术，然后解决了在解决 MISDP 时存在的计算难题，同时提出了近似算法和 MILP 模型，有效地解决了规模问题，最后将其扩展到非对称矩阵和多个协方差矩阵的情况。

Aug, 2020

非凸统计优化：多项式时间下的极小极大稀疏 PCA

提出一个名为 'tighten after relax' 的两阶段计算框架，其中第一阶段使用建议的凸松弛方法进行近似求解，第二阶段则通过直接求解基础非凸问题的新算法'sparse orthogonal iteration pursuit' 来迭代优化初始估计值，并证明该框架的稳定性和最优性在特定模型类别下成立。

Aug, 2014

稀疏主成分分析的平方和下界

本文研究使用凸松弛法解决高维机器学习问题时，统计与计算的权衡。对稀疏主成分分析（Sparse PCA）问题和 Sum-of-Squares（即 Lasserre / Parillo）凸松弛法进行了探究。通过研究发现基于次数 - 4 的 SoS 算法不能改善计算次数为 k² 的情况，为这种强大的凸松弛算法族中的一部分问题建立了平均情况下的下限，说明它们存在困难问题。

Jul, 2015