Oct, 2018

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

PDF
TL;DR本文提出了一种使用凸整数规划框架来导出 Sparse PCA 的对偶界限的方法，包括在标准半定编程（SDP）松弛中获得对偶界限的双重界限，并将其进一步放松为凸整数编程。此方法表现出在高维数据集上表现的能力， 尤其是与 SDP 松弛相比，可以通过商业整数规划求解器更好地扩展。
发现论文，激发创造
  • 稀疏主成分分析的精确和近似算法

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

    Aug, 2020

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

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

    Nov, 2010

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

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

    Mar, 2008

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

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

    May, 2020

  • 利用半正定规划对稀疏 PCA 进行直接求解

    研究在 Frobenius-norm 意义下，将正半定对称矩阵近似为一个秩为一的矩阵，其特征向量的基数有一个上限的问题以及其在协方差矩阵分解到稀疏因子等领域中的应用，提出了一个基于半定规划的方法，并讲解了 Nesterov's 平滑最小化技术在直接稀疏 PCA 方法中的应用。

    Jun, 2004

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

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

    Jul, 2015

  • 具有多个分量的稀疏 PCA

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

    Sep, 2022

  • 全局支持稀疏主成分分析问题的解决

    本文通过提出凸松弛方法和随机稀疏化程序，改进现有算法，对于线性组合变量数目不超过 k、有限个主成分的求解进行了实验，结果表明算法具有正确性和高效性。

    Oct, 2020

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

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

    Aug, 2014

  • 稀疏主成分分析的近似算法

    本文介绍了一种名为门限法的难以置信的精简主方向载荷方法，并将其与半定规划松弛相结合，以改进主成分分析的解释性。

    Jun, 2020