Day 4 -- A Veritable Cornucopia of Compressed Sensing

If you were going to come to ICASSP for one day, this would probably have been the day you chose to come (if you read these blogs, anyway). The morning consisted of a CS poster session and a talk by Michael Wakin. This afternoon consisted of an entire lecture session: Compressive Sensing: Theory and Methods. Yes, it seems IEEE has decided on the -ive rather than the -ed. Also, I think today will consist of fewer pictures, because most of the ones I got tended towards blurry and the back of folk's heads. Those poster crowds can get rough.

The first poster I saw was "Empirical Quantization for Sparse Sampling Systems"  by Michael Lexa out of the University of Edinburgh, formerly out of Rice. (Rice really pumps out the DSP don't they?) He's a Nuit Blanche-er, so Igor can go ahead and give a little fist pump :P As for the work, I find it pretty cool that folks are beginning to look at the quantization problems. This method of quantization, Michael said, is best understood in the context of "quantization for classification." It seems that the target for this technique is something akin to  Mishali & Eldar's Sub-Nyquist wideband sampler. I'm pretty far from throughly understanding the work, so I'm afraid that my further explanation won't do much justice to it. Be sure to check it out. If you're handy with the Kullback-Leibler, you should feel pretty comfortable with this paper. Great work, Michael, hopefully that "spouse's pay check" grant will let us see more of the same :)

After talking for a bit about what we were working on, Michael pointed me towards Jason Luska, from Rice, and Marco Duarte, formerly of Rice now at Princeton, who both worked on the single-pixel camera. I'm eager to see one of these things in action, and maybe I won't have to wait very long. Jason told me that a recent startup has formed for the production of these devices, and that recently they have put together a portable version, so the Single-Pixel Camera is finally out of the lab and capturing IR in the natural world. I'm glad to hear that work is progressing on it! The new versions are apparently running at high resolution (1024x768 I believe) and thanks to some optimization folks, Jason says the reconstructions are "under a minute". I believe they're still using the l1 BP approach, but I can't be sure. He also hinted at some future work on "in the loop" reconstruction feedback to the encoder for distilled image enhancement, which sounds complicatedly wonderful.

Marco also reminisced about the first six months of building the camera, saying they spent they spent the first six months reconfiguring the reconstructions, inserting proposals from new research all along the way trying to correct the erroneous results they were getting only to find out that the problem all along was faulty optics. Ouch! Thank you both for the conversation.

Wakin's talk, "Concentration of Measure for Block Diagonal Measurement Matrices", I found to particularly interesting, since the blocked-approach we've been using amounts to this same approach. I imagine that we'll be making use of this theoretical framework in the future, and I'd love to see it expanded into a journal article. I've been looking at some similar phenomena and wonder if they can be fit into this same framework. The only difference is that I've been phrasing what I've been doing as a correlation between block energies rather than a concentration. I'll have to fiddle around some more.

Marco also gave a talk at the afternoon session, "Kronecker Product Matrices for Compressed Sensing", which was also very interesting because of his kind of "fusion" of basis functions to act as a sparse 3D basis for the joint reconstruction of hyperspectral datacubes. I'm wondering if this would be useful at all with Dr. Fowler's Compressive Projection PCA. I also really liked Silvia Gandy & Isao Yamada's "Alternating Minimization Techniques for the Efficient Recovery of a Sparsely Corrupted Low-Rank Matrix". Its a little bit of a different application of an l1 minimization, but the end result is very interesting, and I would like to see more examples of it. The one given was separating shadowing and specular effects from faces given a database of a face under different lighting conditions. I had seen something based on this last year and I'm wondering if this was the same work.

I also took a look at the "Bayesian Compressed Sensing Imaging Using a Gaussian Scale Mixture" poster shown by George Tazagkarakis. It seemed pretty solid, though I didn't get many details on the reconstruction time, and the quality measures were a little bit hard to directly compare to some other methods. However, this was one of a few papers that I saw today that make use of the GSM as a sparsifying prior, rather than a laplace or gaussian (which does a terrible job) prior. There was another interesting prior for the Bayesian crowd that was shown in the CS lecture session: the Inverse Gamma prior, used in "Efficient Sparse Bayesian Learning via Gibbs Sampling" by Xing Tan, Jian Li, and Peter Stoica. I think there was a Jefferys prior thrown into the mix sometime today, as well. All I can say is, all you BCS folks are insane. 

Okay, thats all for now, check back later this evening or tomorrow :)

