## L1-regularized Least Squares on a matrix with Toeplitz Blocks (not block-Toeplitz)

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?

-
Can you say more about what the matrix is? That looks like a $kn \cross n$ matrix but I'm not sure. Unless you're doing something unusual most of the your computation time should be least squares solving the $||Mx - b||^2$ term. There has been some work on this that might be interesting to you eecs.umich.edu/~fessler/papers/files/jour/05/… – rcompton Oct 24 2011 at 21:59
this link: citeseer.ist.psu.edu/viewdoc/… – rcompton Oct 24 2011 at 21:59
You're right, it's kn x n, or some small factor difference depending on how I deal with edge effects. I'm using iterative methods, like Iterative Shrinkage and Thresholding, and I've found a paper that uses a greedy method. None of this takes advantage of the Toeplitz structure except through the relative efficiency of applying the convolution. I'll take a look at that link, thanks. – DoubleJay Oct 24 2011 at 23:05
Ok well if it's just a stack of Toeplitz matrices I don't think you can do better than using FFTs. You can do much faster than iterative shrinkage and thresholding with Tom's method: ftp.math.ucla.edu/pub/camreport/cam08-29.pdf – rcompton Oct 25 2011 at 7:12