稀疏随机正则图中边缘特征向量普遍性的尖锐平方根界-计算机科学-机器学习-算法.pdf

稀疏随机正则图中边缘特征向量普遍性的尖锐平方根界

LEONHARDNAGEL

摘要.我们研究了随机正则图的特征向量在投影到固定方向时的行为。对于一个具

有-正则且有个顶点的随机图，其中度数随着缓慢增长，我们证明了这些

投影近似地遵循正态分布。我们的主要结果建立了Berry-Esseen界限，显示收敛到

高斯分布时误差为，对于度数成立。这个界限显著改

进了之前结果中的误差项，这些误差项的缩放为，并通过建立一个匹配的下界证

明我们的缩放是最佳的。我们的证明结合了三种技术：(1)利用正则图特定方差

本结构的精细集中不等式，(2)避免迭代过程的基于向量的解算子分析，以及(3)结

译合Stein方法与图论工具来控制高阶波动的框架。这些结果为从稀疏到中等密度图

的过渡中的特征向量普遍性提供了精确常数。

中

1

v

91.介绍

5

21.1.背景与主要结果.关于随机正则图中特征向量统计的研究揭示了一个惊人

4

1的普遍现象：边缘特征向量表现出与Tracy-Widom的本征值标度[14]相匹配

7.的高斯波动，速率是。在最近的一项工作中[12]，我们为固定次数情况下

0这种普遍现象建立了首个定量的Berry-Esseen界限。

5

2本文将这些结果扩展到缓慢增长的次数，并具有对的最

:

v优依赖性。关键见解是，方差考虑规定了一个自然的缩放，而现有工作引

i

x用了界限[1]。我们通过精炼的集中不等式、Stein-Malliavin技术和自洽格

r

a林函数比较的结合来实现这一最优界限。

定理1(最优的Berry-Esseen定理对于增长的次数).令为一个在个顶点

上的均匀随机的正则图，其中满足对于某个固定的有

。对于任何确定性的单位向量，满足（其中是

全一的向量），我们有

sup

其中是归一化邻接矩阵的第二个特征向量，是标准正态分布函数，并且