Region Detection in Markov Random Fields: Gaussian Case
This work addresses the sample-deficient scenario in Gaussian Markov fields, offering a practical solution for applications where learning edge parameter distributions is more critical than exact edge locations, though it is incremental as it builds on existing information-theoretic frameworks.
The paper tackles the problem of model selection in Gaussian Markov fields when sample sizes are insufficient for full graph recovery, focusing instead on detecting spatial regions with similar edge parameters. It establishes new information-theoretic bounds showing that a bounded number of samples can consistently recover these regions and introduces an efficient region growing algorithm that achieves high accuracy in synthetic simulations.
We consider the problem of model selection in Gaussian Markov fields in the sample deficient scenario. The benchmark information-theoretic results in the case of d-regular graphs require the number of samples to be at least proportional to the logarithm of the number of vertices to allow consistent graph recovery. When the number of samples is less than this amount, reliable detection of all edges is impossible. In many applications, it is more important to learn the distribution of the edge (coupling) parameters over the network than the specific locations of the edges. Assuming that the entire graph can be partitioned into a number of spatial regions with similar edge parameters and reasonably regular boundaries, we develop new information-theoretic sample complexity bounds and show that a bounded number of samples can be sufficient to consistently recover these regions. Finally, we introduce and analyze an efficient region growing algorithm capable of recovering the regions with high accuracy. We show that it is consistent and demonstrate its performance benefits in synthetic simulations.