0

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?

flag
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
1 
 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

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.