Nuit Blanche: 08/01/2012

Friday, August 31, 2012

The Accidental Multispectral Coded Aperture Camera

Whereas some see a beautiful stained glass ....

I only see an accidental multispectral coded aperture camera

References:

Accidental pinhole and pinspeck cameras: revealing the scene outside the picture by Antonio Torralba, William T. Freeman
Does Richter's "4096 Colours" painting fulfill the Restricted Isometry Property for Sparse Signal Recovery ?

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.

The Impact of the Tail

Videos of your meeting or talk or course are appreciated in the tail..

from here.

Implementation: Signal Space CoSaMP Toolbox

From Mark Davenport's page:

The bulk of the Compressive sensing (CS) literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In practice, however, there are many signals that cannot be sparsely represented or approximated using an orthonormal basis, but that do have sparse representations in a redundant dictionary. Standard results in CS can sometimes be extended to handle this case provided that the dictionary is sufficiently incoherent or well-conditioned, but these approaches fail to address the case of a truly redundant or overcomplete dictionary.

This software package implements a variant of the iterative reconstruction algorithm CoSaMP for this more challenging setting. In contrast to prior approaches, the method is "signal-focused"; that is, it is oriented around recovering the signal rather than its dictionary coefficients.

For further details, see the paper "Signal Space CoSaMP for Sparse Recovery with Redundant Dictionaries," by M.A. Davenport, D. Needell, and M.B. Wakin.

Signal Space CoSaMP can be downloaded here; the Matlab files entitled "demo_*.m" provide several examples of how to invoke Signal Space CoSaMP and compare the results to traditional CS algorithms. The Matlab data (.mat) files necessary to reproduce the figures presented in the paper can be downloaded here. Please e-mail mdav-at-gatech-dot-edu if you find any bugs or have any questions.

The attendant paper: Signal Space CoSaMP for Sparse Recovery with Redundant Dictionaries by Mark A. Davenport, Deanna Needell, Michael B. Wakin. The abstract reads:

Compressive sensing (CS) has recently emerged as a powerful framework for acquiring sparse signals. The bulk of the CS literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In practice, however, there are many signals that cannot be sparsely represented or approximated using an orthonormal basis, but that do have sparse representations in a redundant dictionary. Standard results in CS can sometimes be extended to handle this case provided that the dictionary is sufficiently incoherent or well-conditioned, but these approaches fail to address the case of a truly redundant or overcomplete dictionary. In this paper we describe a variant of the iterative reconstruction algorithm CoSaMP for this more challenging setting. We utilize the D-RIP, a condition on the sensing matrix analogous to the well-known restricted isometry property. In contrast to prior work, the method and analysis are "signal-focused"; that is, they are oriented around recovering the signal rather than its dictionary coefficients. Under the assumption that we have a near-optimal scheme for projecting vectors in signal space onto the model family of candidate sparse signals, we provide provable recovery guarantees. We also provide a discussion of practical examples and empirical results.

Thursday, August 30, 2012

Implementation: BLENDENPIK: Supercharging LAPACK's Least-Squares Solver

A year ago, Petar Maymounkov commented on Finding Structure with Randomness

Is this what you are looking for:: http://pdos.csail.mit.edu/~petar/papers/blendenpik-v1.pdf

This is random preconditioning, which works well in practice.

and then, I wanted to follow up on it but did not. Here is the paper: BLENDENPIK: Supercharging LAPACK's Least-Squares Solver by Haim Avron, Petar Maymounkov and Sivan Toledo. The abstract reads:

Abstract. Several innovative random-sampling and random-mixing techniques for solving problems in linear algebra have been proposed in the last decade, but they have not yet made a signi cant impact on numerical linear algebra. We show that by using an high quality implementation of one of these techniques we obtain a solver that performs extremely well in the traditional yardsticks of numerical linear algebra: it is signi cantly faster than high-performance implementations of existing state-of-the-art algorithms, and it is numerically backward stable. More speci cally, we describe a least-square solver for dense highly overdetermined systems that achieves residuals similar to those of direct QR factorization based solvers (lapack), outperforms lapack by large factors, and scales signi cantly better than any QR-based solver.