Day 3 -- A Break

There was one more talk at the Dictionary Learning session that I wasn't able to post about thanks to some really wonky internet at the conference. Right at the end it gave out and I lost all the notes that I made...guess I learned my lesson!

"Ultrasound Tomography with Learned Dictionaries" Ivana Tosic, Ivana Jovanovic, Pascal Frossard, Martin Vetterli, Neb Duric

It was on the reconstruction of sound speed through ultrasound tomography samples that used l1 regularization as an added constraint to offer better performance than a least squares approach.

I have some apologies to make:

Firstly, I missed the session on Video and Motion Analysis last night, which is unfortunate because there were two papers presented during that session of particular interest to us (though Sungkwang did attend, and I'm pressing him to make a write up :P ). The two papers were

"Motion Estimation from Compressed Linear Measurements" Vijayarghavan Thirumalai, Pascal Frossard

"Compressive Sensing and Differential Image Motion Estimation" Nathan Jacobs, Stephen Schuh, Robert Pless

Also, this morning I had intended to attend a talk in the Target Detection & Localization session by the folks over at Duke:

"Hyperspectral Target Detection from Incoherent Projections" Kalyani Krishnamurthy, Maxim Raginsky, Rebecca Willett

Unfortunately, I got caught up in the Dictionary Learning session and didn't make it in time for this talk, but Zach Harmany, one of their colleagues at Duke, told me it was a pretty good presentation, and I'm sorry I missed it.

Last night, Sungkwang and I were having pizza out at this great little Italian bar down the road and talking about CS and the nature of research. At a big event like this, its easy to see how "far" research has come. Yes, I did use quotations there. Maybe my brain is wired a bit differently, but I'm a big fan of quality over quantity, which is a topic that I think many researchers have been moaning about for many decades. The problem, of course, is how to quantify the effectiveness of research dollars spent, and ultimately quantity measure has been adopted because of its objectiveness. I'm not sure its something that can be easily changed, and solution is not exactly well defined.

Also, after looking at many posters the past couple of days and mulling over everything, I'm beginning to wonder about the nature of the transition in research from finding answers to challenging problems to having challenging and complex solutions and finding problems to put them on. There seems to be this major disconnect with what the "point" of all this is. Perhaps I'm talking much more like a PhD student and much less like a future professor, and thats okay, I suppose. But I have an investment in all this, too, its my literal bread and butter as well. 

What I'm getting at is this: I can see myself getting very tired, very fast with some of the self-serving nature of research. In the end, it cannot be about the complexity of your contribution but its meaningfulness. Of course, many significant contributions to the community and humanity as a whole are inherently complex. The theory underlying wavelets can be thought of as "complex", but the final solution is, in fact, an elegant one. I suppose I would just like to see the pursuit of elegance in engineering research as it is in many scientific pursuits. 

I want research to consist of wooded vales, tobacoo pipes, benches, good outside conversation and collaboration (without the nagging consistent fear of theft), conferences of under 200, and a constant focus on solving the present problems definitively. A pipe dream, I suppose. I'm probably about 70 or 80 years too late for that.

This kind of got me thinking about a conference for strictly CS related topics. I hadn't heard of one yet, maybe its already happened and I've missed the boat. Many things in the field are still in what I'd call a "high-entropy" state and haven't yet coalesced into some standard models of which problems we're solving and what context we are solving them in. It seems like every paper has a different results metric and its not clear what to take seriously and what not. I can't tell you how many times I've started reading a CS paper with a very intriguing abstract only to find it fairly light and completely impractical. There seems to be a lot of people walking around with their hammers giving a one-go at the CS "nail."

I'm still very much in favor of seeing more thought going into the hardware behind CS. Until there are some very robust sampling methodologies for a particular signal type, CS will remain on the sidelines of that field. The medical imaging community has done an excellent job making a case for CS, which I think is great. The imaging community, I think, needs a bit more work. Sure, the single pixel camera has been made, but thats far from "solving" the image and video signal sampling problem. There are so many other things to look at and validate, especially in the field of video. I'm actually really surprised that there hasn't been more hardware work to come out of Rice after the single pixel camera. I am becoming more and more convinced that we've got to be tying CS in with some kind of hardware framework. In other words, can we stop sampling in the wavelet domain, please? How does that make any physical sense? Where are these magical coefficient capturing cameras? 

CS is now beginning to be more well understood analytically, which is great, and provides us with insight into future implementations and what CS is capable of, but our empirical & physical results need a lot of catching up. Perhaps over the next year we'll see more of this :)

Okay, thats all for now. I hope you can bear with my idealism from time to time!

Day 2 -- Part 1

Today began with a plenary talk by Dr. Ronald W. Schafer of HP Labs, "A Celebration of the Science and Technology of DSP" which I found to be pretty interesting. I noticed a few nodding off here and there, and Dr. Schafer isn't exactly the most engaging speaker, but the history of DSP was very informative. For example, I had no idea that the first VLSI implementation of a DSP process was in fact the Speak & Spell. Sort of the foreshadowing of DSP's influence in the multimedia/entertainment domain. In speaking of the future of DSP, Dr. Schafer mentioned "who knows, maybe Compressed Sensing will be the new FFT." We can hope, right? I sort of wanted to give a little shout, but I supressed the urge. I'm a total fanboy, its true.

Afterwards, I talked to Ahmad Akl, who was presenting a poster by his colleagues Veria Havary-Nassab and Sadiq Hassan under Dr. Valaee at the University of Toronto, "Compressive Detection for Wide Band Spectrum Sensing". This paper was pretty interesting, more for the novelty rather than complexity of its application. The basic idea is that you have some set of transmitters that want to communicate on a shared medium, in this case at some wireless frequency. Basically, the total medium bandwidth, W, is split into a set of N discrete communication channels. Traditionally, to know on which of the channels to transmit, each device would have to scan through the entirety of W, checking the current signal energy at each communication band. Using CS, the approach is altered by sampling the entire band and sending it through a bank of K filters, where K < N. This acts as the columns of a measurement matrix, \Phi. Ahmad wasn't sure about which method was used to reconstruct the signal, but assumed it to be something like the standard \l_1 BP. 

The implication here is that the channel usage is in fact sparse on the whole. I asked about the situation in which the communication medium is in fact full, i.e. in the case of network congestion and Ahmad said "it wouldn't work." I can see this as being a potential negative to this process, but otherwise interesting. Ahmad will be presenting his work "Accelerometer-Based Gesture Recognition via Dynamic-Time Warping, Affinity Propagation, & Compressive Sensing" on Friday, so I'll try and stop by for his poster.

Also talked to Markus Flierl about his paper "A l1-Norm Preserving Motion Compensated Transform for Sparse Approximation of Image Sequences" which was a pretty heady work and I would be dishonest if I said that I followed all of it, but I'll try to convey the gist. He suggested to start with his previous work "A Motion-Compensated Orthogonal Transform with Energy Concentration Constraint". He said that the idea was "not practical" but more of an exercise in what is possible. I only started to begin to understand this while eating lunch at Chen's Kitchen, just down the street from the hotel. Sungkwang and were trying to think about what you could actually do with an l1 preserving transform, but we came up empty. I'm not really sure what this would be useful for, but I think that was Markus meant by "not practical". I asked him if he thought there was any confluence between these ideas and Compressive Sensing, but he was of the opinion that they would be unsuited due to CS's emphasis on linear projections into the measurement basis. I'm sure someone will find use for this, however!

Next, I spoke with Dimitri Milioris about his group's work "Multiple-Measurement Bayesian Compressed Sensing Using GSM Priors for DOA Estimation". Before today, I hadn't really ever heard of Arrival (DOA), but it seems to be pretty popular with the beamforming crowd. Also, Bayesian CS seems to have a really good showing at ICASSP this year. There are quite a few papers being presented that make use of this methodology. To be honest, I've kind of stayed far away from BCS because of some its complexity, and the simplicity of iterated methods just make sense to me, but the Bayesian approach seems very powerful in the noisy setting. I'll have to sit down and really get into it a bit more. Anyway, back to the paper at hand. Basically, in this work, they are trying to determine an angle in single degree precision (though I'm sure it could be upped fairly easily) that is the correct angle between the receiver and the source. There are 180 angles to choose from in this example. This is represented by a 180 element vector, consisting of 0's at the incorrect angles and a 1 at the correct angle. This is the target of the reconstruction. Also, their method makes use of multiple receivers to add a bit more informational power to the system. Dimitri said they found optimal performance using Gaussian Scale Mixtures due to their closeness to Dirac's, but with heavy tails. 

Dimitri also tipped me off to a paper by his colleague, George Tazagkarakis "Bayesian Compressed Sensing Imaging Using a Gaussian Scale Mixture" which will be presented as a poster on Thursday. I talked to George a little bit about the complications of having all your techniques being restricted to the decoder side and the problematic nature of CS in that it becomes very non-intuitive to apply the power of modern DSP methods when you simply don't have the original data to work with (modelling, motion compensation, etc). He also told me that these papers were presented a little out of order, as the DOA paper is an extension of the imaging technique. I look forward to asking some questions about BCS with GSM on Thursday.

Unfortunately, I was not able to attend the lecture on "Using Reed-Muller Sequences as Deterministic Compressed Sensing Matrices for Image Reconstruction" or "Non-Convex Group Sparsity: Application to Color Imaging" as both of these took place during the Biomedical Imaging session which took place concurrent to the Scalable and Multiview Coding session I attended. However, it seems I would have been better served going to the Biomed sessions since 4/5 of the authors did not show up to the session I attended. Dr. Fowler was chairing the session, and to quote him it was "an embarrassment." He told us that perhaps one in ten authors might not attend, but four in five was kind of a new low. It seems that it is becoming more frequent that authors are submitting their papers to ICASSP/ICIP and paying the attendance fee, but never intending on actually showing up for their presentations in the hopes that the paper will slide under the door and still make it into the Proceedings. This gets kind of stale after a while and makes me wonder if the IEEE will begin actually enforcing its policies and become stricter on blacklisting. But, perhaps its just a condition of the economic times and it'll be better in the future. We'll have to see.

Thats all I have for now! I'll be making an update later tonight after attending the Video Motion Analysis session this evening which will feature two quite interesting papers...that is, if they come ;)

Day 2 -- It Begins

If you are at the conference and don't know where to go for dinner, go to Sol Irlandés. Its has a weird name, but its delicious.

I was able to take a look at the schedule last night, and I've put together a preliminary schedule for today.

Tuesday: 

• 9:00 - 10:00: Plenary Talk
• 11:30 - noon: "Using Reed-Muller Sequences as Deterministic Compressed Sensing Matrices for Image Reconstruction"
• noon - 12:30: "Multiple-Measurement Bayesian Compressed Sensing Using GSM Priors for DOA Estimation"
• 2:00 - 2:30: "Compressed Sensing for Bandwidth Constrained Systems"
• 4:00 - 6:00: Video Motion Analysis & Object Tracking Session, including the talk "Motion Estimation from Compressed Linear Measurements"

Looks like it will be a fairly full day! I'll update as I can throughout the day with more information about these and other talks.

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?