研究稀疏噪声下低秩矩阵推断的主成分分析,发现信号恢复存在两类相变。
Sparse corruption in low-rank matrix inference: the PCA benchmark
- 用复制法和种群动力学解析稀疏噪声下的主成分分析性能
- 识别出两个临界信号强度:θ_crit(信号可恢复)与θ_b(特征值脱离谱体)
- 适用于图结构噪声模型,对网络数据分析有重要启发
主成分分析(PCA)是从小幅噪声观测中提取低秩信号的标准工具。已知在大矩阵极限下,当一阶信号被密集同质噪声污染时,会出现著名的BBP相变:异常特征值出现与对应特征向量对齐同时发生。本文研究稀疏噪声情形,将噪声矩阵建模为具有有限平均连通性的加权无向图邻接矩阵。利用复制法,通过种群动力学求解递归分布方程,解析计算了典型最大特征值、最大特征向量分量密度及与信号的平方重叠度。我们发现信号强度随图连通性变化存在两种相变:θ_crit(特征向量开始恢复信号)推广了BBP相变,θ_b(信号相关特征值脱离谱体)。当噪声均值非零时,因结构性稀疏图异常值导致两相变不再重合,平方重叠出现不连续跃迁;若信号特征值虽为异常值但低于结构性异常值,则第二大规模特征值对应的特征向量仍能连续恢复信号。我们将方程特化至泊松和随机正则度分布,复现了高连通性下的稠密噪声结果,并通过大规模矩阵数值对角化验证了理论预测。
原文摘要 · Abstract (English)
Principal Component Analysis (PCA) is a standard tool for extracting a low-rank signal from noisy observations. It is known that applying PCA to a rank-one signal corrupted by a dense, homogeneous noise, in the large matrix size limit, the celebrated BBP transition occurs, where the emergence of an outlying eigenvalue and the alignment of the corresponding eigenvector occur at the same critical signal strength. Here we study the case of sparse noise corruption. The noise matrix is modelled as the adjacency matrix of a weighted undirected graph with finite average connectivity. Using the replica method, we analytically compute the typical top eigenvalue, the top eigenvector component density, and the squared overlap with the signal, through recursive distributional equations solved by population dynamics. We identify two signal-strength transitions as functions of graph connectivity: $θ_{\rm crit}$, marking signal recovery by the top eigenvector and generalising the BBP transition, and $θ_{\rm b}$, where the signal-related eigenvalue detaches from the bulk. For noise with nonzero mean, these transitions need not coincide because of a structural sparse-graph outlier, leading to a discontinuous transition in the squared overlap with the top eigenvector. The same top-eigenpair formalism also predicts the overlap of the signal with the eigenvector associated with the second largest eigenvalue when the signal eigenvalue is an outlier but remains below the structural outlier, where the transition is continuous. We specialise the equations to Poissonian and Random Regular degree distributions, recover dense-noise results in the large-connectivity limit, and validate the theory by numerical diagonalisation of large matrices.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。