The attendant code is here. If you recall this is inline with the subject of Streaming Data Mining

Implementation: Rapid Characterization of FPGAs with Matrix Completion

This is a little late but it has an implementation attached to it.

Rapid FPGA Delay Characterization Using Clock Synthesis and Sparse Sampling by Mehrdad Majzoobi, Eva Dyer, Ahmed Elnably, and Farinaz Koushanfar. The abstarct reads:

Abstract—This paper introduces a set of novel techniques for rapid post-silicon characterization of FPGA timing variability. The existing built-in self-test (BIST) methods work by incrementing the clock frequency until timing failures occur within the combinational circuit-under-test (CUT). A standing challenge for industrial adoption of post-silicon device proﬁling by this method is the time required for the characterization process. To perform rapid and accurate delay characterization, we introduce a number of techniques to rapidly scan the CUTs while changing the clock frequency using off-chip and on-chip clock synthesis modules. We next ﬁnd a compact parametric representation of the CUT timing failure probability. Using this representation, the minimum number of frequency samples is determined to accurately estimate the delay for each CUT within the 2D FPGA array. After that, we exploit the spatial correlation of the delays across the FPGA die to measure a small subset of CUT delays from an array of CUTs and recover the remaining entries with high accuracy. Our implementation and evaluations on Xilinx Virtex 5 FPGA demonstrate that the combination of the new techniques reduces the characterization timing overhead by at least three orders of magnitude while simultaneously reducing the required storage requirements.

The attendant code is here.

Wednesday, August 29, 2012

Around the blogs in 80 summer hours

Since the last Around the blogs in 80 summer hours, the flat line activity of the Summer on the interwebs seems to be over. First of all, we had quite a few implementation made available by their authors.

As usual these entries get to be featured longer and in a single entry. Releasing an implementation is serious work and I try to make a big deal out of it, so there.

When mentioning those subjects: Streaming Data Mining and the GraphLab and GraphChi group on LinkedIn, it occurred to me that, for my own sake, I needed to do a synthesis of what we are currently seeing. I applied to give a TEDxParis talk but they declined, unbeknownst to me the theme of the meeting was 2030 so I decided to provide a glimpse of August 25th, 2030 based on what we know, no crystal ball here just applying what we have seen so far and doing a little of interpolation.. Here are part 1 and 2 of the material on which the talk would have been based on:

Talking about TED, here is a TED Talk by Ramesh Raskar on Imaging at a trillion frames per second. The random bit of the week is this finding on The First Programmable Robot You've Never Heard of.

The activity on the blogs has regained some steam:

Dirk provided a nice overview of some of the talks at ISMP:

Bob tells us about EUSIPCO

Masaaki

Laurent features a call for papers on Time-frequency analysis and applications
Emmanuel explains his Radio silence. Lots of good stuff coming up.
Danny

Larry

Rich let us know that Rice Founds E-Learning Center
Andrej has set up a nifty Academic Countdown
Christian reminds us about the Bayes by the Bay meeting
Greg features Juha Vierinen's jitter project, GNU Ionospheric Tomography Receiver
Yannick let is know about a group meeting on CS and medical imagery in France.
Carter intends on building some Haskell version of some of the advanced Matrix factorization algorithms.
John lists the Patterns for research in machine learning
David has some advice on 7 Habits of the Open Scientist #3: Pre-publication dissemination of research

Finally, if you thought Nature was in the business of high quality and high impact papers, you might rethink that in light of this Guest Post: Terry Rudolph on Nature versus Nurture

Image Credit: NASA/JPL-Caltech/MSSS, Focusing the 100-millimeter Mastcam, layered buttes of Mount Sharp,

Monday, August 27, 2012

Predicting the Future: Randomness and Parsimony

[ Thus is part 2. Part 1 is here: Predicting the Future: The Steamrollers]

For many people, predicting the future means predicting the breakthroughs, and while this might seem reasonable at first, one should probably focus on how the steamrollers can precipitate these findings as opposed to expecting chance to be on our side.

