图 书 馆
隐团和隐子阵问题的改进平方和下界Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems |
|
| 课程网址: | https://videolectures.net/videos/colt2015_deshpande_submatrix_pro... |
| 主讲教师: | Yash Deshpande |
| 开课单位: | 信息不详。欢迎您在右侧留言补充。 |
| 开课时间: | 2025-02-04 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Given a large data matrix $A\in\reals^{n\times n}$, we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution $A_{ij}\sim P_0$, or instead $A$ contains a principal submatrix $A_{\sC,\sC}$ whose entries have marginal distribution $A_{ij}\sim P_1\neq P_0$. As a special case, the hidden (or planted) clique problem is finding a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided $|\sC|\ge C \log n$ for a suitable constant $C$. However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when $|\sC| = o(\sqrt{n})$. Recently, \cite{meka2013association} proposed a method to establish lower bounds for the hidden clique problem within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree-$4$ SOS relaxation, and study the construction of \cite{meka2013association} to prove that SOS fails unless $k\ge C\, n^{1/3}/\log n$. An argument presented by \cite{BarakLectureNotes} implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moment method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erd\"os-Renyi random graph. |
| 关 键 词: | 大数据矩阵; 主子矩阵; 隐团问题 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2025-03-30：zsp |
| 最后编审: | 2025-03-30：zsp |
| 阅读次数: | 1 |