Sparse regularization has been receiving an increasing interest in the literature. Two main difficulties are encountered when performing sparse regularization. The first one is how to fix the parameters involved in the regularization algorithm. The second one is to optimize the inherent cost function that is generally non differentiable, and may also be non-convex if one uses for instance an ℓ0 penalization. In this paper, we handle these two problems jointly and propose a novel algorithm for sparse Bayesian regularization. An interesting property of this algorithm is the possibility of estimating the regularization parameters from the data. Simulation performed with 1D and 2D restoration problems show the very promising potential of the proposed approach. An application to the reconstruction of electroencephalographic signals is finally investigated.