One of the realities of applied mathematics is the dearth of really new and important algorithms. It is not surprising, it is a tough and difficult process. In turn, the mathematical tools we will use in the next 20 years are, for the most part, probably in our hands already. How can this fact help in predicting the future you say? Well, let us combine this observation with another one in the health care area, but it could be any other field that can be transformed through synthetic biology thanks to genomic sequencing.

First there is this stunning example recounted by David Valle in The Human Genome and Individualized Medicine (it is at 57min32s)

...First of all, acute lymphoblastic leukemia. When I was a house officer in the later '60s and early '70s, acute lymphoblastic leukemia was the most common form of childhood leukemia and had a 95 percent mortality rate - 95 percent mortality. Nowadays, acute lymphoblastic leukemia remains the most common chilhood leukemia. It has 95 percent survival rate, 95 percent survival/ So it went from 95 percent mortality to 95 percent survival. So what account for that change ? So actually if you look at it, the medicines that are currently being used are very similar, if not identical, to the medicines that we used all those years ago. So it's not the kinds of medicines that are being used. What it is, I would argue, is that oncologists have learned that this diagnosis is actually a heterogeneous group of disorders. And they've learned how to use gene expression profiling, age of onset, DNA sequence variation and other tools to subdivide the patients. In other words, move from one collective diagnosis to subcategories of diagnosis moving towards individualizing the diagnosis to individual patients and the manipulating their treatment according to which subdivision the patient falls. And that approach. a more informed approach in terms of differences between individual patient with the same diagnosis, has had a dramatic effect on the consequences of having ALL....

In other words, starting with the same medicines, it took us 40 years (most of that time without sequencing capabilities) to match a hierarchy of diseases to a hierarchy of drugs and processes. Back in the 70s, this matching of hierarchies entailed:

the ability to get a rapid feedback from drug trials
the ability to have enough statistics from a sub-group for certain drug trials

Because of the statistics required, treating rare diseases have been at odds with this process. How is this different nowadays ? Hal Dietz discusses that in Rational therapeutics for genetic conditions (see "...The Window Doesn't Close..."). and he points out that if you have the right tool to examine deep inside the metabolic networks through genome sequencing, then the window doesn't close. From the Q&A:

Question: Are Adults with Marfan syndrome all treatable ?

Hal Dietz: Yeah, so that'sa great question. The question is, are adults with Marfan all treatable or is the window of opportunity to make a difference over in childhood ? At least in our mice, we can allow them to become mature adults. They're sexually mature at about two months, by six months of age they are sort of mid-adult life and by a year of age they are old mice. And whether we start treatment right after birth, in the middle of that sequence, or at the end, we see the same kind of benefits. So we think that the window doesn't close, that there is an opportunity even later in life.

In short, with genomic sequencing, the matching process occurring in health care -a data driven hypothesis process- now becomes

the ability to get a rapid feedback from drug trials
the ability to get an information rich feedback from these drug trials

The Steamrollers that are Moore's law and Rapid Genomic Sequencing point to an ability to generate higher quality data at a faster pace than ever before while profoundly changing survival rates or curing diseases.

All would be well if the quality of the information from genomic sequencing did not come at the expense off an attendant large quantity of data. Let's put this in perspective: The genome comprises a billion information, the microbiome about ten times that and there are about seven billion people on Earth. If one were to decode the genome of the entire population, we would generate about 10^19 data. This is huge, it's more information than there are stars in the universe. However huge, this data is not that information rich, simply speaking there is a larger variety in the human genome between folks from the same tribe in Africa than any other humans living on the four other continents.

In short, the useful data actually "lives" in a much much much smaller world than the one produced by the combination of the Steamrollers. In order to handle this parsimonious needles within these very large haystacks, mathematical concentration of measure type of results have recently yielded different tools. Some of these methods use randomness as an efficient way of compressing this useful but sparse information.

What is the time frame for these tools using parsimony and randomness to be part of the standard toolbox in personalized medicine ?

