异常点下主成分分析的复杂度优化
该文介绍了一种名为 Outlier Pursuit 的基于凸优化的算法,该算法使用矩阵分解来恢复未损坏矩阵的正确列空间,并确定损坏的点。此算法在基因组学和金融应用中具有重要意义。
Oct, 2010
本文介绍一种新的基于多个不相交支撑的稀疏主成分分析算法,能够在多项式时间复杂度内,统一优化多个不相交的主成分,并且在真实数据集上的实验结果表明,在许多情况下,该算法能够胜过现有的基于排除法的方法。
Aug, 2015
本文介绍了一种非凸优化方法,用于解决全观测和部分观测情况下的鲁棒主成分分析问题,该方法与现有最佳算法相比,显著降低了计算复杂度,并且在部分观测情况下,我们的算法在有可证明的情况下也是已知的运行时间最短的算法。
May, 2016
本文提出了一种名为Coherence Pursuit的算法,用于从数据中检测和去除异常值,并得到主成分的低维子空间,该算法能快速计算并在不同模型的数据集中得到优异表现的同时,具有非迭代、可证明牢靠性和容忍大量非结构化异常值等特点。
Sep, 2016
本文提出了基于阈值的迭代算法,用于处理含有离群点的数据集中的偏差鲁棒主成分分析问题,该方法的迭代复杂度最多线性,可以处理至多α分数的离群点,并且对于一般噪声设置具有近乎最佳的计算复杂度。对于特殊情况,即噪声是加性高斯噪声,本文改进了该方法,并成功地减小了恢复误差。
Feb, 2017
本研究概述了鲁棒子空间学习和跟踪领域。通过罕见因素加上低秩矩阵分解(S+LR),在存在异常值的情况下解决了罕见子空间学习或PCA问题,并发现针对长数据序列的跟踪鲁棒子空间的更好的模型是假设数据位于低维子空间中,而该模型的异常值被作为稀疏病态安装建模。
Nov, 2017
通过将稀疏主成分分析重新制定为凸混合整数半定规划问题,并设计一个切平面方法,该方法可以以确切的最优性选择5个协变量从300个变量并能在更大范围内提供小的界限间隙。我们还提出了一种凸松弛和贪心舍入方案,可在几分钟内提供1-2%的绑定间隙,使其成为规模上的可行替代方法。使用真实的金融和医疗数据集,我们展示了我们的方法在可解释性和易于计算的情况下,在不同范围内可行性的能力。
May, 2020
本研究解决了在存在异常值的情况下,主成分分析(PCA)面临的最优子空间计算问题,填补了这一领域的方法空白。我们提出的新算法通过高阶沃罗诺伊图提供了有效的解决方案,具有良好的时间复杂度,并确保捕捉到最优子空间的高成功概率。该方法具有显著的实用价值,尤其在大数据集和高维环境中表现出色。
Aug, 2024
本研究解决了在存在异常值情况下的主成分分析(PCA)中最优子空间选择的问题。通过引入高阶Voronoi图和Grassmann流形采样的新算法,研究展示了一种更有效的寻找最优解的方法,显著提高了大数据集和高维设置下的分析准确性。最重要的发现是,新的算法实现了在复杂性和成功概率方面的显著优化。
Aug, 2024