论文标题
Erdős-rényi图和稀疏矩阵的第二特征向量的噪声灵敏度
Noise sensitivity of second-top eigenvectors of Erdős-Rényi graphs and sparse matrices
论文作者
论文摘要
我们考虑Erdős-rényi图的邻接矩阵的特征向量，并通过随机重新采样条目来研究其方向的变化。令$ \ mathbf {v} $为与Erdős-rényi图的第二大特征值相关的特征向量。在随机选择给定矩阵的$ k $条目并重新采样后，我们获得了另一个与从重新采样过程获得的矩阵的第二大特征值相对应的eigenVector $ \ mathbf {w} $。我们证明，在某个稀疏制度中，$ \ mathbf {w} $是“几乎”正交到$ \ mathbf {v} $，如果$ k \ gg n^{5/3} $，则具有很高的概率。另一方面，如果$ k \ ll q^2 n^{2/3} $，其中$ q $是稀疏参数，我们观察到$ \ mathbf {v} $和$ \ mathbf {w} $是“几乎是” coluinear。这将Bordenave，Lugosi和Zhivotovskiy的最新工作扩展到了Erdős-Rényi模型。
We consider eigenvectors of adjacency matrices of Erdős-Rényi graphs and study the variation of their directions by resampling the entries randomly. Let $\mathbf{v}$ be the eigenvector associated with the second-largest eigenvalue of the Erdős-Rényi graphs. After choosing $k$ entries of the given matrix randomly and resampling them, we obtain another eigenvector $\mathbf{w}$ corresponding to the second-largest eigenvalue of the matrix obtained from the resampling procedure. We prove that, in a certain sparsity regime, $\mathbf{w}$ is "almost" orthogonal to $\mathbf{v}$ with high probability if $k\gg N^{5/3}$. On the other hand, if $k\ll q^2 N^{2/3}$, where $q$ is the sparsity parameter, we observe that $\mathbf{v}$ and $\mathbf{w}$ are "almost" collinear. This extends the recent work of Bordenave, Lugosi and Zhivotovskiy to the Erdős-Rényi model.
