MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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,fessler.pdf – dranxo Oct 24 '11 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 '11 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: – dranxo Oct 25 '11 at 7:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.