Optimized Dictionaries

Some months ago, I was assigned to start looking at Compressed Sensing (CS), specifically, CS reconstruction. At the time, Sungkwang and Dr. Fowler were working on some IHT reconstruction techniques, and I was given a paper to look at that took a whole different approach: a generalized, non-causal form of the Total Variation (TV) metric. With TV, the sparse domain is assumed to be the gradient domain, and the gradients are calculated along the vertical and horizontal casual directions. The paper I was looking at took the approach that we should look at all of a pixel's neighbors and use some weight assigned to each one to calculate the gradient in the following manner:

gradient(P) = P - (w1*P_up + w2*P_left + w3*P_right + w4*P_down)

So, that’s great, you say, but where do these weights come from? The authors had some methods for calculating the weights and proposed that during the reconstruction process, if there weren't some oracle weights, then you should use an EM approach to optimize the reconstruction result. This sounds good on paper, but in implementation, it was a whole different story.

I want to talk about the infeasibility of using an approach like this. For convex optimization reconstruction algorithms, performing a single reconstruction takes enough time, even for a small image. If we are taking the time to reconstruct any interestingly sized image, doing it once takes long enough, doing it 5 or so times waiting for the metrics to converge gets pretty rediculous. Waiting on this algorithm to run further reinforced to me the need for A) Blocking strategies, and B) faster reconstruction algorithms, such as IHT methods.

Anyway, to avoid this problem of retraining, the authors suggested that the weights be found once for an entire class of images, and then applied broadly to future images that fall within that class. Perhaps there might have been adequate results in applying this method, but the reconstruction results for this approach were so poor that I discontinued my research into the method.

But, at the time, it got me thinking about the entire "learning" approach to CS, which brought me to the idea of optimizing the random matrices to get better results, and in the same vein, to optimize them to a class of images. After thinking about it for a little longer, I shelved the thought. Why? I find the implied assumptions of oracle information about a problem unpalatable. There are already many papers within the body of CS work that rely on assumptions of a certain level of sparsity and, in the case of optimized weightings and dictionaries, of the actual source signal.

In my opinion, there is still too much work to be done on creating and improving reconstruction algorithms to begin degenerating into these sorts of focused optimizations. So, like the previous thought about a weighted gradient space, I shelved the idea of optimizing dictionaries. I figured that it was just the musings of an early graduate student that didn't know much about the field, yet.

You can image my surprise, then, when I opened this month's SPS Content Gazette and found the following work:

• J.M. Duarte-Carvajalino, G. Sapiro. "Learning to Sense Sparse Signals: Simultaneous Sensing Matrix and Sparsifying Dictionary Optimization."

And within that work is a reference to an earlier one that I was not aware of:

• M. Elad. "Optimized Projections for Compressed Sensing."

I'm not calling into question the quality or robustness of these works, but I find myself torn. I find the concept of optimizing not only the random projections, but also the transformation into the sparse basis, very, very interesting, but I am wondering about practicality of these methods. As an engineer, I like optimizations, I like the idea of taking a general idea and applying it to a specific situation, but as a researcher, I like general solutions that are guaranteed to work for a wide range of problems.

What do you all think?