NIPSAug, 2018

具有 $\tilde {O}(\sqrt {n})$ 随机特征的流式核 PCA

PDF
TL;DR在核主成分分析中使用随机傅里叶特征的统计和计算学方面的研究，证明在温和假设下，使用 O (sqrt (n) log n) 个特征即可达到 O (1/epsilon^2) 的样本复杂度；此外，还提出了一种基于经典 Oja 算法的内存高效的流算法来实现这一速率.
发现论文，激发创造
  • 流式核主成分分析

    提出了一种基于矩阵草图的流式 Kernel 主成分分析方法，它能够在流中维护一小组基本元素，仅需要对 n 取对数的空间，比当前最先进的方法在实践中表现得更好。

    Dec, 2015

  • 使用随机特征的近似核主成分分析：计算与统计的权衡

    本文研究了随机特征逼近在核主成分分析中的应用，通过比较计算效率和统计效率，分析了逼近 KPCA 的计算和统计性能优于 KPCA，研究依赖于自伴随 Hilbert-Schmidt 算子值 U 统计量的算子和 Hilbert-Schmidt 范数的 Bernstein 型不等式。

    Jun, 2017

  • 随机特征学习的泛化性能

    本研究探讨了统计学习框架下随机特征稀疏化岭回归的泛化性质，结果显示仅需 O（根号 n*log n）个随机特征即可实现 O（1 / 根号 n）的学习界限，优于之前的提法；此外我们证明了一系列快速学习速率及其潜在影响，研究证明了及格自适应分配随机特征的可行性，这有助于降低计算复杂度，并保持最优泛化特性。

    Feb, 2016

  • 随机傅里叶特征的误差

    本文介绍了核方法在机器学习问题中的应用，提到了采用随机傅里叶特征解决大规模数据集问题的方法，并给出了更好的误差界限及嵌入方式的理解、近似误差、在某些机器学习方法中的使用，同时指出了该特征的两种变体中，更常用的一种在高斯核中具有严格更高的方差且具有更糟糕的界限的令人惊讶的事实。

    Jun, 2015

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

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

    Feb, 2016

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

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

    Jun, 2013

  • 核特征的高斯积分

    使用高斯积分逼近核函数的频域，可以构建确定性特征图来替代随机傅里叶特征映射，其采样量是以指数形式来考虑的，适用于稀疏 ANOVA 核函数，具有生成速度快和较高精度的特点。

    Sep, 2017

  • 用于马尔可夫数据的流式主成分分析

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

    May, 2023

  • 正交随机特征：显式形式和尖锐不等式

    通过正交随机特征来近似普遍的高斯核，本研究分析了基于正交随机特征的核逼近的偏差和方差，并通过使用归一化贝塞尔函数推导出了明确的表达式，并提供了支持正交随机特征比随机傅里叶特征更具信息性的尖锐指数界限。

    Oct, 2023

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

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

    Apr, 2015