Jul, 2016

随机图中归一化拉普拉斯算子的特征向量的极限定理

PDF
TL;DR本研究证明：在一个有限维的随机点积图的归一化拉普拉斯矩阵的 $d$ 个最大特征值所对应的特征向量的组成部分符合中心极限定理。作为推论，我们证明了对于随机块模型图，归一化拉普拉斯矩阵的谱嵌入的行收敛于多元正态分布，并且每个行的均值和协方差矩阵是其所对应顶点块成员的函数。与邻接矩阵的特征向量的先前结果一起，我们通过多元正态分布之间的 Chernoff 信息比较了嵌入方法选择对后续推理的影响，演示了嵌入方法都不占优势，因此推断潜在块分配的任务无法通过这些嵌入方法获得显著提升。
发现论文，激发创造
  • 独立边随机图中的邻接矩阵和拉普拉斯矩阵的集中度

    在随机图中，将边权值视为概率，如果最小期望度数为 ω(ln n)，则随机图的邻接矩阵和拉普拉斯矩阵集中于边权为概率的加权图，应用于债券渗透和不均匀随机图问题中，通过引入矩阵 concenetration 和集中不等式得到新的结论。

    Nov, 2009

  • 随机拉普拉斯矩阵和凸松弛

    对于一大类随机拉普拉斯矩阵来说，最大特征值与最大对角线元素的大小关系是紧的。其中最大特征值可以用半正定松弛方法解决，从而解决了一些凸松弛算法紧度的问题。这也可以解释 Erdős-Rényi 图的连通阈值和谱范数矩阵估计等问题。

    Apr, 2015

  • 邻接矩阵和拉普拉斯矩阵谱嵌入的外样本扩展极限定理

    研究了针对图嵌入方法的样本外推问题，通过最小二乘方法和极大似然方法得出的新数据点嵌入向量近似服从中心极限定理及浓度不等式，并提供了一个既简捷又精确的计算成本与估计精度权衡框架。

    Sep, 2019

  • 大型随机矩阵有限低秩扰动的特征值和特征向量

    研究了随机矩阵的有限低秩扰动的特征值和特征向量，发现扰动的矩阵极端特征值收敛于非随机值且存在相变现象，临界点与积分变换有关。

    Oct, 2009

  • 利用光谱嵌入技术对随机游走特征值的锐利界限

    本文介绍了利用图的随机行走矩阵的前 k 个非平凡特征向量对图进行谱嵌入的方法，并使用此框架限制了所有图的所有特征值，并提出了一种新的工具 —— 谱嵌入，在分析可逆马尔可夫链中使用。

    Nov, 2012

  • 关于随机块模型图的谱嵌入性能和揭示网络结构

    本文分析 Laplacian 和 adjacency 频谱嵌入在随机块模型图中块分配恢复方面的相对性能，并研究了嵌入性能与底层网络结构之间的关系，结果表明 Laplacian spectral embedding 更适用于相对稀疏的图，而 adjacency spectral embedding 更适用于核心 - 边缘网络结构。

    Aug, 2018

  • 流形热插值下高斯核化图拉普拉斯的特征收敛

    研究随机采样的流形上的图拉普拉斯矩阵与 Laplace-Beltrami 算子的谱收敛，证明可以通过与流形热核进行卷积来构造近似的本征函数，从而实现本征值和本征向量的收敛，证明了多维数据中的收敛率和一些低本征值的点与 Dirichlet 形式收敛之间的联系，进一步证明了密度校正图拉普拉斯下的点和 Dirichlet 形式收敛速度。

    Jan, 2021

  • 随机图的浓缩和正则化

    本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度，其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图，对于稀疏随机图，其期望度数小于 o（logn），需要使这种度数正则化，本文通过一些方法，例如重量重排或删除足够的边等操作来实现，演示了在社区检测问题中，集中结果的应用。

    Jun, 2015

  • 随机内积核矩阵的谱范数

    本文研究了一种内积核随机矩阵模型，证明其经验谱分布在大 $n$ 和 $p$ 极限下收敛于一定的测度。通过将其与一个具有相同极限谱的 GUE 矩阵的轨迹矩进行比较，研究了奇数内核函数的情况，该矩阵的谱范数几乎必定收敛于极限谱的边缘。本研究的动机是分析一种利用协方差阈值处理来统计检测和估计稀疏主成分的方法，并且本文的结果表征了样本协方差矩阵在零设置下的最大特征值极限。

    Jul, 2015

  • 稀疏随机图：特征值和特征向量

    证明了对于正则随机图 Gn,d (d→∞)，该图的特征值的半圆律，补充了 McKay 在固定 d 的情况下的先前研究结果。同时，对 Erdős-Rényi 随机图 G (n,p) 特征向量的无穷范数得出了上限，回答了 Dekel-Lee-Linial 的问题。

    Nov, 2010