研究如何检测在被加性高斯噪声污染的大矩阵中具有提高平均值的小子矩阵的最小极小方法,考虑复杂度理论角度的统计性能和计算成本之间的平衡问题,得出当矩阵规模 p→无穷大时,当子矩阵大小 k =Θ(pα) 时,计算复杂度会对统计性能造成严重的惩罚,并且关于支持恢复的困难程度也得出了结果。
Sep, 2013
研究插入聚类和子矩阵定位问题,提出四个算法,每个算法都在困难度更大的情况下无法成功。研究表明,机器学习和统计推断等算法之间的权衡,以及极小化恢复限制可能无法通过多项式时间算法实现。
Feb, 2014
提出一种基于低阶半正定松弛和矩阵谱的方法,用于在特定条件下解决隐含团问题的下界证明。
Feb, 2015
介绍了一个用于证明计算问题下界的框架,其中算法可使用对统计查询的访问来实现,并应用于检测种植的双部分图团分布中的统计查询算法的复杂性的近乎最优下界。
Jan, 2012
研究了检测结构化低秩信号矩阵被加性高斯噪声污染的问题,包括在高斯混合模型中的聚类, 稀疏主成分分析和子矩阵定位。通过将第一和第二时刻方法应用于这些 “种植模型” 和零模型之间的似然比来导出阈值的上下界,我们证明了在信号矩阵过于微弱时没有任何算法可以检测其信号。
Jul, 2016
提出了一种用于检测具有显著元素的子矩阵的测试方法,并计算了其检测边界和自适应敏锐度。在稀疏矩阵上得到了出色的表现,并扩展了结果以应对不同的矩阵类型和双侧替代假设。
Sep, 2011
研究检测大型 Erdős-Rényi 随机图中种植的小型密集社区的问题,并探究其计算复杂性及相变现象,结果可应用于恢复密集社区和逼近最密 $K$- 子图。
Jun, 2014
研究对称数据矩阵中的隐藏社区的恢复问题,聚焦于两种渐近恢复保证类型:弱恢复和精确恢复,并推导出恢复的充分条件和必要条件。结果表明,算法提供弱恢复时,可以通过简单的投票程序在额外线性时间内升级以实现精确恢复。
Sep, 2015
本文提出了一种统计查询下限技术,用于解决高维学习问题中高斯分布的学习和鲁棒性学习问题,并得出了样本复杂度和计算复杂度之间存在的超多项式差距,同时提供了一个新的方法来解决一些相关的无监督估计和测试问题。
Nov, 2016
在稀疏主成分检测的背景下,我们提供了计算效率的统计代价存在的证据。我们通过检测它能够检测到的最小信号强度来测量测试性能,并提出了一种基于半定规划的计算有效方法。同时,我们证明了这个测试的统计性能不能被任何计算有效的方法严格改进。我们的结果可以被视为基于某些种植团问题的某些实例不能在随机多项式时间内被解决这一假设的复杂性理论下界。
Apr, 2013