  In this paper, we consider Bayesian image denoising based on a Gaussian
Markov random field (GMRF) model, for which we propose an new algorithm. Our
method can solve Bayesian image denoising problems, including hyperparameter
estimation, in $O(n)$-time, where $n$ is the number of pixels in a given image.
From the perspective of the order of the computational time, this is a
state-of-the-art algorithm for the present problem setting. Moreover, the
results of our numerical experiments we show our method is in fact effective in
practice.
