I am trying to speed up a sparse signal recovery algorithms.

My sensing matrix is a set of Toeplitz Blocks, M = [T1,T2,T3,...,Tk]

The objective is min ||Mx - b||_2^2 + ||x||1

What I'm actually doing is trying to encode an image with multiple patch-like bases, each of which can be centered anywhere on the image.

Is there any structure of my M = [T1,...,Tk] sensing matrix that I can take advantage of? For instance, can I efficiently compute (MM')^(-1/2) or do any other useful structure I can take advantage of to speed this up beyond naive applications (adapted to us the convolution operator) of other sparse recovery algorithms?