Yesterday, I was on Muthu's weekly hangout where he, Andrew McGregor and others talked about streaming algorithms. I really like the idea of having algorithms dealing with high throughput data that cannot be recorded. It really is a thought provoking process to say the least. And we are getting there. If you recall the recent presentation by Eric Fossum, the inventor of CMOS for imaging, he is interested in building a new kind of imaging sensor that can deal with a 10Tbits/s transfer rate, yes 1 Terabytes per second give or take 200 GBytes/second.
In a different direction, we now have 15 megapixel cameras for less than $300. What about a camera that doesn't store data only some statistics as in data streaming algorithms ? What if instead of a "normal" lens, we use a random lens in front of the imaging chip. Each pixel receives a linear combination of light rays from different locations, directions and wavelengths at very high speed, but only the statistics of that data is eventually stored.
One would imagine that the back-end electronics would become highly simplified and as a result a cheaper design. One could not contemplate an image reconstruction in the traditional sense nor would we have much in the way of calibration, but should we care ? What type of estimation problem can be solved with this type of camera ?
For more information on Sketching / Streaming algorithms you may want to read this
For more information on Sketching / Streaming algorithms you may want to read this
- wonderful blog entry by László Kozma on Sketching data structures
- Muthu's PODS 2011 Invited Tutorial on Data Streams Research: Where to Go.
- Muthu's lectures on Data Streaming Algorithms
- Muthu's count-min sketch & its applications page (and its relationship to compressive sensing, ),
- High-throughput sketch update on a low-power stream processor, Yu-Kuen Lai, Gregory T. Byrd, ANCS 2006. Presentation.
- Merrimac - Stanford Streaming Supercomputer Project
- The Stanford Imagine Project
This idea has been added to the Technologies Do Not Exist list.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
Interesting, this may have to be removed soon, as a device that doesn't exist that is.
ReplyDeleteI'm currently engaged in a masters (MIng) at the University of Johannesburg, South Africa. I only came across the concept of compressed sensing recently, to find that the device i've been developing for the past year is just that...A streaming camera.
I'll send you relevant information when my dissertation is approved. All I can say at the moment is that it's exceedingly cheap to produce (thanks to the pressures of a shoestring budget, and a non-existent tech industry in the country). The amount of device-side computation is little more than a low-end microcontroller. The compressive sensing approach was developed independent of the community (dumb luck that I just never ran across the topic in lit. review), and thus takes a different approach, with different ideas about basis functions.
I hope to forward you the publishable details soon enough.