ICMLMay, 2023

异常值鲁棒主成分分析的近线性时间和流式算法

PDF
TL;DR本研究主要研究经典问题 PCA 中的异常值问题，提出了近线性时间的近似最优解鲁棒 PCA 算法以及单遍流式鲁棒 PCA 算法，并进行了相关的理论分析。
principal component analysisrobust pcaoutlierslinear time algorithmstreaming algorithm
发现论文，激发创造
  • 异常点下主成分分析的复杂度优化

    本文介绍了一种基于主成分分析的算法，可以在多个应用领域中发现和拟合给定数据点的主要性质，同时克服了数据中存在的异常值和离群点的影响。所提出的算法能够在多项式时间内求解，且精度可以保证。

    May, 2019

  • 基于阈值的高效异常值鲁棒主成分分析

    本文提出了基于阈值的迭代算法，用于处理含有离群点的数据集中的偏差鲁棒主成分分析问题，该方法的迭代复杂度最多线性，可以处理至多 α 分数的离群点，并且对于一般噪声设置具有近乎最佳的计算复杂度。对于特殊情况，即噪声是加性高斯噪声，本文改进了该方法，并成功地减小了恢复误差。

    Feb, 2017

  • 在线主成分估计的近最优随机逼近

    本文将在线 PCA 转化为随机非凸优化问题，并将在线 PCA 算法分析为随机逼近迭代。在亚高斯假设下，我们证明了在线 PCA 算法的近乎最优有限样本误差界限，并且表明有限样本误差界限与极小信息下界紧密匹配。

    Mar, 2016

  • 分布式和流式模型中的最优主成分分析

    该论文提供了改进的分布式 PCA 和流式 PCA 算法，旨在找到矩阵的最佳秩 - k 逼近。

    Apr, 2015

  • 流式 PCA：匹配矩阵伯恩斯坦和 Oja 算法的几乎最优有限样本保证

    该研究提出了一个对流式主成分分析（PCA）有改进保证的线性时间算法，该算法可以在常数精度下估计协方差矩阵的前几个特征向量。该算法通过一种新颖的 Oja 算法分析方法实现。

    Feb, 2016

  • 改进的分布式主成分分析

    本文研究具有多台服务器的分布式计算环境，通过开发 PCA 算法来处理点集的低维子空间问题，进而解决异常检测以及聚类等计算问题，提出的新算法显著降低了 $k$-means 聚类与相关问题的计算以及通讯成本，并且经过实验验证，在解决方案质量方面具有忽略不计的退化。

    Aug, 2014

  • 通过离群值追踪实现鲁棒的 PCA

    该文介绍了一种名为 Outlier Pursuit 的基于凸优化的算法，该算法使用矩阵分解来恢复未损坏矩阵的正确列空间，并确定损坏的点。此算法在基因组学和金融应用中具有重要意义。

    Oct, 2010

  • 基于流式数据的内存受限 PCA

    本研究提出了一种基于流处理的、使用有限内存的主成分分析算法，它可以在高维情况下有效地运行，并且在样本复杂度上比相关算法更好。

    Jun, 2013

  • 图上快速鲁棒主成分分析

    本文提出了一种基于主成分分析（PCA）的解决方案，通过设计凸优化问题来实现对高维数据集的低秩恢复，重点解决了高计算复杂性、非凸性和数据中的大量异常问题，同时经过了 7 组基准数据集的聚类实验和 3 组视频数据集的背景分离实验的测试，结果表明我们提出的模型优于 10 种最先进的降维模型。

    Jul, 2015

  • 大规模高维数据的单次 PCA

    本文提出了一种基于单次随机算法的主成分分析法，适用于处理极大和高维度的数据，并且具有小的计算误差和低的存储成本。

    Apr, 2017