Image restoration through l0 analysis-based sparse optimization in tight frames

Sparse optimization in overcomplete frames has been widely applied in recent years to ill-conditioned inverse problems. In particular, analysis-based sparse optimization consists of achieving a certain trade-off between fidelity to the observation and sparsity in a given linear representation, typically measured by some ¿_p quasi-norm. Whereas most popular choice for p is 1 (convex optimization case), there is an increasing evidence on both the computational feasibility and higher performance potential of non-convex approaches (0 ¿ p < 1). The extreme p = 0 case is especial, because analysis coefficients of typical images obtained using typical pyramidal frames are not strictly sparse, but rather compressible. Here we model the analysis coefficients as a strictly sparse vector plus a Gaussian correction term. This statistical formulation allows for an elegant iterated marginal optimization. We also show that it provides state-of-the-art performance, in a least-squares error sense, in standard deconvolution tests.