Abstract: Fully connected Boltzmann machine models can be used to provide a comprehensive description of statistical dependencies between sparse coefficients but with high time complexity. To improve the speed and quality of the Boltzmann machine-Bayesian matching pursuit (BM-BMP) method, an improved algorithm was proposed. First, the maximum a posteriori (MAP) estimation of the BM-BMP algorithm is decomposed into its value at the last iteration and an increment; thus, it only needs to calculate the increment in each iteration, which greatly reduces the computational time. Second, by calculating the mean of the significant MAP estimations, an effective approximation is obtained for the minimum mean square error (MMSE) estimation and a smaller reconstruction error is achieved. Compared with the BM-BMP, this method reduces the running time on average by 73.66% while improving the peak signal to noise ratio (PSNR) by 0.57 dB.