Certainly less than 18 years. It took about 27 years to build efficient tools ( EISPACK (1972) - LAPACK (1999)) in linear algebra that are just now considering randomization (see Slowly but surely they'll join our side of the Force...). Using the parsimony of the data will probably be handled at a faster pace by crowdsourcing efforts such as scikit-learn. In the next eighteen years, we should expect libraries featuring standardized :Advanced Matrix Factorization Techniques as well as factorization in the Streaming Data model to be readily available in ready-to-use toolboxes. Parsimony also effectively embeds graph related concepts as well and one already sees the development of distributed computing beyond the now seven year old Hadoop such as GraphLab.

But the concepts of parsimony and randomness will also play a tremendous role in how we take data in the first place by changing the way we design diagnostic instruments. Sensing with parsimony aka Compressive Sensing will help in making this a reality. Besides aiding in reverse engineer biochemical networks,ir providing an effective way to compare genomic data, it will also help engineers devise new sensors or perfect older ones such as MRI. Expect new diagnostic tools.

Which gets us back to the original question: What can I say with certainty about August 25th, 2030 ? We will manage the large datasets coming out of the steamrollers only through the use of near philosophical concepts such as parsimony and randomness. By doing so we are likely to reduce tremendously our current number 1 and number 2 causes of death.

( Source for the last graph: The Burden of Disease and the Changing Task of Medicine, New England Journal of Medicine).

Stay tuned for the third installment of this series on Predicting the Future.

[ This would have been two or three slides at TEDxParis, see A Glimpse of August 25th, 2030 ]

Sunday, August 26, 2012

Predicting the Future: The Steamrollers

[ Thus is part 1. Part 2 is here:Predicting the Future: Randomness and Parsimony ]

In order to predict what will happen on August 25th, 2030, here is some history and perspective:

In 1975, while they had no idea how it would affect their business, Kodak engineers produced the first digital camera using a technology called CCD. It took the economies of scale of CMOS (brought forth by the development of computing) to drive down the cost of cameras so that anybody could own one.

CMOS for imaging started in the lab in the mid-90's, fast forward 14 years later, a billion smartphones with integrated CMOS cameras are produced per year. In short the economies of scale that followed Moore's law enabled the growth from a prototype into a mass market item in little over a decade. It did not happen by magic as entire industries' capital and government funding was poured in making this reality happen. In fact, algorithm development also helped. From Fueling Innovation and Discovery: The Mathematical Sciences in the 21st Century, there is a description of how the Fast Multipole Algorithm (FMM), discovered in the late 80s, helped:

....The applications of the Fast Multipole Method have not been limited to the military. In fact, its most important application from a business perspective is for the fabrication of computer chips and electronic components. Integrated circuits now pack 10 billion transistors into a few square centimeters, and this makes their electromagnetic behavior hard to predict. The electrons don’t just go through the wires they are supposed to, as they would in a normal-sized circuit. A charge in one wire can induce a parasitic charge in other wires that are only a few microns away. Predicting the actual behavior of a chip means solving Maxwell’s equations, and the Fast Multipole Method has proved to be the perfect tool. For example, most cell phones now contain components that were tested with the Fast Multipole Method before they were ever manufactured....

Some could argue that there must be a caveat, that this Moore's law cannot continue forever. Indeed, witness the recent bumps that have emerged in this rosy picture in the Scariest Graph I've Seen Recently. But that would be too pessimistic, this type of comparison featuring upcoming showstoppers with current technologies never allows for the inclusion of other competing technologies (see 1-bit cameras concepts (QIS, Gigavision Camera)), hence, because there is no reason it will stop, we will consider Moore's law to be holding for the next twenty years.

The other lesson from this recent past history shows that any competing technology to CMOS is bound to yield under the stress of this exponential growth (see Do Not Mess with CMOS ). In all, Moore's law or any law that is exponential in nature act as a steamroller and provides the best predictor to what is going to happen in the next fifteen to eighteen years.

I recently mentioned (see What is Faster than Moore's Law and Why You Should Care) that there was another technology that was growing faster than Moore's law: Genomic Sequencing.

From

DNA Sequencing Costs

In those cases of rapid growth, one always wonder if we are witnessing some sort of transient, an accidental bump or some sorts of asymptotics i.e. a real "law". Thanks to the Nanopore technology featured in a real test this year (2012), it looks like the growth rate of the Genomics law is bound to remain larger than Moore's law for a while longer. This fact translates into, for instance, the fact that data generated by genomics will overwhelm data currently produced by imaging CMOS (to give an idea of the growth of images and videos, YouTube recently stated that 72 hours of videos were uploaded to YouTube every minute ). While it took 14 years to go from one prototype to 1 billion units generated large amount of data in the CMOS example. It may take a shorter time span for this genomics technology to be an integral part of the medical profession and be part of our everyday life through synthetic biology.

It is stunning and somehow seems ludicrous to think of such a rapid integration of genomics into medicine. Indeed, one wonders how can something like this be that fast ? I have two examples

The first is anecdotal: Elaine Mardis, a researcher performing sequencing, has to change her presentation slides every fifteen days (she says so in this video). I have never heard somebody in the science and technology making such a statement, even off-hand.

The second example points to how slow the traditional publication process is. In the just released 2012 National Academy Press publication on Innovation and Discovery: The Mathematical Sciences in the 21st Century, one can read the following:

"....Interpreting the Human Genome

In all, human DNA contains about 3 billion “base pairs,” or rungs of the staircase. The goal of the Human Genome Project was to list all of them in order. Unfortunately, chemists can sequence only a few hundred base pairs at a time. To sequence the whole genome, scientists had to chop it into millions of shorter pieces, sequence those pieces, and reassemble them. "

[Emphasis added ]

If the Nanopore technology results hold, most of these algorithms for sequencing will become effectively useless (for sequencing) as the DNA is chopped off in larger fragments than current sequencing technology and hence can easily be put back together...

In summary, in this first part of this piece on predicting the future I described two technological steamrollers that will shape our technology landscape for the next 18 years. In part 2, I will describe the type of algorithms that will help us make sense of this tsunami of data being generated as a result of these two technologies. I will then try to translate this into what it will mean on August 25th, 2030. Stay Tuned.

[ This would have been two slides at TEDxParis, see A Glimpse of August 25th, 2030 ]

Saturday, August 25, 2012

A Glimpse of August 25th, 2030

I offered the organizers of TEDxParis to talk to their next event but they declined. Unbeknownst to me was the theme of the meeting: 2030. Given what we have seen so far in the burgeoning fields of compressive sensing, advanced matrix factorization, big data and so forth, subjects that are only 8 to 12 years old at most, I wonder how one could extrapolate something about our everyday life on August 25th, 2030 or 18 years from now. For that I'll be using some of the figures featured on Nuit Blanche.

Putting this into perspective, 18 years ago was August 25th, 1994. Google did not exist, Gopher was in full use by people who had access to the interwebs and most countries did not have commercial ISPs.

There are no dates but this list contains some of the most important algorithms (some additional thoughts can be found here and in the comments here), even though it is surprising that nobody seems to care that the FMM is not listed, it must be a CS bias. SIAM has a list that is both date stamped and dated but it does feature the FMM.

Stay tuned.

Friday, August 24, 2012

The First Programmable Robot You've Never Heard of

As I was visiting the Conservatoire National des Arts et Métiers museum of Technology (CNAM) in Paris the other day, I came upon a loom that I don't think I had ever heard of before. Back in 1740's, a man by the name of Jacques de Vaucanson devised a fully automated weaving process. According to Wikipedia:

His proposals for the automation of the weaving process, although ignored during his lifetime, were later perfected and implemented by Joseph Marie Jacquard, the creator of the Jacquard loom.

From that text, one could infer that it was just an earlier design of the Jacquard loom. It doesn't seem to be the case however:

Next to the loom, there are two descriptions, one in French and and one in English. The English version is only a subset of the full explanation provided in French. Here is my poor translation attmpt of the French text that is not provided in the English description:

A real automated weaving machine, the loom starts operating thanks to a simple handle and therefore radically transforms the gestures of the weaver. In 1747, The newspaper "Le Mercure de France" recounts the following: " One can see the whole cloth being fabricated without any human intervention, i.e. one can see the chain [sic] open, then the shuttle throws the frame, then the clapper hits the cloth with more accuracy than possible with the human hand"

The loom remained a prototype with no direct descendant. The mechanics inspired other inventors like Jacquard who did put it back in shape at the Conservatoire des Arts et Metiers at the beginning of the 19th century.

Let me get this straight, a fully programmable robot saw the light of the day in 1747 never to be directly copied later because it took jobs away from humans ? I did not know that, and I don't think I am the only one. The Jacquard loom was "inspired" by this machine and was successful a full sixty years later in part because it required human intervention. Let us also note the punch card mechanism at the top of this 1740's machine. That idea was the mainstay for programming computer in the 1960s.

Cute story 1: According to our tour guide, since the Vaucanson design required only a power source and removed human intervention. Many loom prototypes were destroyed by weavers who could become out of work had the machine been adopted. The story goes that to destroy the looms the workers used their wooden shoes (called sabot in French) and this is why the word sabotage is used when referring to the destruction of a piece of machinery.

Cute story 2: Also according to our guide, the expression "être un ane" (being a donkey, a slang for being dumb) is an expression that comes from the fact that skilled weavers were facing being in direct competition with the unskilled labor of a power source that was generally provided by a donkey.

Implementation: Spread spectrum magnetic resonance imaging - s2MRI

Gilles Puy tweeted about the release of the Spread spectrum MRI toolbox. From the page:

Spread spectrum magnetic resonance imaging - s2MRI

Abstract: We propose a novel compressed sensing technique to accelerate the magnetic resonance imaging (MRI) acquisition process. The method, coined spread spectrum MRI or simply s2MRI, consists of pre-modulating the signal of interest by a linear chirp before random k-space under-sampling, and then reconstructing the signal with non-linear algorithms that promote sparsity. The effectiveness of the procedure is theoretically underpinned by the optimization of the coherence between the sparsity and sensing bases. The proposed technique is thoroughly studied by means of numerical simulations, as well as phantom and in vivo experiments on a 7T scanner. Our results suggest that s2MRI performs better than state-of-the-art variable density k-space under-sampling approaches.

Toolbox: s2MRI_toolbox.zip or s2MRI_toolbox.tar.gz.

If you use this toolbox, please cite the following paper: Puy et al., "Spread spectrum magnetic resonance imaging," IEEE Transactions on Medical Imaging, vol. 31(3), pp. 586 - 598, 2012.

Comments: gilles {DOT} puy {AT} epfl {DOT} ch

Image Credit: NASA/JPL-Caltech
This image was taken by Navcam: Right A (NAV_RIGHT_A) onboard NASA's Mars rover Curiosity on Sol 17 (2012-08-23 17:18:51 UTC) .
Full Resolution

Thursday, August 23, 2012

Implementation: On Variable Density Compressive Sampling

Gilles Puy just tweeted the release of the code implementing the method described in the paper "On Variable Density Compressive Sampling" which we featured a year ago. From the page:

On Variable Density Compressive Sampling

Abstract: We advocate an optimization procedure for variable density sampling in the context of compressed sensing. In this perspective, we introduce a minimization problem for the coherence between the sparsity and sensing bases, whose solution provides an optimized sampling profile. This minimization problem is solved with the use of convex optimization algorithms. We also propose a refinement of our technique when prior information is available on the signal support in the sparsity basis. The effectiveness of the method is confirmed by numerical experiments. Our results also provide a theoretical underpinning to state-of-the-art variable density Fourier sampling procedures used in magnetic resonance imaging.

Code: VDS_code.zip or VDS_code.tar.gz.

If you use this code, please cite the following paper: Puy et al., "On Variable Density Compressive Sampling," in IEEE Signal Processing Letters, vol. 18(10), pp. 595-598, 2011.

Acknowledgement: This code make use of the function "oneProjectorMex" of the spgl1 toolbox. The SPGL1 toolbox is available at http://www.cs.ubc.ca/~mpf/spgl1/. The description of the theory of the SPGL1 algorithm is outlined in E. van den Berg and M. P. Friedlander, "Probing the Pareto frontier for basis pursuit solutions," SIAM J. on Scientific Computing, 31(2):890-912, 2008.

Comments: gilles {DOT} puy {AT} epfl {DOT} ch
Link to preprint
Link to published paper

Image Credit: NASA/JPL/Space Science Institute
W00075164.jpg was taken on August 20, 2012 and received on Earth August 22, 2012. The camera was pointing toward SATURN at approximately 1,483,173 miles (2,386,936 kilometers) away, and the image was taken using the CB2 and CL2 filters.

Compressive Source Separation: Theory and Methods for Hyperspectral Imaging - implementation -

On his Google + feed, Pierre Vandergheynst let us know that he and his colleagues :

Just released a new preprint on compressive source separation. The paper shows that you can perform source separation directly on compressive measurement. It's a great advantage for hyperspectral imaging or other modalities where datasets are huge. We also give theoretical guarantees on recovery. This is the first paper in a series: in this work we assume we know the dictionary of spectral signatures, but the next paper will deal with the blind case.

I also would like to stress that the paper comes with a reproducible research addendum: we provide the necessary code and data to reproduce our experimental results. It's all online and open. Use it, hack it, criticize, have fun. I really want to push this idea of providing code and data with all future papers of the lab.

The whole package (paper + addendum) can be downloaded here: https://infoscience.epfl.ch/record/180911?ln=en

Compressive Source Separation: Theory and Methods for Hyperspectral Imaging by Golbabaee, Mohammad; Arberet, Simon; Vandergheynst, Pierre. The abstract reads:

With the development of numbers of high resolution data acquisition systems and the global requirement to lower the energy consumption, the development of efficient sensing techniques becomes critical. Recently, Compressed Sampling (CS) techniques, which exploit the sparsity of signals, have allowed to reconstruct signal and images with less measurements than the traditional Nyquist sensing approach. However, multichannel signals like Hyperspectral images (HSI) have additional structures, like inter-channel correlations, that are not taken into account in the classical CS scheme. In this paper we exploit the linear mixture of sources model, that is the assumption that the multichannel signal is composed of a linear combination of sources, each of them having its own spectral signature, and propose new sampling schemes exploiting this model to considerably decrease the number of measurements needed for the acquisition and source separation. Moreover, we give theoretical lower bounds on the number of measurements required to perform reconstruction of both the multichannel signal and its sources. We also proposed optimization algorithms and extensive experimentation on our target application which is HSI, and show that our approach recovers HSI with far less measurements and computational effort than traditional CS approaches.

All the codes supporting this paper are here.

Wednesday, August 22, 2012

Implementation : Re-Weighted l_1 Dynamic Filtering for Time-Varying Sparse Signal Estimation and Sparsity penalties in dynamical system estimation

You probably recall this entry on Re-Weighted l_1 Dynamic Filtering for Time-Varying Sparse Signal Estimation. Adam Charles just sent me an update on the implementation:

Hi Igor,

I promised some code a few weeks ago when I emailed you about our recently submitted paper "Re-Weighted l_1 Dynamic Filtering for Time-Varying Sparse Signal Estimation". Well the code is ready and I posted it up on my website:

http://users.ece.gatech.edu/~acharles6/downloads.html. The MATLAB code inside will both perform the functionality in the recently submitted re-weighted l1 dynamic filtering paper as well as the basis pursuit de-noising dynamic filtering from an earlier CISS paper "Sparsity penalties in dynamical system estimation" (both texts are also available on my website:

http://users.ece.gatech.edu/~acharles6/publications.html).

Cheers,

-Adam

Thanks Adam!. We covered Re-Weighted l_1 Dynamic Filtering for Time-Varying Sparse Signal Estimation but not Sparsity penalties in dynamical system estimation by Adam Charles, M. Salman Asif, Justin Romberg, Christopher Rozell. The abstract reads:

In this work we address the problem of state estimation in dynamical systems using recent developments in compressive sensing and sparse approximation. We formulate the traditional Kalman ﬁlter as a one-step update optimization procedure which leads us to a more uniﬁed framework, useful for incorporating sparsity constraints. We introduce three combinations of two sparsity conditions (sparsity in the state and sparsity in the innovations) and write recursive optimization programs to estimate the state for each model. This paper is meant as an overview of different methods for incorporating sparsity into the dynamic model, a presentation of algorithms that unify the support and coefﬁcient estimation, and a demonstration that these suboptimal schemes can actually show some performance improvements (either in estimation error or convergence time) over standard optimal methods that use an impoverished model.

Credit: NASA/ESA

Tuesday, August 21, 2012

Streaming Data Mining Tutorial slides (and more)

Jelani Nelson.and Edo Liberty just released an important tutorial they gave at KDD 12 on the state of the art and practical algorithms used in mining streaming data, it is entitled: Streaming Data Mining I personally marvel at the development of these deep algorithms which, because of the large data streams constraints, get to redefine what it means to do seemingly simple functions such as counting in the Big Data world. Here are some slides that got my interest, but the 111 pages are worth the read:

of related interest we have the recent Improved Concentration Bounds for Count-Sketch by Gregory T. Minton, Eric Price. The abstract reads:

We present a refined analysis of the classic Count-Sketch streaming heavy hitters algorithm [CCF02]. Count-Sketch uses O(k log n) linear measurements of a vector x in R^n to give an estimate x' of x. The standard analysis shows that this estimate x' satisfies ||x'-x||_infty^2 < ||x_tail||_2^2 / k, where x_tail is the vector containing all but the largest k coordinates of x. Our main result is that most of the coordinates of x' have substantially less error than this upper bound; namely, for any c < O(log n), we show that each coordinate i satisfies

(x'_i - x_i)^2 < (c/log n) ||x_tail||_2^2/k with probability 1-2^{-c}, as long as the hash functions are fully independent. This subsumes the previous bound. Our improved point estimates also give better results for l_2 recovery of exactly k-sparse estimates x^* when x is drawn from a distribution with suitable decay, such as a power law.

Our proof shows that any random variable with positive real Fourier transform and finite variance concentrates around 0 at least as well as a Gaussian. This result, which may be of independent interest, gives good concentration even when the noise does not converge to a Gaussian.

For additional reference:

Already earlier this month, we saw this subject area in different meetings and blog entries:

Let us first recall that in Coding, Complexity, and Sparsity Workshop Slides, Piotr Indyk presented a Tutorial on compressive sensing/streaming algorithms.

The count-min sketch and related algorithms have a dedicated page. Of related interest is the excellent Probabilistic Data Structures for Web Analytics and Data Mining blog entry by Ilya Katsov.

More recent blog entries by Andrew McGregor, Suresh Venkatasubramanian and Anna Gilbert summarized the recent Dortmund meeting:

Of interest are the slides in the following meetings:

and videos and slides from the UC Berkeley Conference: From Data to Knowledge: Machine-Learning with Real-time and Streaming Applications with all the videos here: Part 1, Part 2, Part 3, Part 4, Part 5.

In particular in Part 3: Videos of the UC Berkeley Conference: "From Data to Knowledge: Machine-Learning with Real-time and Streaming Applications"

Petros Drineas talked about Randomized Algorithms in Data Mining: a Linear Algebraic Approach

We recently also covered similar work on Nuit Blanche on the subject of Randomization and Linear Algebra:

Fast approximation of matrix coherence and statistical leverage, Michael Mahoney, Petros Drineas, Malik Magdon-Ismail, David Woodruff
Parallel implementation of a fast randomized algorithm for the decomposition of low rank matrices by Andrew Lucas, Mark Stalzer, John Feo .

Nuit Blanche Referenced in the Dead Tree World!

The Big Picture in Compressive Sensing was mentioned in an article of La Recherche, the french speaking equivalent/competitor to Science. October 2010 issue, page 20-21.
Wired Magazine had a piece on Compressed Sensing featuring links to this blog and the Big Picture. (March 1, 2010)
Emmanuel Candes and Terry Tao wrote about Nuit Blanche in the Dec. '08 issue of the IEEE Information Theory Society Newsletter
Xiaochuan Pan, Emil Sidky and Michael Vannier wrote about Nuit Blanche in Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction?.
Check also the acknowledgments in this Ghost Imaging paper and this one.

Nuit Blanche

Page Views on Nuit Blanche since July 2010