Minimax rates for sparse signal detection under correlation

Subhodh Kotekal, Chao GaoarXiv 2021 · DOI · arXiv

Abstract

In high-dimensional statistics, the Gaussian sequence model serves as a fundamental framework for understanding the limits of sparse signal detection. While the independent noise case is well-understood, real-world data often exhibit correlation. This paper fully characterizes the nonasymptotic minimax separation rate for sparse signal detection in the Gaussian sequence model with $p$ equicorrelated observations. We demonstrate that correlation can be a blessing, a curse, or irrelevant depending on its strength. Furthermore, we identify new phase transitions in the minimax separation rate at sparsity levels $\sqrt{p}$ and $p-\sqrt{p}$, and extend these results to group-structured correlation models involving multiple random effects.

Introduction

The challenge of detecting sparse signals—identifying a few non-zero components within a high-dimensional vector—is a cornerstone of modern statistical inference. Traditionally, the minimax separation rate, which defines the minimum signal strength required for reliable detection, has been studied under the assumption of independent and identically distributed (i.i.d.) Gaussian noise. However, in many practical applications, such as genomics or longitudinal studies, observations are correlated due to shared environmental factors or repeated measurements.

This research addresses the fundamental question: How does correlation influence the difficulty of sparse signal detection? By analyzing equicorrelated and group-structured models, we provide a rigorous map of the statistical landscape, revealing that the relationship between correlation and detection difficulty is non-monotonic and highly dependent on signal sparsity.

Problem Formulation and Methodology

The Model

We consider a Gaussian sequence model where the observation vector $Y$ is given by $Y = \theta + \xi$. Here, $\theta$ is an $s$-sparse signal vector, and $\xi$ represents correlated Gaussian noise. In the equicorrelated case, the noise is modeled as having a shared random effect, a structure common in linear mixed models. The goal is to determine the minimax separation rate $\epsilon^*$, the threshold above which the null hypothesis ($H_0: \theta = 0$) can be distinguished from the alternative ($H_1: \theta \in \Theta_s(\epsilon)$).

Analytical Techniques

To derive the minimax rates, the authors employ several key strategies:

  1. Orthogonal Decomposition: The detection problem is decomposed into two distinct sub-problems: detecting the signal component orthogonal to the correlation (Problem I) and the component aligned with the shared random effect (Problem II).
  2. Data Transformation: A projection-based transformation is introduced to decorrelate the data. This involves adding a controlled amount of auxiliary independent noise to facilitate the separation of the signal from the shared random effect.
  3. Hybrid Test Statistics: The optimal detection procedure utilizes a combination of $\chi^2$-type tests (optimal for dense signals) and specialized thresholding statistics (optimal for high sparsity).
  4. Adaptive Scanning: The authors prove that an adaptive procedure can achieve the optimal rate even when the true sparsity level $s$ is unknown, by scanning across potential sparsity regimes.

Key Insights: The Blessing and the Curse

The research reveals three distinct regimes based on the correlation level $\gamma$:

  • Weak Correlation ($\gamma \lesssim 1/\sqrt{p}$): Correlation is statistically irrelevant. The minimax separation rate remains identical to the independent noise case: $\epsilon^{*2} \asymp s \log(1+p/s^2) \vee \sqrt{p}$.
  • Moderate Correlation: Correlation acts as a "curse." The shared noise obscures the signal without being strong enough to be accurately estimated, thereby increasing the signal strength required for detection.
  • Strong Correlation: Correlation becomes a "blessing." In this regime, the shared random effect is so dominant that it can be estimated and subtracted from the observations. This effectively cleans the data, allowing for the detection of signals that would be invisible in the independent case.

Phase Transitions

The transition into the "blessing" regime is not uniform. The study identifies critical phase transitions at sparsity levels $s \approx \sqrt{p}$ and $s \approx p - \sqrt{p}$. These thresholds determine when the benefits of correlation begin to outweigh the noise it introduces. Notably, a sharp discontinuity in the detection rate appears when moving from a nearly dense signal ($s=p-1$) to a completely dense signal ($s=p$) under strong correlation.

Group-Structured Correlations

Extending the analysis to models with $R$ groups (multiple random effects), the authors find that the group structure fundamentally alters the detection problem. The number of groups introduces a new layer of complexity, changing how information is "borrowed" across observations. The minimax rates in these models exhibit different behaviors than the single-group equicorrelated case, highlighting the importance of structural assumptions in experimental design.

Conclusion and Implications

This work provides a theoretical foundation for choosing experimental designs. For instance, in settings where signals are expected to be very sparse ($s < \sqrt{p}$), a correlated (within-subjects) design may be significantly more powerful than an independent (between-subjects) design.

While this characterization is exhaustive for the $L_2$ norm under Gaussian noise, future work remains to explore different metrics (such as the $L_\infty$ norm) and non-Gaussian noise distributions. The ultimate goal remains a unified theory for sparse detection under arbitrary covariance structures, for which this study provides a critical stepping stone.

Summary updated

Abstract

We fully characterize the nonasymptotic minimax separation rate for sparse signal detection in the Gaussian sequence model with $p$ equicorrelated observations, generalizing a result of Collier, Comminges, and Tsybakov. As a consequence of the rate characterization, we find that strong correlation is a blessing, moderate correlation is a curse, and weak correlation is irrelevant. Moreover, the threshold correlation level yielding a blessing exhibits phase transitions at the $\sqrt{p}$ and $p-\sqrt{p}$ sparsity levels. We also establish the emergence of new phase transitions in the minimax separation rate with a subtle dependence on the correlation level. Additionally, we study group structured correlations and derive the minimax separation rate in a model including multiple random effects. The group structure turns out to fundamentally change the detection problem from the equicorrelated case and different phenomena appear in the separation rate.
BibTeX
@misc{kotekal2021minimax,
  author = {Subhodh Kotekal and Chao Gao},
  title = {{Minimax rates for sparse signal detection under correlation}},
  year = {2021},
  eprint = {2110.12966},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2110.12966},
}
Figure