具有 Oracle 属性的稀疏主成分分析
本文研究了高维 PCA 问题,通过添加 $k$-sparse 最大特征向量来扰动协方差矩阵,并分析了两种可计算的最大特征向量恢复方法:一种是简单的对角线阈值法,另一种是复杂的半定规划 (SDP) 松弛法,研究结果突出高维推断中计算与统计效率的权衡。
Mar, 2008
研究稀疏主成分分析、半定规划等算法在单脉冲模型中的应用,证明了 SDP 算法在 k≥Ω(√n) 时不能恢复稀疏脉冲,并且推测在单脉冲模型中,没有高效算法可以恢复 Ω(√n)稀疏度的脉冲。最后,提出经验结论,表明通过简单的协方差阈值算法可以实现对低稀疏度(k = O (√n))下的恢复。
Jun, 2013
本论文研究基于高维独立的高斯观测下,对总体协方差矩阵中的主要特征向量进行估计的问题。研究者们提出了一种基于坐标选择方案结合 PCA 的主要特征向量估计器,并证明了该估计器在稀疏条件下可以达到最优收敛速率。同时,也证明在某些情形下,通常的 PCA 可以达到最小最大收敛速率。
Feb, 2012
本文考虑了高维情况下主成分子空间的极小值估计和自适应估计,并利用聚合构建了速率最优估计器。同时介绍了一种通过降维来对稀疏主成分分析问题求解的方法。
Nov, 2012
本文研究使用凸松弛法解决高维机器学习问题时,统计与计算的权衡。对稀疏主成分分析(Sparse PCA)问题和 Sum-of-Squares(即 Lasserre / Parillo)凸松弛法进行了探究。通过研究发现基于次数 - 4 的 SoS 算法不能改善计算次数为 k² 的情况,为这种强大的凸松弛算法族中的一部分问题建立了平均情况下的下限,说明它们存在困难问题。
Jul, 2015
通过研究计算复杂性理论,发现在满足一定限制的协方差集中条件下存在有效的样本大小范围,在此范围内无法有随机多项式时间算法达到最佳极小风险率;对著名的半定松弛估计方法的理论性能进行研究,揭示了统计效率和计算效率之间微妙的相互作用,此方法为多维数据稀疏主成分分析提供了一种解决方案。
Aug, 2014
本文介绍了一种计算正半定矩阵的 k - 稀疏主成分的新算法,其通过查看低维度特征子空间中的一组离散特殊向量来实现。该算法的近似保证取决于其特征值分布,这使得其能够在多项式时间内对任意精度进行近似计算,同时几乎能够匹配或优于之前算法在所有测试数据集上的表现。
Mar, 2013
研究在 Frobenius-norm 意义下,将正半定对称矩阵近似为一个秩为一的矩阵,其特征向量的基数有一个上限的问题以及其在协方差矩阵分解到稀疏因子等领域中的应用,提出了一个基于半定规划的方法,并讲解了 Nesterov's 平滑最小化技术在直接稀疏 PCA 方法中的应用。
Jun, 2004
研究了鲁棒子空间恢复的基本问题,通过解决凸最小化过程来估计 “鲁棒逆样本协方差”,然后通过此矩阵的底部特征向量(其数量对应于接近 0 的特征值的数量)恢复子空间。我们保证在某些条件下精确恢复子空间,同时提出了一种快速迭代算法,可线性收敛到最小化凸问题的矩阵。我们对噪声和正则化的影响进行了量化,并在各种设置中讨论了许多实际和理论问题,以改善子空间恢复。与许多其他鲁棒 PCA 算法相比,在合成和实际数据集上进行了比较,并证明具有最先进的速度和准确度。
Dec, 2011