Statistical and computational limits for sparse matrix detection (Q2196237)

The focus of the paper is to understand the fundamental limits of detecting sparse matrices from both the statistical and computational perspectives. While achieving the optimal estimation rates does not suffer from any computational barrier, it turns out the detection counterpart does when and only when the sparsity level exceeds the cubic root of the matrix size. The main result is a tight characterization of the statistical and computational limits of detecting sparse matrices in both the Gaussian noise model and the covariance matrix model, which precisely describe when achieving optimal detection is easy hard and impossible, respectively.