提出一种基于低阶半正定松弛和矩阵谱的方法,用于在特定条件下解决隐含团问题的下界证明。
Feb, 2015
研究检测大型 Erdős-Rényi 随机图中种植的小型密集社区的问题,并探究其计算复杂性及相变现象,结果可应用于恢复密集社区和逼近最密 $K$- 子图。
Jun, 2014
利用半定规划及二元变量,针对含有噪声的观测变量和图的边缘矩阵进行数据重构和分析,可以对图中两个社区及其相关性进行分析与检测。
Apr, 2014
考虑在稀疏随机网络中检测紧密社区的问题,将其形式化为在随机图中测试是否存在密集子图。在本文中,我们研究渐近稀疏情况下的信息理论下限,并比较了各种测试方法的性能,发现我们的检测边界是尖锐的。
Aug, 2013
研究了检测结构化低秩信号矩阵被加性高斯噪声污染的问题,包括在高斯混合模型中的聚类, 稀疏主成分分析和子矩阵定位。通过将第一和第二时刻方法应用于这些 “种植模型” 和零模型之间的似然比来导出阈值的上下界,我们证明了在信号矩阵过于微弱时没有任何算法可以检测其信号。
Jul, 2016
在这篇论文中,我们研究了在一般的二元博弈和高斯矩阵模型中的精确社区恢复问题,这两种模型分别捕捉了随机块模型、子矩阵定位和 Z2 同步作为特例。我们还研究了有关社区分配标签的智能信息可用的情况,将其建模为通过噪声通道传递真实标签:二进制擦除通道(其中某些社区标签已知而其他被抹去)或二进制对称通道(其中某些标签被翻转)。我们对智能信息对精确恢复的信息论极限的影响提供了统一的分析,扩展了之前的研究并拓展到新的设定。此外,我们设计了一个简单但最优的谱算法,将智能信息(如有)与矩阵观测的特征向量结合起来。利用入元素特征向量分析的强大工具 [Abbe, Fan, Wang, Zhong 2020],我们表明我们的谱算法可以模仿所谓的 “精灵辅助估计器”,其中第 i 个精灵辅助估计器在精灵揭示其他标签的情况下,最优计算第 i 个标签的估计。这一观点为最近的一系列工作中各种精确恢复问题的谱算法的最优性提供了统一的理解。
Jun, 2024
研究如何检测在被加性高斯噪声污染的大矩阵中具有提高平均值的小子矩阵的最小极小方法,考虑复杂度理论角度的统计性能和计算成本之间的平衡问题,得出当矩阵规模 p→无穷大时,当子矩阵大小 k =Θ(pα) 时,计算复杂度会对统计性能造成严重的惩罚,并且关于支持恢复的困难程度也得出了结果。
Sep, 2013
本文研究在带有局部性质的图中恢复社区的问题,提出了一种算法,它在测量数量上近线性,并且能够实现恢复的信息理论限制。
Feb, 2016
研究总结了在不同分布情况下计算复杂性与 KL 散度之间的统计分层次关系,揭示了计算下界中的普适性原理。
Feb, 2019
本文提出了一种算法,用于在恶意干扰下检测包含损坏节点的随机模型中的社区结构,并在 $Z_2$ 同步问题中实现了最优恢复阈值。借助关键的可识别性证明和 Grothendieck 范数的推动效应,该算法突破了 Kesten-Stigum 阈值的技术瓶颈。
May, 2023