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

Feb, 2024

Thresholded Oja does Sparse PCA?

Syamantak Kumar, Purnamrita Sarkar

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

Abstract

We consider the problem of sparse principal component analysis (PCA) when the ratio $d/n \rightarrow c > 0$. There has been a lot of work on optimal rates on sparse pca in the offline setting, where all the data

sparse principal component analysis sparse pca streaming algorithms thresholding oja's algorithm

发现论文，激发创造

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

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

Feb, 2016

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

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

Jul, 2016

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

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

May, 2023

高维数据的增强稀疏主成分分析

本论文研究基于高维独立的高斯观测下，对总体协方差矩阵中的主要特征向量进行估计的问题。研究者们提出了一种基于坐标选择方案结合 PCA 的主要特征向量估计器，并证明了该估计器在稀疏条件下可以达到最优收敛速率。同时，也证明在某些情形下，通常的 PCA 可以达到最小最大收敛速率。

Feb, 2012

稀疏主成分分析和迭代阈值法

本文针对特征数比样本个数大的情况，提出了一种新的迭代阈值方法，用于估计主成分空间，这种方法在高维稀疏场景下实现了主成分空间和主要特征向量的一致恢复和最优恢复。模拟实例也证明了其具有竞争性的性能。

Dec, 2011

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

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

May, 2023

稀疏主成分分析的近似算法

本文介绍了一种名为门限法的难以置信的精简主方向载荷方法，并将其与半定规划松弛相结合，以改进主成分分析的解释性。

Jun, 2020

主成分分析的最优性与次优性 I：尖峰随机矩阵模型

通过研究 Le Cam 的连续性，我们探讨了用于检测稀疏向量存在的测试的统计极限，包括非光谱测试，并证明了对于高斯 Wishart 集合，PCA 阈值对于正向 spikes（自然先验）是最佳的，但这并不总是负向 spikes 的情况。

Jul, 2018

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

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

Feb, 2017

基于协方差阈值的稀疏主成分分析

该研究分析了一个新颖的协方差阈值算法，并且证明了该算法在稀疏主成分分析中恢复支持的高可靠性，同时也探讨了核随机矩阵范数的新界限。

Nov, 2013