Minimax optimal submatrix detection: Sharp non-asymptotic rates
Given an observation $\mathbf Y \in \mathbb{R}^{d_1\times d_2}$ from the model $\mathbf Y = \mathbf X + \mathbf E$ where $\mathbf X$ is constant and $\mathbf E$ has i.i.d. $N(0,1)$ entries, we consider the problem of detecting a planted submatrix in the mean matrix $\mathbf X$. Specifically, we aim to distinguish the null hypothesis $\mathbf X = 0$ from the alternative hypothesis in which $\mathbf X$ is non-zero only on a submatrix of size $s_1 \times s_2$ with elevated entries bounded below by $μ>0$. We establish a minimax lower bound characterizing how large $μ$ must be to ensure that the two hypotheses are distinguishable with high probability. Furthermore, we derive novel minimax-optimal tests achieving the lower bound, and describe extensions of these tests that are adaptive to unknown sparsity levels $s_1$ and $s_2$. In contrast with previous work, which required restrictive assumptions on $s_1,s_2, d_1$ and $d_2$, our non-asymptotic upper and lower bounds match for any configuration of these parameters.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling
Low-rank matrix completion concerns the problem of estimating unobserved entries in a matrix using a sparse set of observed entries. We consider the non-uniform setting where the observed entries are sampled with highly …
Low-Rank Matrix CompletionMatrix CompletionComputational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
The interplay between computational efficiency and statistical accuracy in high-dimensional inference has drawn increasing attention in the literature. In this paper, we study computational and statistical boundaries for…
Computational EfficiencyEstimation of discrete distributions with high probability under $χ^2$-divergence
We investigate the high-probability estimation of discrete distributions from an \iid sample under $χ^2$-divergence loss. Although the minimax risk in expectation is well understood, its high-probability counterpart rema…
Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
We consider two closely related problems: planted clustering and submatrix localization. The planted clustering problem assumes that a random graph is generated based on some underlying clusters of the nodes; the task is…
ClusteringCommunity DetectionStochastic Block ModelSubmatrix localization via message passing
The principal submatrix localization problem deals with recovering a $K\times K$ principal submatrix of elevated mean $\mu$ in a large $n\times n$ symmetric matrix subject to additive standard Gaussian noise. This proble…
2kCommunity Detection