具有能量分布依赖样本复杂度的稀疏主成分分析

《IEEE Transactions on Information Theory》：Sparse Principal Component Analysis with Energy Profile Dependent Sample Complexity

　　

摘要：

我们研究高维、样本受限设定下的稀疏主成分分析，旨在恢复由少数坐标支撑的主导成分。尽管取得了广泛进展，但大多数方法和分析都是针对平坦尖峰情形定制的，当尖峰能量在支撑集上分布不均时，提供的指导作用有限。受此启发，我们提出了谱能量追逐法（SEP），这是一种有效的迭代方案，通过反复筛选和重新选择坐标，其样本复杂度能够适应能量分布特征。我们的框架围绕一个结构函数 s(p) 展开，该函数量化了尖峰能量在其前 p 个条目上的累积情况。据我们所知，SEP 是首个受完整能量分布支配的样本复杂度保证的多项式时间 SPCA 方法：它在 m ? max_1≤p≤k p s²(p) log n 个样本下成功，对于平坦尖峰，恢复了经典的 k² log n 速率，对于充分集中的分布，则改进为 k log n。作为一种轻量级后处理，证明单次截断幂迭代能使最终估计器达到一致的统计误差界。使用平坦分布和偏移正则化衰减分布进行的经验模拟验证了 SEP 能够适应分布结构，无需针对特定分布进行调整，且性能优于现有算法。