The work reported in this paper describes a statistical model that takes into account dependencies between the dictionary atoms and shows how this model can be used for sparse signal recovery. We follow the suggestion of several recent works (see the paper for more details) and model the sparsity pattern by a Boltzmann machine (BM), a commonly used graphical model. In this work we address topics like pursuit of the sparse representations and learning of the Boltzmann parameters. The effectiveness of our proposed approach is demonstrated both on synthetic data and image patches. The following freely available package contains all our Matlab code to reproduce the results of the above-mentioned paper.