- In this work we present a new approximate Bayesian compressed sensing scheme. The new method is based on a unique type of sparseness-promoting prior, termed here semi-Gaussian owing to its Gaussian-like formulation. The semi-Gaussian prior facilitates the derivation of a closed-form recursion for solving the noisy compressed sensing problem. As part of this, the discrepancy between the exact and the approximate posterior pdf is shown to be of the order of a quantity that is computed online by the new scheme. In the second part of this work, a random field-based classifier utilizing the approximate Bayesian CS scheme is shown to attain a zero error rate when applied to fMRI classification.