Mean Estimation in High-Dimensional Markov-Dependent Gaussian Mixtures

We explore the problem of mean estimation for a high-dimensional binary symmetric Gaussian mixture model, where the label (sign) follows a Markovian dependency structure. For the time-inhomogeneous chain structure we propose a spectral estimator based on a partition of a subset of the samples to blocks. We develop a computationally efficient algorithm to find the optimal blocks, and derive minimax lower bounds on the estimation loss of any estimator, which (almost) match the loss of our proposed estimator. The resulting minimax rate illuminates the interplay between the sample size, dimension, signal strength, and the memory in determining the minimax rate. We further discuss the generalization of our work to the tree-structured Markov Random Field formulation.

M.Sc. student under the supervision of Prof. Nir Weinberger.