研究总结了在不同分布情况下计算复杂性与 KL 散度之间的统计分层次关系,揭示了计算下界中的普适性原理。
Feb, 2019
提出了一种用于检测具有显著元素的子矩阵的测试方法,并计算了其检测边界和自适应敏锐度。在稀疏矩阵上得到了出色的表现,并扩展了结果以应对不同的矩阵类型和双侧替代假设。
Sep, 2011
研究插入聚类和子矩阵定位问题,提出四个算法,每个算法都在困难度更大的情况下无法成功。研究表明,机器学习和统计推断等算法之间的权衡,以及极小化恢复限制可能无法通过多项式时间算法实现。
Feb, 2014
研究了检测结构化低秩信号矩阵被加性高斯噪声污染的问题,包括在高斯混合模型中的聚类, 稀疏主成分分析和子矩阵定位。通过将第一和第二时刻方法应用于这些 “种植模型” 和零模型之间的似然比来导出阈值的上下界,我们证明了在信号矩阵过于微弱时没有任何算法可以检测其信号。
Jul, 2016
提出一种基于低阶半正定松弛和矩阵谱的方法,用于在特定条件下解决隐含团问题的下界证明。
Feb, 2015
该论文研究了矩阵完成问题的基本错误特征,通过分析噪声模型下的最小极大误差边界得出,结果表明最大似然估计量的复杂性正则化可以在多个噪声场景下,获得最小风险率。
Oct, 2015
研究在估计一个未知的 $n*m$ 矩阵 $X_0$ 时,采用了核范数正则化的方法进行去噪,并使用软阈值法求解核范数正则化问题,同时推导了极小极大均方误差的渐进性质及其临界阈值。
Apr, 2013
本文研究了在不知道子矩阵大小的情况下,如何在数据矩阵中定位具有较大条目值的子矩阵。我们建立了一个基于多尺度扫描统计量的优化框架,并开发了算法来逼近优化器。我们还展示了我们的估计器只需要与最小极大估计器具有相同阶数的信号强度,就可以在高概率下准确恢复异常。我们进行了一些模拟,表明我们的估计器相对于其他不需要先前子矩阵知识的估计器具有更好的性能,同时计算速度相对更快。
Jun, 2019
通过将联通子图嵌入到线性矩阵不等式(LMI)中,可以计算与联通子图相关的合适目标的优化。我们通过最优化凸目标函数解决了联通性的组合问题,并证明我们的测试对于指数族分布的一维和二维晶格是 Minimax 最优的。我们展示了联通子图族的内部导电对于表征可检测性扮演了重要角色。
Nov, 2014
本文研究在一个稀疏极限下,当底层隐藏向量(构建排名为一的矩阵)非零组成部分数与向量总维数的比例为亚线性,信噪比以适当的速度趋于无穷大时,估计被加性高斯噪声矩阵污染的排名为一的矩阵的统计和计算限制,并证明了渐近互信息的显式低维变分公式,分析了稀疏状态下的近似消息传递算法。对于伯努利和伯努利 - 拉德马赫分布向量,当稀疏度和信号强度满足适当的比例关系时,我们发现渐近最小和算法均方误差的全有或全无相变。在渐近情况下,统计与算法之间的差距发散,表明近似消息传递对于稀疏恢复是非常困难的。
Jun, 2020