标题： 统计与计算极限用于稀疏矩阵检测 显示英文标题

标题： Statistical and Computational Limits for Sparse Matrix Detection

摘要： 本文从统计和计算的角度研究了在白高斯噪声污染下检测高维稀疏矩阵的基本极限。 我们考虑行和列各自为$k$-稀疏的$p\times p$矩阵。 我们提供了稀疏矩阵检测的统计和计算极限的精确描述，这准确地描述了何时达到最优检测是容易的、困难的或不可能的。 尽管本文考虑的稀疏矩阵没有明显的子矩阵结构，相应的估计问题根本没有计算问题，但当稀疏度级别$k$超过矩阵大小$p$的立方根时，检测问题有一个令人惊讶的计算障碍：达到最优检测边界在计算上至少与解决植入团问题一样困难。 相同的统计和计算极限也适用于稀疏协方差矩阵模型，在该模型中每个变量最多与其他$k$个变量相关。 构建统计最优检验的关键步骤是稀疏矩阵的一个结构性质，这可能具有独立的兴趣。 显示英文摘要

摘要： This paper investigates the fundamental limits for detecting a high-dimensional sparse matrix contaminated by white Gaussian noise from both the statistical and computational perspectives. We consider $p\times p$ matrices whose rows and columns are individually $k$-sparse. We provide a tight characterization of the statistical and computational limits for sparse matrix detection, which precisely describe when achieving optimal detection is easy, hard, or impossible, respectively. Although the sparse matrices considered in this paper have no apparent submatrix structure and the corresponding estimation problem has no computational issue at all, the detection problem has a surprising computational barrier when the sparsity level $k$ exceeds the cubic root of the matrix size $p$: attaining the optimal detection boundary is computationally at least as hard as solving the planted clique problem. The same statistical and computational limits also hold in the sparse covariance matrix model, where each variable is correlated with at most $k$ others. A key step in the construction of the statistically optimal test is a structural property for sparse matrices, which can be of independent interest.