The night never sets on Nuit Blanche:
Bob is shy of 143 days from writing a paper, but first he has to perform some computations and that's how much time it will take him. Maybe he could use octave and run these computations on the cloud. It cost money but not that much money. Laurent Duval's Decimate Brands of Banded matrices entry points to Gil Strang's recent papers on matrices that have inverse that are themselves banded. I commented on his blog:
Bob is shy of 143 days from writing a paper, but first he has to perform some computations and that's how much time it will take him. Maybe he could use octave and run these computations on the cloud. It cost money but not that much money. Laurent Duval's Decimate Brands of Banded matrices entry points to Gil Strang's recent papers on matrices that have inverse that are themselves banded. I commented on his blog:
If you know A and want to know A^-1 and know that both of them are sparse (banded here), then one might want to apply CS to this problem. Laurent Desmanet has done some work on that [1] and I wonder how his bounds are different if one knows in advance that A^-1 is itself sparse.I also note in Gil Strang's paper the need for other types of factorization:
May we mention one more group structure to be considered in a future paper. The matrices B = A + UV^T are banded plus fi nite rank, with the requirement that A^(-1) is also banded.uh...
I recently provided an answer on Quora to the following question; "What is compressed sensing (compressive sampling) in layman's terms?". My answer is here and below. Any improvement is welcome:
I think the best way to explain it in layman's terms is to use the example of group testing. Imagine you have a defective item placed among a large set of many similar but non-defective items. You also have a sensor that could detect whether any one item is defective but in order to find out which one it is, you'd have to perform as many measurements as there are items in the full (and large) set.
Imagine now the possibility of performing measurements on groupings of items: Instead of measuring one item at a time, one measures several items at a time and obtain one measurement per grouping being measured. Compressed sensing provides you a means of designing what these groupings are, i.e. you get to have rules on how to mix the different items together in different groupings.
Using techniques developed in compressed sensing, the number of measurements needed to find that one defective item is now much less than if you were measuring all these items one at a time. This is the reason the expression has the word "compressed" or "compressive" in it. "Sensing" refers to the act of measuring these group of items.
The means of figuring out which specific item is defective (out of many non-defective items) is instantiated in what is called a reconstruction solver [2]. The means by which one can perform the groupings is called multiplexing, encoding or measurement matrices [1]. The reason we can do all this is because there are few (defective) items (sparse solutions) out of very many (non-defective items). TheDonoho-Tanner phase transition [3] is a graph that tells you how many groupings (measurements) you need to have, given the known number of defective items and the total number of items.
A simple example is the 12-ball problem [4] where one looks for 1 lighter or heavier ball out of a set of 12 balls through comparative weighings. What is fascinating to the layman is that the ball groupings can be designed before performing all the weighings [5]. Compressed sensing allows one to generalize this problem to much larger sets than 12 items.Other examples include the single pixel camera built at Rice University by Rich Baraniuk's group [5] for which I provided a simple explanation of in [6] or the hyperspectral imager of David Brady at Duke [7]. In both cases, one doesn't acquire a single ray of light per pixel but rather a combination (a bunch, a mix) of rays of light (each coming from a different direction or spectral band or both) per pixel. Naturally, in order to obtain back a picture that can be understood by the human eye, one needs the reconstruction methods mentioned earlier [2]. Other hardware implementing this compressed sensing "trick" can be found in [8].
Vladimir Kofman reports on; Eric Fossum's recent presentation of Quanta Image Sensor at Yale University. Eric is the inventor of CMOS. Here is what I added in the comment section:
Thanks Vladimir for the heads-up.Eric answered.
Eric's description of QIS seem to be a good fit to the generic work undertaken in compressive sensing. In particular, I noted that the timebits planes were likely sparse (a condition for using compressive sensing). The track and sum process can be improved by a CS acquisition process. I noted specifically on slide 23, the statement that "Not really feasible at this time to consider 5.3 Tb/s data rate off chip". I agree but if the compression a la CS is done on the chip, you might get this number down.
Pierre Vandergheynst et al came out recently with one type of implementation of the concept of using CS on an imaging chip ( A (256x256) Pixel 76.7mW CMOS Imager/ Compressor Based on Real-Time In-Pixel Compressive Sensing, Vahid Majidzadeh, Laurent Jacques, Alexandre Schmid, Pierre Vandergheynst and Yusuf Leblebici, available at: http://goo.gl/2WZWt)
For those of you looking for a layman's introduction to CS, here is my recent attempt at answering this question on Quora: http://goo.gl/qGfw5
If you recall This is not a hardware-only or solver-only problem ... Iwas making a point but I got the multiplexing wrong. An anonymous commenter kindly commented:
Regarding the work presented by F. Magalhães et al., the projector used does not use DMD technology but LCD instead...
Keep up the excellent work with this website!
Thanks anonymous. So it is worse :-) after all. That subject brings me back to another point which is the effect of the multiplicative noise on the Donoho-Tanner phase transition. I like Bob's excellent computational adventures, when I grow I'd like to be just like him i,e, present some results on the blog first. Maybe I should do this first and delay by a day or two the announcement for y'all papers. What do you think ? Yes, No, Yes, No, Ok I'll do it.
Thanks Igor!
ReplyDeleteI like this way of presenting engineering in the raw. My students have an impression (and so did I) that since the papers they read are clean and direct, the work it took to get there must also have been clean and direct. What is not visible are the dead ends, bugs in the code, musings, etc. The things I would normally put in my private lab book, I now post to my research blog.
Through this, I have come in contact with several people across the globe (thanks in large part to you!), who have inspired me to look in new directions. It is like teh Internets has assumed the place of my PhD supervisor of old. I definitely encourage others to try this approach. Sure, it takes time to write and post, but for me that is when I begin to formalize my ideas more, and take a more critical look at my results, and those of others.
Most importantly for me in my pursuit of a permanent academic research position, my blog serves me as a hyperlinked and searchable database of my work, and papers that I have read. (My lab books, which total about 400 pages from the past 3 years, are not so searchable.) On my blog, I now have 186 posts, and I return many times to these to resume a research thread, or remind myself about the particulars of other work. Sometimes too, I need to retrieve code that I posted. My blog serves almost, but not quite, exactly unlike a subversion system.
Of course, there is the danger of someone "stealing" the ideas and results in the things I post; but I don't really care since: 1) I don't own knowledge in a way that it can be stolen; 2) advancing a problem brings new problems; and 3) I will have more ideas and results.