We propose a new fast algorithm for solving one of the standard formulations of frame-based image deconvolution: an unconstrained optimization problem, involving an lscr2 data-fidelity term and a non-smooth regularizer. Our approach is based on using variable splitting to obtain an equivalent constrained optimization formulation, which is then addressed with an augmented Lagrangian method. Experiments on a set of image deblurring benchmark problems show that our algorithm is clearly faster than previous state-of-the-art methods.