Computational and statistical boundaries for submatrix localization in a large noisy matrix
大型噪声矩阵中子矩阵定位的计算与统计边界
We study in this paper computational and statistical boundaries for submatrix localization. Given one observation of (one or multiple nonoverlapping) signal submatrix (of magnitude $\lambda$ and size $k_{m}\times k_{n}$) embedded in a large noise matrix (of size $m\times n$), the goal is to optimal identify the support of the signal submatrix computationally and statistically. Two transition thresholds for the signal-to-noise ratio $\lambda/\sigma$ are established in terms…