Feb, 2016

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

PDF
TL;DR该研究提出了一个对流式主成分分析（PCA）有改进保证的线性时间算法，该算法可以在常数精度下估计协方差矩阵的前几个特征向量。该算法通过一种新颖的 Oja 算法分析方法实现。
streaming pcalinear-time algorithmeigenvectorsmatrix bernstein inequalityoja's algorithm
发现论文，激发创造
  • 用于马尔可夫数据的流式主成分分析

    研究了数据点从无法分解的 Markov 链中采样的流式主成分分析（PCA）问题，提出了一个新的算法并证明了其收敛速率，解决了使用 MCMC 算法从链的稳态分布中采样的问题。

    May, 2023

  • 流式 k-PCA 的第一个高效收敛：全局无间隙，近乎最优速率

    本研究研究了流式主成分分析，并提出了 Oja 算法的全局收敛，同时提供了一个修改后的变体 Oja++，可以比 Oja 更快地运行。

    Jul, 2016

  • Oja 阈值处理是否实现稀疏 PCA？

    稀疏主成分分析 (Sparse Principal Component Analysis, PCA) 的问题，当比率 $d/n ightarrow c > 0$ 时进行研究。针对在线优化问题，我们提出一种简单的算法，通过阈值和重新归一化 Oja 算法的输出 (即 Oja 向量)，获得接近最优的误差率。这是非常令人惊讶的，因为没有阈值时，Oja 向量存在很大的误差。我们的分析主要围绕未归一化 Oja 向量的元素进行界定，其中涉及到独立随机矩阵乘积在随机初始向量上的投影，这是非常复杂且新颖的，因为对 Oja 算法和矩阵乘积的先前分析是在限制了总体协方差矩阵的迹的情况下进行的，而在我们的情境中，这个量可以达到 $n$ 的大小。

    Feb, 2024

  • 增量型 PCA 的快速收敛

    本研究针对在已知分布均值为零和未知协方差的情况下，使用增量算法以 O (d) 空间复杂度计算顶部特征向量，对 Krasulina 和 Oja 的两种传统方案进行了有限样本收敛率分析。

    Jan, 2015

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

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

    Apr, 2015

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

    本研究主要研究经典问题 PCA 中的异常值问题，提出了近线性时间的近似最优解鲁棒 PCA 算法以及单遍流式鲁棒 PCA 算法，并进行了相关的理论分析。

    May, 2023

  • 用于高速流式主成分分析的分布式随机算法

    本文探讨了在流式数据下，从独立同分布的数据采样中估算协方差矩阵的主特征向量的问题，并提出和分析了一种分布式变体方案 D-Krasulina，该方案可以在多个处理节点上分布计算负载以跟上高数据流率。通过对该方案的分析表明，在适当的条件下，D-Krasulina 以次序优化的方式收敛于主特征向量，即在接收到所有节点的 M 个采样后，其估算误差可以是 O (1/M)。最后，通过对合成和真实世界数据的实验验证了 D-Krasulina 和 DM-Krasulina 在高速数据流场景中的收敛行为。

    Jan, 2020

  • 随机梯度下降法在 PCA 中的收敛性

    本文针对主成分分析问题在流式随机场景中进行探讨和研究，给出了针对性的随机梯度下降算法，提供了最新的无需基于非平凡特征值间隙假设的收敛保证，并改进了在该假设下的优化算法保证效果。

    Sep, 2015

  • 主成分分析的有限样本逼近结果：矩阵扰动方法

    研究如何使用矩阵摄动方法，研究 PCA 在有限样本下的特征值与特征向量与极限样本 PCA 之间的关系，证明了在有 “spiked covariance model” 时，样本 PCA 和极限样本 PCA 之间的接近性，进而将研究重点转移到有限维的 PCA 中并解释了转换点现象和特征向量丢失追踪的现象。

    Jan, 2009

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

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

    Mar, 2016