Apr, 2013

稀疏主成分分析的计算下界

PDF
TL;DR在稀疏主成分检测的背景下，我们提供了计算效率的统计代价存在的证据。我们通过检测它能够检测到的最小信号强度来测量测试性能，并提出了一种基于半定规划的计算有效方法。同时，我们证明了这个测试的统计性能不能被任何计算有效的方法严格改进。我们的结果可以被视为基于某些种植团问题的某些实例不能在随机多项式时间内被解决这一假设的复杂性理论下界。
sparse principal component detectioncomputational efficiencysemidefinite programmingcomplexity theoryplanted clique problem
发现论文，激发创造
  • 高维稀疏主成分的最优检测

    通过有限样本分析，我们提出了一个新的基于稀疏特征值统计量的极小化最佳检验方法，使用凸松弛的方法实现了有效性，并证明其接近于最优的检测水平。通过计算机模拟实验，我们证明了该方法在检测高维协方差矩阵的稀疏主成分方面的有效性。

    Feb, 2012

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

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

    Jul, 2015

  • 稀疏主成分估计中的统计和计算折衷

    通过研究计算复杂性理论，发现在满足一定限制的协方差集中条件下存在有效的样本大小范围，在此范围内无法有随机多项式时间算法达到最佳极小风险率；对著名的半定松弛估计方法的理论性能进行研究，揭示了统计效率和计算效率之间微妙的相互作用，此方法为多维数据稀疏主成分分析提供了一种解决方案。

    Aug, 2014

  • 聚类、稀疏 PCA 和子矩阵定位中的信息论限制和相变

    研究了检测结构化低秩信号矩阵被加性高斯噪声污染的问题，包括在高斯混合模型中的聚类， 稀疏主成分分析和子矩阵定位。通过将第一和第二时刻方法应用于这些 “种植模型” 和零模型之间的似然比来导出阈值的上下界，我们证明了在信号矩阵过于微弱时没有任何算法可以检测其信号。

    Jul, 2016

  • 信息论上最优稀疏主成分分析

    本文讨论了两种概率稀疏主成分分析模型：钉住 Wigner 模型和钉住 Wishart 模型，并分析了一个用于估计基本信号的近似信息传递 (AMP) 算法。在高维极限下，AMP 估计是信息理论上的最优。此外，本文提供了稀疏 PCA 问题的单字母特征。

    Feb, 2014

  • 低秩逼近实现的稀疏主成分分析

    本文介绍了一种计算正半定矩阵的 k - 稀疏主成分的新算法，其通过查看低维度特征子空间中的一组离散特殊向量来实现。该算法的近似保证取决于其特征值分布，这使得其能够在多项式时间内对任意精度进行近似计算，同时几乎能够匹配或优于之前算法在所有测试数据集上的表现。

    Mar, 2013

  • 半定松弛是否可以解决稀疏主成分分析问题直至信息极限？

    研究稀疏主成分分析、半定规划等算法在单脉冲模型中的应用，证明了 SDP 算法在 k≥Ω（√n） 时不能恢复稀疏脉冲，并且推测在单脉冲模型中，没有高效算法可以恢复 Ω（√n）稀疏度的脉冲。最后，提出经验结论，表明通过简单的协方差阈值算法可以实现对低稀疏度（k = O (√n)）下的恢复。

    Jun, 2013

  • 稀疏主成分分析的最优解

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

    Jul, 2007

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

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

    Jun, 2020

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

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

    Mar, 2008