|
Abstract:
|
We present a novel method for obtaining lower bounds on the minimal signal strength required to asymptotically distinguish (in a minimax sense) Gaussian graphical models whose graph structures are separable by a single edge. The proposed strategy bypasses lengthy calculations by reducing the problem to an exercise of counting closed walks on a given graph. We apply our lower bound technique to obtain signal strength limitations in various testing problems including connectivity detection and cycles detection, and self-avoiding path length testing. In addition, we provide computationally tractable algorithms which can provably handle such structure testing problems optimally up to a scalar multiplier, whenever we are given a high-dimensional sufficiently sparse graphical model. Finally, we propose a generalization of our lower bound strategy, capable of addressing problems whose graphical structures may differ in multi-edged sets. Using this lower bound we analyze the signal strength required to test whether the graph at hand contains a sparse star subgraph, in addition to a sparse clique detection example.
|
