Minimax Structured Normal Means Inference

The prevalence of high-dimensional signals in modern scientific investigation has inspired an influx of research on recovering structural information from noisy data. These problems arise across a variety of scientific and engineering disciplines; for example identifying cluster structure in communication or social networks, multiple hypothesis testing in genomics, or anomaly detection in sensor networking. Specific structural assumptions include sparsity [13], low-rankedness [11], cluster structure [15], and many others [8]. The literature in this direction focuses on three inference goals: detection, localization or recovery, and estimation or denoising. Detection tasks involve deciding whether an observation contains some meaningful information or is simply ambient noise, while recovery and estimation tasks involve more precisely characterizing the information contained in a signal. These problems are closely related, but also exhibit important differences, and this paper focuses on the recovery problem, where the goal is to identify, from a finite collection of signals, which signal produced the observed data. One frustration among researchers is that algorithmic and analytic techniques for these problems differ significantly for different structural assumptions. This issue was recently resolved in the context of the estimation, where the atomic norm [8] has provided a unifying algorithmic and analytical framework, but no such theory is available for detection and recovery problems. In this paper, we provide a unification for the recovery problem, leading to deeper understanding of how signal structure affects statistical performance.