研究如何检测在被加性高斯噪声污染的大矩阵中具有提高平均值的小子矩阵的最小极小方法,考虑复杂度理论角度的统计性能和计算成本之间的平衡问题,得出当矩阵规模 p→无穷大时,当子矩阵大小 k =Θ(pα) 时,计算复杂度会对统计性能造成严重的惩罚,并且关于支持恢复的困难程度也得出了结果。
Sep, 2013
研究对称数据矩阵中的隐藏社区的恢复问题,聚焦于两种渐近恢复保证类型:弱恢复和精确恢复,并推导出恢复的充分条件和必要条件。结果表明,算法提供弱恢复时,可以通过简单的投票程序在额外线性时间内升级以实现精确恢复。
Sep, 2015
本文研究了用于稀疏恢复的正交最小二乘算法以及与之相关的采样矩阵的限制等距性质,证明了在满足特定条件下,算法能够从采样中精确恢复出 $k$- 稀疏向量的支撑集,并提供了对于一般情况下无法恢复的支撑集的上界调节量。
Nov, 2016
研究了检测结构化低秩信号矩阵被加性高斯噪声污染的问题,包括在高斯混合模型中的聚类, 稀疏主成分分析和子矩阵定位。通过将第一和第二时刻方法应用于这些 “种植模型” 和零模型之间的似然比来导出阈值的上下界,我们证明了在信号矩阵过于微弱时没有任何算法可以检测其信号。
Jul, 2016
通过对高度破损的测量信号进行稀疏信号恢复,本文证明了一个令人惊讶的现象,并保证了当污染度较高时仍能够稳定恢复稀疏信号。
Feb, 2011
在 “可能但艰难” 的稀疏主成分分析中,我们使用亚指数时间算法的能力来探索稀疏度和恢复时间的平滑权衡,提供了一种新的演变家族,并对低阶似然比进行分析,从而证明了我们算法所实现的权衡是最优的。
Jul, 2019
本文研究多元回归中的分组 Lasso,使用基于 L1/L2 范数的分块正则化进行支持融合恢复或恢复 B * 非零行的集合,证明了分组 Lasso 在高维缩放下对于问题序列 (n、p、s) 成功的阈值和失败的阈值,并使用模拟演示了理论结果的锐度。
Aug, 2008
本文提出并研究了高斯机制的一种复杂变体,通过使用该变体输出的矩阵与 $M$ 的最佳秩 - k 近似之间的 Frobenius 范数之差被限制在大约 $\tilde {O}({\sqrt {kd}})$,这可以改善先前的工作,前者需要每对 $M$ 的前 k 个特征值之间的差异至少为 $\sqrt {d}$,而后者仅需要相邻的前 k 项的差异。
Jun, 2023
该研究证明了基于谱的划分算法可以在保证性能的同时,实现稀疏切割,同时将分析扩展到其他图划分问题中。
Jan, 2013
我们研究了随机块模型(SBM)中具有大型簇和无法恢复的小型簇的图聚类。我们提出了一种基于半定规划(SDP)的算法,可以恢复大型簇而不受其余簇大小的影响。我们的研究结果在存在大量小簇的情况下,达到了更低的样本复杂度,并为递归聚类问题提供了改进的算法。
Aug, 2023